Magic Tower: Min HP and Gem Collection

$xtq$ is playing a magical tower game. Unlike ordinary towers made of square grids, this magical tower is represented by an undirected graph with $n$ nodes and $m$ edges. Each edge is guarded by a monster. Although on this reward floor none of the monsters cause damage, each monster can only be attacked if $xtq$ has a certain minimum HP.

Furthermore, every node contains a gem. There are many types of gems, but if $xtq$ reaches a node and he already has that type of gem, he cannot pick it up. To complicate matters further, due to mysterious powers the gem types may change over time.

$xtq$ wants to answer two kinds of queries:

1. Given two nodes, determine the minimum HP $H_{min}$ required to travel from one node to the other. In other words, find a path from node $u$ to node $v$ such that the maximum monster threshold along the path is minimized, and output that value. (If an edge has threshold $w$, it can be used only if $HP \ge w$.)
2. Given a starting node and a HP value $H$, if $xtq$ only traverses edges with monster thresholds at most $H$, how many distinct gem types can he collect along his journey? Note that once a gem type is collected, picking up another gem of the same type has no effect.

In addition, there is an update query where the gem type at a specific node can change.

It is guaranteed that if $xtq$ has infinite HP, he can travel between any pair of nodes.

inputFormat

The input begins with a line containing three integers $n$, $m$, and $q$, where $n$ is the number of nodes, $m$ is the number of edges, and $q$ is the number of queries.

Then follow $m$ lines, each containing three integers $u$, $v$, and $w$, representing an undirected edge between nodes $u$ and $v$ with monster threshold $w$.

The next line contains $n$ integers: the $i$-th integer is the gem type at node $i$.

Then follow $q$ lines. Each query is in one of the following formats:

• Type 1: 1 u v — Query the minimum HP required to travel from node $u$ to node $v$.
• Type 2: 2 u H — Query the number of distinct gem types that can be collected starting from node $u$ when $xtq$ has HP $H$ (i.e. only traverse edges with threshold $\le H$).
• Type 3: 3 u new_gem — Update the gem type at node $u$ to new_gem.

All numbers are separated by spaces and/or newlines. It is guaranteed that with infinite HP, any node is reachable from any other node.

outputFormat

For each query of type 1 and type 2, output one line with the answer.

sample

5 5 5
1 2 10
2 3 5
3 4 7
4 5 3
1 5 12
1 2 1 3 2
1 1 3
2 2 10
3 3 4
2 2 10
1 1 5

10
3
4
10

</p>