题目背景

模板题。

题目描述

有 $n$ 个点，从 $1 \sim n$ 编号，第 $i$ 个点有一个权值 $w_i$，初始没有边。

有 $m$ 个操作，如果操作后，这个无向图的每个连通块都是个仙人掌，且不存在自环，那这个操作合法，否则不合法。不合法的操作忽略。一共有六种操作：

1. 在结点 $v,u$ 间连一条权值为 $w$ 的边；

2. 在结点 $v,u$ 间删掉一条权值为 $w$ 的边；

3. 把结点 $v$ 到结点 $u$ 的最短路上的每一个结点的权值都加上 $d$；

4. 把以结点 $v$ 为根，子仙人掌 $u$ 的每一个结点的权值都加上 $d$；

5. 查询结点 $v$ 到结点 $u$ 的最短路信息。

   输出两个用空格隔开的整数 $min,\sigma$，分别代表最短路上点权的最小值、和。

   如果没有路可到达则 $min=-1,\sigma =-1$。

   如果最短路不唯一则 $min=-2,\sigma =-2$。

6. 查询以结点 $v$ 为根，子仙人掌$u$的信息。

   输出两个用空格隔开的整数 $min,\sigma$，分别代表子仙人掌 $u$ 中点权的最小值、和。

   如果 $v,u$ 不连通则 $min=-1,\sigma =-1$。

以结点 $v$ 为根，子仙人掌 $u$ 的定义是，删掉 $v$ 到 $u$ 之间的所有简单路径上的边之后，$u$ 所在的连通块。

输入格式

第一行两个用空格隔开的正整数 $n,m$ 表示一共有 $n$ 个结点，$m$ 个操作。

接下来一行 $n$ 个正整数，第 $i$ 个正整数为 $w_i$。

接下来 $m$ 行，每行代表一个操作，每行前三个整数：$opt_i,v_i,u_i$

若 $opt_i \in \{ 1,2,3,4 \}$ 则接下来再输入一个整数，否则此行结束。

输出格式

对于操作 $5$、$6$，输出相应的结果。

11 23
10 5 11 7 8 14 30 3 16 20 19
1 1 2 5
1 2 3 3
1 3 4 7
1 4 5 8
1 2 6 10
1 6 7 15
1 4 7 3
1 6 8 9
1 6 8 6
1 7 9 12
1 9 11 10
1 7 10 4
1 9 10 8
5 5 11
5 2 10
6 8 7
3 8 5 100
5 1 7
6 8 7
4 11 7 1000
5 8 3
4 3 2 2333
5 1 5

-2 -2
5 73
16 85
5 263
16 185
1005 4233
1011 9907

提示

【数据范围】
对于 $100\%$ 的数据，$1 \leq n \leq 50000, 1 \leq m \leq 250000$

保证操作 $1$、$2$ 中的 $w$ 满足 $1 \leq w \leq 10000$，所以关于边权的计算不会超出 $32$ 位有符号整数范围。

保证初始的 $w_i$ 不超过 $10^9$，保证所有操作 $3$、$4$ 中的 $d$ 之和不超过 $10^9$。