The country of Anihc has $n$ cities, numbered $1$ to $n$, with city $1$ being the capital. Initially, there are $m$ highways between the cities. Each highway has a non-negative integer economic impact factor, and each highway connects two cities (possibly the same city). It is guaranteed that any two cities are reachable from each other via highways.

Anihc is planning the "Eight Verticals and Eight Horizontals" high-speed railway project. The plan involves building several high-speed railways, each connecting two cities (possibly the same city) and having a non-negative integer economic impact factor. After the completion of the "Eight Verticals and Eight Horizontals" project, the country plans to expand the "Belt and Road" into the "Belt and Road and One Ring" by adding an "Inland City Economic Ring." This is defined as a path starting from the capital, following a series of high-speed railways and highways, and ending back at the capital. Each high-speed railway or highway can be traversed multiple times, and each city can be visited multiple times. The GDP of the "Inland City Economic Ring" is defined as the XOR sum of the economic impact factors of all high-speed railways or highways traversed along this path (if a road is traversed multiple times, its factor is included multiple times).

Anihc is currently discussing the construction plan for the "Eight Verticals and Eight Horizontals" project. They will continuously modify the plan, and they want you to provide real-time feedback on the maximum possible GDP of the "Inland City Economic Ring" for the current plan.

Initially, the "Eight Verticals and Eight Horizontals" plan contains no high-speed railways. There are three types of operations:

Add x y z

Construct a high-speed railway between city $x$ and city $y$ with an economic impact factor of $z$. If this is the $k$-th Add operation, this railway is named the $k$-th high-speed railway.

Cancel k

Cancel the $k$-th high-speed railway. It is guaranteed that the $k$-th high-speed railway exists at this time.

Change k z

Change the economic impact factor of the $k$-th high-speed railway to $z$. It is guaranteed that the $k$-th high-speed railway exists at this time.

Input

The first line contains three integers $n$, $m$, and $P$, representing the number of cities, the number of highways, and the number of operations, respectively.

The next $m$ lines each contain three integers representing the information of a highway.

The next $P$ lines each contain an operation.

Note: All economic impact factors in the input are given in binary form from the most significant bit to the least significant bit.

Output

The first line contains an integer representing the maximum GDP of the "Inland City Economic Ring" if no high-speed railways are built.

The next $Q$ lines each contain an integer representing the maximum GDP of the "Inland City Economic Ring" after each corresponding operation.

Note: The output answers must also be given in binary form from the most significant bit to the least significant bit.

Examples

Input 1

4 4 3
1 2 1110
1 3 10
2 4 1110
2 3 100
Add 3 4 11
Change 1 101
Cancel 1

Output 1

1000
1001
1111
1000

Subtasks

Let $\text{len}$ be the maximum number of bits in the binary representation of all economic factors. The data satisfies the following table:

For all data, it is guaranteed that $n, m \le 500$, $Q, \text{len} \le 1000$, and $1 \le x, y \le n$. There are no more than $550$ Add operations. There may be multiple highways or high-speed railways between two cities, and the two ends of a highway or high-speed railway may be the same city (i.e., there may be multiple edges and self-loops).