Computational neuroscience has been a hot topic in academia in recent years as an emerging interdisciplinary field. A type of neural tissue called SHOI has attracted great attention due to its close connection with the recently discovered compound SHTSC.

The SHOI tissue consists of several SHOI cells, which form a strict tree structure. Each SHOI cell has exactly one output, called an axon. Except for one special SHOI cell, called the root cell, whose output serves as the output of the entire tissue, the axons of all other cells are connected to their parent SHOI cell. Each cell also has exactly three inputs, called dendrites, which receive information from its child cells or other neural tissues. The signaling mechanism of SHOI cells is simple, consisting only of 0 and 1. Each SHOI cell outputs the signal (0 or 1) that appears more frequently among its three inputs.

You are given information about a SHOI tissue and the changes in the inputs from external neural tissues. Please simulate the output of the SHOI tissue.

Input

The first line contains an integer $n$, representing the total number of SHOI cells. The SHOI cells are numbered $1$ to $n$, where $1$ is the root cell.

The next $n$ lines each contain three integers $x_1, x_2, x_3$, representing the dendrite connections for SHOI cells $1$ to $n$ respectively. $1 < x_i \le n$ indicates a connection to the axon of the cell numbered $x_i$, and $n < x_i \le 3n+1$ indicates a connection to an external input numbered $x_i$. The input data guarantees that the given SHOI tissue is valid and that all $x_i$ are distinct.

The next line contains $2n+1$ integers (0 or 1), representing the initial external inputs.

The $(n+3)$-th line contains an integer $q$, representing the total number of operations.

Following this, $q$ lines each contain an integer $x$, representing that the external input numbered $x$ has changed its value.

Output

Output $q$ lines, each containing an integer, corresponding to the output of the root cell after the $i$-th change in external input.

Examples

Input 1

3
2 3 4
5 6 7
8 9 10
0 0 0 0 1 1 1
5
4
4
5
6
8

Output 1

1
0
0
1
1

Constraints

• For 10% of the data, $n, q \le 1000$.
• For an additional 10% of the data, modifications only change 0 to 1.
• For an additional 30% of the data, the input SHOI structure forms a chain with the root as an endpoint.
• For 100% of the data, $n \le 500000, q \le 500000$.