In many parts of Russia, it snows during the winter. There are $N$ cities in Russia, numbered from $0$ to $N-1$. There are $N-1$ roads, numbered from $0$ to $N-2$. Road $i$ ($0 \le i \le N-2$) connects two distinct cities $A_i$ and $B_i$ ($0 \le A_i < B_i \le N-1$) in both directions. It is possible to travel between any two distinct cities in Russia by passing through some sequence of roads.

The snowy condition of each road changes from day to day. On any given day, each road is either snowy or not snowy. The snowy condition of a road does not change during the course of a single day.

Anya and Boris work at the Russian Department of Transportation. Anya works in the road information management department, and Boris works in the department that answers questions from citizens. A citizen's question is: "What is the minimum number of snowy roads I must pass through to travel from the capital city, city 0, to a certain other city?" Boris usually answers citizens after receiving a question and communicating with Anya.

Recently, a world programming contest is being held in Russia for $Q$ days. During the contest, it is expected that communication lines will be congested, making it difficult for Anya and Boris to communicate directly. Therefore, Anya and Boris have decided to communicate in the following way:

• At the beginning of each day, Anya receives the snowy road information for that day and sends data to a relay server.
• When Boris receives a question from a citizen, he answers it by communicating with the relay server.

However, there are the following constraints on the communication between Anya and Boris:

• The capacity of the relay server is $L = 1000$ bits. Anya can store at most $L$ bits of information in the relay server.
• The data stored in the relay server is initialized to all 0s at the beginning of each day.
• Boris can read a specified 1 bit of information by interacting with the relay server once.
• To answer a question, Boris can interact with the relay server at most 20 times per question.

You, an acquaintance of the Director of the Department of Transportation, have been asked to devise a strategy for Anya and Boris.

Anya and Boris's communication strategy

Implementation Details

You must submit two files in the same programming language.

The first file is named Anya.c or Anya.cpp. This file implements Anya's strategy and must implement the following two routines. The program must include Anyalib.h.

• void InitAnya(int N, int A[], int B[]) This function is called exactly once for each test case.

  • The argument N represents the number of cities.
  • The arguments A[] and B[] are arrays of length $N-1$, representing the road connection information. Elements A[i] and B[i] ($0 \le i \le N-2$) are integers representing that road $i$ connects cities A[i] and B[i] in both directions, satisfying $0 \le A[i] < B[i] \le N-1$.

• void Anya(int C[]) This function is called $Q$ times after InitAnya is called. This function corresponds to Anya deciding the bit string to store in the relay server after the snowy road information is updated at the beginning of the day.

  • The argument C[] is an array of length $N-1$, representing the snowy road information. Element C[i] ($0 \le i \le N-2$) is an integer of 0 or 1, where C[i] = 1 means road $i$ is snowy, and C[i] = 0 means road $i$ is not snowy.

Within the function Anya, you can call the following function:

• void Save(int place, int bit) This function represents the operation of Anya saving a bit to the relay server.
  • The argument place represents the location to write the bit. place must be an integer between $0$ and $L-1$ inclusive. If a value outside this range is specified, it is judged as Wrong Answer [1]. Also, in each call to the function Anya, you cannot call this with the same place argument more than once. If called twice with the same argument, it is judged as Wrong Answer [2].
  • The argument bit is an integer representing the bit to be written, which must be 0 or 1. If any other value is specified, it is judged as Wrong Answer [3].

After the Save call, the content of the place-th bit of the relay server becomes bit. If a Save call is judged as a Wrong Answer, the program terminates at that point.

Immediately before the function Anya is called, the bits in the relay server are always initialized to all 0s. That is, at the end of the function Anya, locations where no save operation was performed by the Save function contain 0.

The second file is named Boris.c or Boris.cpp. This file implements Boris's strategy and must implement the following two routines. The program must include Borislib.h.

• void InitBoris(int N, int A[], int B[]) This function is called exactly once for each test case.

  • The argument N represents the number of cities.
  • The arguments A[] and B[] are arrays of length $N-1$, representing the road connection information. Elements A[i] and B[i] ($0 \le i \le N-2$) are integers representing that road $i$ connects cities A[i] and B[i] in both directions, satisfying $0 \le A[i] < B[i] \le N-1$.

• int Boris(int city) This function is called several times after InitBoris is called. This function corresponds to Boris's action in response to a citizen's question.

  • The argument city represents the citizen's question. city is an integer between $1$ and $N-1$ inclusive. This represents the citizen asking for the minimum number of snowy roads they must pass through to travel from city 0 to city.
  • The function Boris must return an integer between $0$ and $N-1$ inclusive, which is the answer to the citizen's question. If an integer outside this range is returned, it is judged as Wrong Answer [4]. If the answer is incorrect, it is judged as Wrong Answer [7].

Within the function Boris, you can call the following function:

• int Ask(int place) This function represents the operation of Boris reading a bit from the relay server.
  • The argument place represents the location to read the bit. place must be an integer between $0$ and $L-1$ inclusive. If a value outside this range is specified, it is judged as Wrong Answer [5]. The return value of the function Ask is an integer representing the content of the place-th bit of the relay server, which is 0 or 1. Also, the function Ask can be called at most 20 times in each call to the function Boris. If called more than 20 times, it is judged as Wrong Answer [6].

If an Ask call is judged as a Wrong Answer, the program terminates at that point.

Subtasks

1. (15 points) $N \le 20$.
2. (5 points) $N \le 100$.
3. (35 points) $A_i = i$ and $B_i = i + 1$ for all $0 \le i \le N-2$.
4. (45 points) No additional constraints.

Constraints

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1 + \dots + D_Q \le 500$.
• It is possible to travel between any two distinct cities by passing through some sequence of roads.

Examples

Input 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Output 1

1 0 0
2

Note

The example above shows the interaction flow. The first line of input is $N=5$. The next 4 lines define the edges. The next line is $Q=2$. The following lines describe the snowy roads and queries for each day. The output shows the answers provided by Boris for the queries on each day.