描述

Boatherds公司是一家在Trabantustan国家运营的航海公司，提供Trabantian河流上的乘船旅行。所有河流都发源于山区，在流向低地的过程中逐渐汇合，最终形成一条大河入海。此外，Trabantian的村庄恰好位于河流的源头、汇合处以及大河的入海口。请注意，在汇合处可能有超过$2$条河流交汇。然而，这些河流始终形成一棵树（村庄为顶点）。

Boatherds的定价政策非常简单：每条河流的两个村庄之间的每一段都被赋予一个价格（双向价格相同），因此如果游客要求在两个村庄之间旅行，售票员只需将路径上各段的价格相加即可。

有一天，一位非常奇怪的游客出现了。她告诉售票员，她第二天就要回国，并希望将剩余的钱全部花在乘船旅行上，因此他们需要找到一条价格恰好等于她剩余金额的路线。作为（咳咳）贫穷的商人，他们向Abacus Calculator Makers寻求帮助。

给定河流网络的描述（包括河段的价格）和一个整数序列$x_1, \ldots, x_k$。对于每个$x_i$，你需要确定河流网络中是否存在一对村庄$(a, b)$，使得$a$和$b$之间的旅行费用恰好为$x_i$。

输入

输入包含多个实例。每个实例的描述如下（按以下顺序）：

• 一行一个整数：村庄数量$N$（$1 \leq N \leq 10\,000$）。
• $N$行描述村庄。第$i$行（$1 \leq i \leq N$）描述编号为$i$的村庄，包含以空格分隔的整数$d_1, c_1, d_2, c_2, \ldots, d_{k_i}, c_{k_i}, 0$。$d_j$是直接流向村庄$i$的河流上游村庄编号（之间没有其他村庄），$c_j$是村庄$i$和$d_j$之间的旅行价格。此外，$2 \leq d_j \leq N$且$0 \leq c_j \leq 1\,000$。村庄1始终对应大河的入海口，因此$d_j$不可能为1。
• $M \leq 100$行描述查询。第$i$行对应第$i$个查询，包含一个整数$x_i$（$1 \leq x_i \leq 10\,000\,000$）。
• 实例以一个单独的行“0”结束。

整个输入以一个单独的行“0”结束。

输出

对于每个实例，输出$M$行（$M$是该实例中的查询数量）。第$i$行如果存在满足条件的村庄对，输出“AYE”，否则输出“NAY”。

每个实例的输出后需跟一个单独的行，内容为一个点“.”。

输入数据 1

6  
2 5 3 7 4 1 0  
0  
5 2 6 3 0  
0  
0  
0  
1  
8  
13  
14  
0  
0  

输出数据 1

AYE  
AYE  
NAY  
AYE  
.  

来源
捷克技术大学公开赛2004