You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

In the enchanting kingdom of Great Britain, there are N chambers (nodes), each adorned with magical lights. These chambers are structured in a tree formation, with chamber 1 serving as the radiant root. Each chamber’s light can either be on or off:

• If the light in a chamber is on, it is represented by 1.
• If the light in a chamber is off, it is represented by 0.

Mr. Heart resides in the capital chamber and is responsible for managing the lights throughout the kingdom. He receives Q queries about the magical lights in the chambers. For each query, he will provide one of two types:

• 1 K -This command directs Mr. Heart to toggle the lights in the subtree of chamber K (including chamber K itself). If a light is currently on, it will be turned off; if it is off, it will be turned on.

• 2 K - This command requests Mr. Heart to count how many lights are currently on in the subtree of chamber K (including chamber K itself).

Your task is to process these commands efficiently and provide the King with the correct responses.

Input

First Line N (2 ≤ N ≤ \(2 * 10^5\)), the number of chambers in the palace.
The second line contains N integers \(A_1\) , \(A_2\) ,,, \(A_N\) (0 ≤ \(A_i\) ≤ 1), where \(A_i\) indicates the initial state of the light in chamber i.
Next N - 1 Lines each contains two integers U and V, indicating a connection between chambers U and V.
The next line which contains Q (1 ≤ Q ≤ \(2 * 10^5\)), the number of Query.
Each query takes two types of input in the following format

• 1 K
• 2 K

K(1 ≤ K ≤ N), a specific node(chamber) of the kingdom

Output

For each "2 K" command, output the number of chambers in the subtree of K (including chamber K) that currently have their lights on.

Sample

5
1 0 0 1 1
1 2
1 3
3 4
4 5
3
2 1
1 1
2 1

3
2

Before applying 1 K

After applying 1 1