题目描述

Anihc 国有 $n$ 个城市，这 $n$ 个城市从 $1\sim n$ 编号，$1$ 号城市为首都。城市间初始时有 $m$ 条高速公路，每条高速公路都有一个非负整数的经济影响因子，每条高速公路的两端都是城市（可能两端是同一个城市)，保证任意两个城市都可以通过高速公路互达。

Anihc 国正在筹划「八纵八横」的高铁建设计划，计划要修建一些高速铁路，每条高速铁路两端也都是城市（可能两端是同一个城市)，也都有一个非负整数的经济影响因子。国家还计划在「八纵八横」计划建成之后，将「一带一路」扩展为「一带一路一环」，增加「内陆城市经济环」即选择一条从首都出发沿若一系列高铁与高速公路走的路径，每条高铁或高速公路可以经过多次，每座城市也可以经过多次，最后路径又在首都结束。令「内陆城市经济环」的 GDP 为依次将这条路径上所经过的高铁或高速公路的经济影响因子异或起来（一条路经过多次则会被计算多次）。

现在 Anihc 在会议上讨论「八纵八横」的建设计划方案，他们会不断地修改计划方案，希望你能实时反馈对于当前的「八纵八横」的建设计划的方案「内陆城市经济环」的最大是多少。

初始时，八纵八横计划中不包含任何—条高铁，有以下三种操作：

Add x y z

在计划中给在城市 $x$ 和城市 $y$ 之间建设一条高铁，其经济影响因子为 $z$ ，如果这是第 $k$ 个 Add 操作，则将这条高铁命名为 $k$ 号高铁。

Cancel k

将计划中的 $k$ 号高铁取消掉，保证此时 $k$ 号高铁一定存在。

Change k z

表示将第 $k$ 号高铁的经济影响因子更改为 $z$ ，保证此时 $k$ 号高铁一定存在。

输入格式

第一行三个整数 $n$ , $m$ , $P$ ，表示城市个数，高速公路条数，操作个数。

接下来 $m$ 行，每行三个整数表示高速公路的信息。

接下来 $P$ 行，每行为一个操作。

注意：输入的所有经济影响因子都将以二进制的形式从高位到低位给出。

输出格式

第一行一个整数，表示如果不修建任何高铁，「内陆城市经济环」的 GDP 最大值。

接下 $Q$ 行，每行一个整数表示进行了对应的每一个操作之后，对于当前的计划「内陆城市经济环」的 GDP 最大值。

注意：输出的答案也要以二进制的形式从高位到低位给出。

样例

input

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

1000
1001
1111
1000

数据范围与提示

令所有的经济因子二进制表示的最多位数为 $\text{len}$ 。数据满足以下表格：

对于所有的数据保证：$n,m\le 500,Q,\text{len}\le 1000,1\le x,y\le n$。且 Add 操作不超过 $550$ 个。两个城市之间可能有多条高速公路或高铁，高速公路或高铁的两端可能是同一个城市（即有重边，有自环）。