Boatherds

Boatherds Inc.는 트라반투스탄(Trabantustan)에서 강을 따라 뱃길 여행을 제공하는 회사이다. 모든 강은 산 어딘가에서 시작해 저지대로 내려오면서 서서히 합류하고, 마지막에는 하나의 강이 되어 바다로 흘러든다. 마을은 정확히 강의 발원지, 강이 합쳐지는 지점, 그리고 가장 큰 강의 하구에 자리한다. 한 합류 지점에서 세 개 이상의 강이 만날 수도 있지만, 강들은 항상 마을을 정점으로 하는 트리(tree) 구조를 이룬다.

요금 정책은 단순하다. 이웃한 두 마을 사이의 각 강 구간에는 고정된 요금이 매겨져 있고(양방향 동일), 두 마을 사이를 오가는 요금은 두 마을을 잇는 유일한 경로 위 구간들의 요금을 모두 더한 값이다.

어느 날 특이한 관광객이 찾아왔다. 그는 내일 이 나라를 떠나며 남은 돈을 한 번의 뱃길 여행에 모두 쓰고 싶어 하여, 요금이 정확히 특정 금액인 경로를 요청한다.

각 구간의 요금이 표시된 강 네트워크와 정수 수열 $x_1, \dots, x_k$ 가 주어진다. 각 $x_i$ 에 대해, 두 마을 $(a, b)$ 사이 여행의 요금이 정확히 $x_i$ 가 되는 마을 쌍이 존재하는지 판정하여라.

입력은 여러 개의 인스턴스로 이루어진다. 각 인스턴스는 다음 순서로 주어진다.

• 마을의 수 $N$ 이 담긴 한 줄 ($1 \le N \le 10,000$).
• 마을을 설명하는 $N$ 개의 줄. 그중 $i$ 번째 줄은 마을 $i$ 를 설명하며, 공백으로 구분된 정수 $d_1, c_1, d_2, c_2, \dots, d_{k_i}, c_{k_i}, 0$ 을 담는다. $d_j$ 는 (사이에 다른 마을 없이) 강이 마을 $i$ 로 곧바로 흘러드는 마을들이고, $c_j$ 는 마을 $i$ 와 $d_j$ 사이 구간의 요금이다. 이때 $2 \le d_j \le N$, $0 \le c_j \le 1,000$ 이다. 마을 $1$ 은 항상 가장 큰 강의 하구이므로 어떤 $d_j$ 도 $1$ 이 될 수 없다. 이 목록은 하나의 $0$ 으로 끝난다.
• 질의를 설명하는 $M \le 100$ 개의 줄. $i$ 번째 줄에는 정수 $x_i$ 가 하나 있다 ($1 \le x_i \le 10,000,000$).
• 각 인스턴스는 $0$ 하나만 있는 줄로 끝난다.

전체 입력은 $0$ 하나만 있는 줄로 끝난다.

각 인스턴스마다 $M$ 개의 줄을 출력한다($M$ 은 해당 인스턴스의 질의 수). $i$ 번째 줄에는, 요금이 정확히 $x_i$ 인 경로로 이어지는 마을 쌍이 존재하면 AYE 를, 그렇지 않으면 NAY 를 출력한다.

각 인스턴스의 출력 뒤에는 마침표 하나(.)만 있는 줄을 덧붙인다.