题目背景

已添加样例解释

在小学五年级的时候，$xtq$迷上了各种奇奇怪怪的魔塔。 关于魔塔游戏的背景：https://baike.baidu.com/item/魔塔/861619?fr=aladdin

对于题意理解可能并没有任何微小的作用

题目描述

xtq 现在正在玩一个魔塔。这个魔塔十分特殊，不是由正方形格子构成的，而是一个 $n$ 个点，$m$ 条边的无向图，而且每条边上都会有一个怪物。xtq 经过了重重阻拦，现在到达了一个奖励层。

在这层内，所有怪物都不会让 xtq 掉血，但是对于每一个怪物如果 xtq 不到一定血量他就无法攻击这个怪物。每一个点上还有一个宝石，宝石的种类有很多，但是如果 xtq 到了一个点但是他已经拥有了这种宝石，他是不能捡起的。他现在想要知道从这个魔塔的一个点到另一个点所需要的最小血量是多少，还要知道如果他从一个点到达这个魔塔，以某个血量能够捡到的宝石数量是多少。还有一件事令 xtq 十分头疼：这个魔塔由于一些神秘的力量，可能宝石的种类会发生变化。保证如果 xtq 的血量无穷大，他就可以走到这一层的任何地方。

输入格式

第一行三个数 $n,m,q$ 代表点数，边数和操作数量

第二行 $n$ 个数，代表每个点上宝石的种类

下面 $m$ 行每行三个数 $u,v,t$，代表 $u$ 和 $v$ 之间有一条路，路上有一个需要 $t$ 点血量才能击杀的怪物

然后 $q$ 行每行三个数 $opt,x,y$

$opt=1$ 时将 $x$ 点的宝石改成第 $y$ 种

$opt=2$ 代表查询从 $x$ 点要到达 $y$ 点所需的最小血量

$opt=3$ 代表查询从 $x$ 点到达魔塔，血量为 $y$ 能捡到多少宝石

输出格式

对于每一个 $2$ 操作和 $3$ 操作，输出一行答案

4 4 4
4 6 4 2
1 2 8
3 2 3
2 4 2
4 1 7
3 4 3
1 4 4
3 1 7
2 4 3

3
2
3

提示

样例解释：

第一次操作为3号操作，从4开始，有3点血量，可以到达 $\{2,3,4\}$，可以获得的宝石种类为 $\{2,4,6\}$

第二次将 $1$ 的宝石种类修改为 $4$，即下图：

第三次为 $3$ 操作，从 $1$ 开始，可以到达的点为 $\{1,2,3,4\}$，可以获得的宝石种类为 $\{4,6\}$。

第四次为 $2$ 操作，从 $4$ 走到 $3$，至少需要 $3$ 点血量。

测试点	$n$	$m$	$q$	有无修改操作
$1$	$10$	$20$	$10$	有
$2 \sim 3$	$1000$	$5000$		^
$4 \sim 5$	$8000$	$30000$	$20000$
$6$	$20000$	$100000$		无
$7$	^			有
$8$	$50000$	$200000$		无
$9$	^		^	有
$10$	$100000$	$300000$		^

对于 $100\%$ 的数据，$n \le 100000,m \le 300000,q \le 200000$

剩余所有数字 $\le \text{intmax}$

保证查询的区间是随机生成的（其实是出题人懒得再写 generator 了）