The city where Little G lives can be abstracted as a directed graph with $N$ vertices and $M$ edges. During the city's development, the roads in the city undergo some changes; specifically, there are $Q$ operations, which consist of the following two types:

1. Given a vertex $p$ and $tot$ numbers $a_i$, add edges from $a_i$ to $p$ in the graph.
2. Given a vertex $p$ and $tot$ numbers $a_i$, delete edges from $a_i$ to $p$ in the graph.

Curious Little G wants to know the reachability between all pairs of vertices after each operation.

Let $F(u, v)$ denote the reachability state between $u$ and $v$. If there exists a path from $u$ to $v$ in the graph, then $F(u, v) = 1$; otherwise, $F(u, v) = 0$. It is easy to see that $F(u, v)$ and $F(v, u)$ are not necessarily equal, and $F(u, u)$ is always 1.

For convenience in querying, each vertex has a weight $val_i$. You need to answer the value of the following expression after each operation:

$$ \sum_{u=1}^{N} \sum_{v=1}^{N} F(u, v) \times (val_u \oplus val_v) $$

where $\oplus$ denotes the bitwise XOR operation. It is guaranteed that the initial graph and the graph after each operation do not contain multiple edges or self-loops; furthermore, when an edge is deleted, it is guaranteed that the edge exists in the graph. We also have some means to force online processing.

Input

• The first line contains an integer $ID$, representing the current test case ID; the IDs for the sample cases are all 0.
• The second line contains an integer $flag$, guaranteed to be $0$ or $1$; when $flag=1$, this test case requires forced online processing.
• The third line contains three integers $N, M, Q$, representing the number of vertices, the number of edges in the initial graph, and the number of operations, respectively.
• The fourth line contains $N$ non-negative integers, representing the weight $val_i$ of each vertex.
• The next $M$ lines each contain two integers $u, v$, representing a directed edge from $u$ to $v$ in the initial graph.
• The next $2Q$ lines describe the operations, with two lines per operation:
  • The first line contains three integers $k, p, tot$. Here $k$ is $0$ or $1$; when $k=0$, it is an edge addition operation; otherwise, it is an edge deletion operation.
  • The second line contains $tot$ distinct integers $a_i$.

When $flag = 1$ (i.e., forced online), let $lastAns$ be the answer output after the previous operation (for the first operation, $lastAns=0$). You must XOR $p$ with $lastAns$ to obtain the true value of $p$.

Note: $lastAns$ can be very large!

Output

$Q$ lines, each containing an integer representing the answer after the corresponding operation.

Examples

Input 1

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

Output 1

10

Input 2

0
0
5 0 10
775753708 730589119 295766137 411078803 10973174
0 1 1
3
0 2 1
3
0 1 1
4
0 3 1
2
0 5 1
4
0 4 1
1
0 1 1
2
0 2 1
5
0 4 1
3
0 1 1
5

Output 2

1067190165
2043082587
2961479386
4033244915
4438519384
8158342623
8158342623
12528106804
12528106804
12528106804

Input 3

0
0
5 7 5
505212782 768758516 141501571 189544889 292811675
2 1
2 3
2 5
3 1
3 4
4 1
5 3
0 3 2
1 4
1 5 1
2
0 1 1
5
1 1 4
2 3 4 5
0 5 1
2

Output 3

5862031096
4844805513
4844805513
2982371382
3999596965

Note

These three examples satisfy the requirements of Type 1, Type 2, and Type 3, respectively.

Subtasks

There are 20 test cases in total, each worth 5 points. All test cases are categorized into the following three types:

Type 1 (20 points)

Guaranteed $Q = 1$, $tot = 0$, meaning only the query for the original graph is required. Also, $0 \le val_i \le 1$.

Type 2 (40 points)

Guaranteed no edge deletion operations, i.e., $k = 0$ for all operations; also $tot = 1$, $M = 0$.

Type 3 (40 points)

No special constraints:

It is guaranteed that 100% of the data satisfies:

• $N \ge 2$
• $0 \le M \le N(N-1)$
• $1 \le u, v, p, a_i \le N$
• $0 \le tot < N$
• $0 \le val_i \le 10^9$