Maximum Inland City Economic Loop

Anihc is a country with n cities numbered from 1 to n, with city 1 being the capital. There are initially m highways among these cities. Each highway connects two (not necessarily distinct) cities and carries a non‐negative integer economic impact factor. It is guaranteed that any two cities are mutually reachable via the highways.

The government is planning the "Eight Longitudinal and Eight Transversal" high‐speed railway project. In this plan, some high‑speed railways will be built; each railway connects two (possibly the same) cities and also has a non‑negative integer economic impact factor. Once the project is completed, the government will extend the Belt and Road initiative into what is called the "Belt and Road Loop" by selecting a cycle that starts at the capital and follows a sequence of highways and high‑speed railways (each road or railway, as well as each city, may be visited multiple times) and then returns back to the capital. The GDP of such an inland city economic loop is defined as the XOR (\(\oplus\)) of the economic impact factors of the roads and railways in the order they are traversed (if an edge is passed multiple times, its value is counted each time).

Initially no high‑speed railways are included in the plan. There will be q operations modifying the railway plan. The operations are of three types:

• Add x y z: In the plan, add a high‑speed railway between cities x and y with economic impact factor z. The railways are numbered in the order of their addition (i.e. the first Add operation creates railway 1, the second creates railway 2, etc.).
• Cancel k: Cancel the high‑speed railway with number k from the plan. It is guaranteed that railway k exists at the time of cancellation.
• Change k z: Change the economic impact factor of railway k to z. It is guaranteed that railway k exists at the time of modification.

After each operation, you are to report the maximum possible GDP that can be achieved by some inland city economic loop.

Note: Although a cycle may traverse the same edge multiple times, because XORing a number with itself yields 0, repeating an edge an even number of times cancels out its effect.

Hint (Mathematical Formulation): Suppose a spanning tree of the highway network is used to define values \(d[u]\) (the XOR sum along the tree from the capital to city \(u\)). Then for any extra edge connecting cities \(u\) and \(v\) (be it a highway not in the tree or a high‑speed railway), the cycle formed has an XOR value of:

[ d[u] \oplus ; w \oplus ; d[v], ]

and the answer is the maximum XOR combination (over \(\oplus\)) achievable from the set of all such cycle values. This can be computed by maintaining a linear basis in \(\mathrm{GF}(2)\).

inputFormat

The first line contains three integers n, m, and q — the number of cities, the number of highways, and the number of operations, respectively.

The next m lines each contain three integers u, v, and w, describing a highway between cities u and v with economic impact factor w.

The following q lines describe an operation. Each operation is one of the following formats:

• Add x y z
• Cancel k
• Change k z

It is guaranteed that the highway network is connected and that all operations are valid.

outputFormat

After each operation, output a single line containing one integer: the maximum possible GDP of an inland city economic loop for the current high‑speed railway plan, computed as the maximum XOR value achievable.

sample

3 3 3
1 2 1
2 3 2
3 1 3
Add 1 3 4
Add 2 2 5
Cancel 1

7
7
5

</p>