有一天，AwD 到森林里游玩，回来之后跟 zhangzy 说，我发现好多棵会动的树耶！zhangzy 说，这有什么好稀奇的，我用手指头就能维护每棵树的形态。
于是又过了几天 AwD 到沙漠里游玩，回来之后跟 zhangzy 说，我发现好多棵会动的仙人掌耶！zhangzy 说，这有什么好稀奇的，我用脚丫子就能维护每棵仙人掌的形态。
而后又再过了几天AwD到篮球场上游玩，回来之后跟zhangzy说，我发现好多棵会动的 k-FC 耶！zhangzy 说，这有什么好稀奇的，我什么都不做就能维护每棵 k-FC 的形态了。
于是 AwD 很郁闷，他向你求助，请帮帮他吧。
如果一个无向连通图的任意一条边最多属于 $k$ 个简单环，我们就称之为 k-FC。
如果一个无向图的每个连通块都是个 k-FC，且不存在自环，我们就称之为篮球场。
为了证明你确实能够维护 k-FC，我们给你 $n$ 个结点，从 $1$ 到 $n$ 标号。
初始时没有任何边，且每个结点 $i$ 有个非负权值 $w_i$。每次进行如下操作之一：
link v u w：在结点 $v,u$ 间连一条权值为 $w$ 的边。- $1 \leq v, u\leq n$ 且 $w$ 为正整数，保证操作后图依然是个篮球场。
- 在进行该操作后输出
ok。
cut v u w：在结点 $v,u$ 间删去一条权值为 $w$ 的边。- $1 \leq v, u \leq n$ 且 $w$ 为正整数，保证操作后图依然是个篮球场。
- 在进行该操作后输出
ok（如果有多条权值为 $w$ 的边删去任意一条）。
query1 v u：查询结点 $v$ 到结点 $u$ 的最短路信息。- $1 \leq v, u \leq n$。
- 输出两个用空格隔开的整数 $\min, \sigma$，分别代表最短路上点权的最小值、和。
- 如果没有路到达则 $\min=-1, \sigma=-1$。
- 如果最短路不唯一 $\min=-2, \sigma=-2$。
query2 v u：查询以结点 $v$ 为根，子k-FC $u$ 的信息。- $1 \leq v, u \leq n$。
- 以结点 $v$ 为根，子k-FC $u$ 的定义是，删掉 $v$ 到 $u$ 之间的所有简单路径上的边之后，$u$ 所在的连通块。
- 输出两个用空格隔开的整数 $\min,\sigma$，分别代表子 k-FC $u$ 中点权的最小值、和。
- 如果 $v,u$ 不连通则 $\min=-1, \sigma=-1$。
add1 v u d：把结点 $v$ 到结点 $u$ 的最短路上的每一个结点的权值都加上 $d$。- $1 \leq v, u \leq n$ 且 $d$ 为正整数。
- 如果有路可达且最短路唯一，则输出
ok； - 否则操作非法，不进行操作并输出
failed。
add2 v u d：把以结点 $v$ 为根，子k-FC $u$ 的每一个结点的权值都加上 $d$。- $1 \leq v, u \leq n$ 且 $d$ 为正整数。
- 如果 $v,u$ 在同一个连通块里，则输出
ok； - 否则操作非法，不进行操作并输出
failed。
提示：众所周知，k-FC 是 k-Factors Cactus 的简称。
输入格式
第一行一个整数 $T$ 表示测试集编号。
第二行三个用空格隔开的正整数 $n,m,k$ 表示一共有 $n$ 个结点，$m$ 个操作，每条边最多属于 $k$ 个简单环。
接下来一行 $n$ 个正整数，第 $i$ 个正整数为 $w_i$。
接下来 $m$ 行，每行代表一个操作。
输出格式
对于每个操作，输出相应的结果。
样例数据
样例输入
0
11 23 4
10 5 11 7 8 14 30 3 16 20 19
link 1 2 5
link 2 3 3
link 3 4 7
link 4 5 8
link 2 6 10
link 6 7 15
link 4 7 3
link 6 8 9
link 6 8 6
link 7 9 12
link 9 11 10
link 7 10 4
link 9 10 8
query1 6 11
query1 2 10
query2 8 7
add1 8 5 100
query1 1 7
query2 8 7
add2 11 7 1000
query1 8 3
add2 3 2 2333
query1 1 5样例输出
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
-2 -2
5 73
16 85
ok
5 263
16 185
ok
1005 4233
ok
1011 9907子任务
一共 $18$ 个测试集：
| 分数 | 测试集编号 | $k$ 的范围 | 特殊性质 |
|---|---|---|---|
| $6$ | $1$ | $k=0$ | AB |
| $6$ | $2$ | AC | |
| $6$ | $3$ | A | |
| $5$ | $4$ | B | |
| $5$ | $5$ | C | |
| $5$ | $6$ | $ $ | |
| $6$ | $7$ | $k=1$ | AB |
| $6$ | $8$ | AC | |
| $6$ | $9$ | A | |
| $5$ | $10$ | B | |
| $5$ | $11$ | C | |
| $5$ | $12$ | $ $ | |
| $6$ | $13$ | $k=8$ | AB |
| $6$ | $14$ | AC | |
| $7$ | $15$ | A | |
| $5$ | $16$ | B | |
| $5$ | $17$ | C | |
| $5$ | $18$ | $ $ |
特殊性质 A：link 与 cut 在其他操作之前。
特殊性质 B：没有操作 query2、操作 add1 与操作 add2。
特殊性质 C：没有操作 query2 与操作 add2。
$1\leq n\leq 50000$；$1\leq m \leq 250000$。
保证 link 和 cut 操作中的 $w$ 满足 $1\leq w\leq 10000$，所以关于边权的计算不会超出 $32$ 位有符号整数范围。
保证初始的 $w_i$ 不超过 $10^9$，保证所有 add1 和 add2 操作中的 $d$ 之和不超过 $10^9$。