
ZOJ Problem Set  4042
BaoBao loves playing Minecraft and he has $n$ farms in Minecraft numbered from 1 to $n$. The $i$th farm has $a_i$ carrots now. BaoBao has built $m$ railways between some pair of farms. BaoBao doesn't want to cost too much time on railways. BaoBao's tolerance of long distance travel depends on his happiness. BaoBao is willing to travel by a railway if and only if the length of the railway is not bigger than his happiness. Every day, BaoBao logs in at some farm, moves between farms by these railways and pick all carrots in all reachable farms. Now, you are given the log on BaoBao's Minecraft server. You are required to calculate BaoBao's gains of every day. The log contains two types of records in ascending order of time.
InputThere are multiple test cases. The first line of input is an integer $T$, indicating the number of test cases. For each test case: The first line contains three positive integers $n$, $m$, $q$ ($1 \le n, q \le 10^5$, $1 \le m \le 2\times 10^5$), indicating the number of farms, railways and records. The second line contains exactly $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), indicating the initial amount of carrots in $i$th farm. Each of the following $m$ lines contains three integers $u$, $v$, $w$ ($1 \le u, v \le n$, $0 \le w \le 10^9$), indicating that a railway of length $w$ connects farm $u$ and farm $v$. Each of the following $q$ lines contain three integers $op$, $s$, $t$ ($1 \le s \le n$, $0 \le t \le 10^{18}$), indicating a record in the log.
The value of $t$ is encoded to prohibit offline solutions. That is, the real value of $t$ is the bitwise exclusive or (xor) of the given $t$ and the answer of the latest query of type 2. You may suppose the answer to be 0 when there is no such query in the current test case before. It is guaranteed that the real value of $t$ is a nonnegative integer and will not be larger than $10^9$. OutputFor each record of type 2, please output the number of gathered carrots in a single line. Sample Input1 3 3 4 1 1 1 1 2 2 2 3 1 1 3 3 2 1 1 2 2 0 1 2 0 2 3 0 Sample Output1 2 4 HintHere is the raw data of sample input: 1 3 3 4 1 1 1 1 2 2 2 3 1 1 3 3 2 1 1 2 2 1 1 2 2 2 3 2 Author: ZHAO, Yueqi Source: ZOJ Monthly, June 2018 