I. So Far Away
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
So Far Away
— Martin Garrix
在公元四世纪的欧洲大陆，一共有 $$$n$$$ 座城邦，每座城邦都有一个特征值 $$$a$$$。其中，对于任意两座不同的城邦 $$$i$$$ 和 $$$j$$$ 来说，它们之间有一条无向边，边的长度为 $$$e(i,j)=\min(a_i,a_j)$$$。

在随后的一个世纪里，发生了许多事件，包含以下两种类型：

  • 1 $$$x$$$ $$$a$$$：城邦 $$$x$$$ 的特征值变为了 $$$a$$$。
  • 2 $$$u$$$ $$$v$$$ $$$k$$$ $$$u_i$$$ $$$v_i$$$：在假设 $$$k$$$ 对城邦之间的边被断开的情况下，城邦 $$$u$$$ 和 $$$v$$$ 之间的最短距离是多少（这些边并没有真的被断开）。
对于每种类型为 $$$2$$$ 的事件，都需要输出一行整数代表答案。
Input

第一行，一个整数 $$$t(1\le t \le 10^4)$$$，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,q(2\le n\le 10^5;1\le q\le10^5)$$$，分别代表城邦的数量和事件的数量。

第二行，$$$n$$$ 个整数 $$$a_1,a_2,\dots,a_n(1\le a_i\le 10^8)$$$，代表初始时每个城邦的特征值。

接下来连续的 $$$q$$$ 行，每行一个事件。先输入一个整数 $$$op(1\le op\le 2)$$$，代表事件的类型。如果 $$$op=1$$$，则接下来输入两个整数 $$$x,a(1\le x\le n;1\le a\le 10^8)$$$，代表把城邦 $$$x$$$ 的特征值修改为 $$$a$$$。如果 $$$op=2$$$，则接下来首先输入两个整数 $$$u,v(1\le u,v \le n,u\neq v)$$$，代表当前查询最短距离的两个城邦编号。接下来一个整数 $$$k({\bf{0\le k\le \min(9,n-2)}})$$$，代表在这次查询中被断开的边的数量，接下来有 $$$k$$$ 对互不相同的整数对 $$$u_i,v_i(u_i\neq v_i)$$$，代表在当且查询中城邦 $$$u_i,v_i$$$ 之间的边被断开。

保证同一测试点内 $$$n$$$ 和 $$$q$$$ 的总和均不会超过 $$$10^5$$$。

Output

对于每种类型为 $$$2$$$ 的事件，输出一行整数代表答案。

可以证明的是，在题目给定的条件下，任意两对城邦之间都是相互联通的。

Example
Input
3
2 4
1 1
2 1 2 0
1 1 2
1 2 3
2 1 2 0
3 5
1 2 3
2 1 2 1 1 2
2 1 2 1 1 3
2 1 2 1 2 3
1 1 6
2 1 2 1 1 2
6 10
1 1 1 1 9 2
2 1 6 4 1 2 1 3 1 4 1 6
1 1 4
1 2 10
1 3 8
2 3 2 1 2 3
1 4 100000000
2 2 6 0
1 6 9
2 2 6 1 3 1
2 3 5 3 3 5 1 3 1 5
Output
1
2
3
1
1
5
3
2
2
8
17