Boatherds

Boatherds Inc. is a sailing company operating in the country of Trabantustan, offering boat trips on Trabantian rivers. All rivers originate somewhere in the mountains and, on their way down to the lowlands, they gradually join until a single resulting river flows into the sea. The Trabantian villages sit exactly at the rivers' springs, at their junctions, and at the mouth of the largest river. More than two rivers may meet at a junction, but the rivers always form a tree whose vertices are the villages.

The pricing policy is simple: each river segment between two neighbouring villages has a fixed price (the same in both directions). The fare for a journey between any two villages is the sum of the prices of the segments along the unique path connecting them.

One day a peculiar tourist arrived. She leaves the country tomorrow and wants to spend all of her remaining money on a single boat trip, so she asks for a route whose fare is exactly a given amount.

You are given the river network with the cost of every segment and a sequence of integers $x_1, \dots, x_k$. For each $x_i$, decide whether there exists a pair of villages $(a, b)$ such that the fare of the trip between $a$ and $b$ equals exactly $x_i$.

The input consists of several instances. Each instance is described as follows, in order:

• A line with a single integer $N$ — the number of villages ($1 \le N \le 10\,000$).
• $N$ lines describing the villages. The $i$-th of these lines describes village $i$ and contains the space-separated integers $d_1, c_1, d_2, c_2, \dots, d_{k_i}, c_{k_i}, 0$. The $d_j$ are the villages whose rivers flow directly into village $i$ (with no other village in between), and each $c_j$ is the price of the segment between villages $i$ and $d_j$. Here $2 \le d_j \le N$ and $0 \le c_j \le 1\,000$. Village $1$ is always the mouth of the largest river, so no $d_j$ is ever equal to $1$. The list is terminated by a single $0$.
• $M \le 100$ lines describing the queries. The $i$-th line contains one integer $x_i$ ($1 \le x_i \le 10\,000\,000$).
• The instance is terminated by a single line containing $0$.

The whole input is terminated by a single line containing $0$.

For each instance output a sequence of $M$ lines (where $M$ is the number of queries in that instance). The $i$-th line contains the word AYE if the network has a pair of villages joined by a path of cost exactly $x_i$, or the word NAY otherwise.

The output for each instance must be followed by a single line containing just a dot character (.).