Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4042
Carrot Gathering

Time Limit: 1 Second      Memory Limit: 131072 KB

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.

  • 1 u b: The number of carrots in farm $u$ is changed to $b$.

  • 2 u h: BaoBao starts gathering from farm $u$ with happiness $h$.


There 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.

  • If $op = 1$ then this is a record of type 1, indicating that the number of carrots in farm $s$ in changed to $t$.

  • If $op = 2$ then this is a record of type 2, indicating that BaoBao starts gathering from farm $s$ with happiness $t$.

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 non-negative integer and will not be larger than $10^9$.


For each record of type 2, please output the number of gathered carrots in a single line.

Sample Input

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 Output



Here is the raw data of sample input:

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
Submit    Status