Migrated from Lutece 2744 大大超人照四方

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

神说，要有光。 大大超人照四方。

大大超人的光辉照耀四方。 人们沐浴着大大超人的光辉，一步一步踏上光明的台阶。

每个台阶都可以看做一条双向路径，从这个地方走到那个地方，也可以从那个地方走到这个地方，每个台阶有一个光辉值 $v_i$ 和长度 $l_i$，每个台阶的光辉程度都是独特的，即没有同时存在的两个台阶光辉程度相同。 所有台阶将所有地方连接起来，有时大大超人会降下神谕，指引人们从某个地方走到另外一个地方。 人们为了表现自己的虔诚，会在所有可能的路径中选择最光辉的路径行走，最光辉的路径是指这条路径所有台阶中最低的光辉值最高，如果两条路径最低光辉值相同，则选取次低的光辉值更高的那条路径，依次类推。特别的，如果某两条台阶数为 $l_1,l_2\ (l_1<l_2)$ 路径中，前 $l_1$ 小的台阶光辉值相同，我们会认为台阶数少的路径光辉值大。 为了避免亵渎大大超人的光辉，人们不会经过重复的台阶，由于每个台阶光辉值独特，一定存在一条最光辉的道路。 你作为大大超人最忠实的信徒，想知道每次神谕指引的路径的长度，当然有可能有时候无法从一个地方走到另一个地方，这是大大超人的考验。

Input

第一行输入两个整数 $n,m$，表示地方的数量和发生的事件个数。 接下来 $m$ 行每行描述一个事件： 1、$\texttt{find id x y v l}$ 表示大大超人创造了一个连接点 $x,y$，编号为 $id$ ，光辉值为 $v$ ，长度为 $l$ 的台阶。 2、$\texttt{move x y}$ 表示大大超人降下神谕，指引人们从点 $x$ 走到 $y$。如果这是大大超人的考验，输出 $-1$即可。 3、$\texttt{change id l}$ 表示大大超人运用神力，将编号为 $id$ 的台阶长度变为 $l$（保证这个台阶存在）。

Output

对于每个 $\texttt{move}$ 的事件，输出一个整数表示答案表示最光辉的路径的长度。

Samples

8 18
find 0 0 2 7 2
find 1 2 4 4 4
find 2 4 6 10 1
find 3 6 7 8 6
move 2 7
move 1 6
find 4 2 5 3 4
move 0 5
change 0 12
find 5 4 5 5 10
find 6 2 3 6 9
move 3 5
find 7 0 1 12 1
move 1 6
find 8 1 7 11 100
move 1 6
move 5 6
move 2 2

11
-1
6
23
18
106
11
0

Constraints

$1\le n\le 100000, 1\le m \le 300000$ 对于所有操作 $0\le id\lt m, 0\le u,v \lt n, 0\le v\le 1000000000, 0 \le l \le 10000$ 保证 $\texttt{find}$ 操作中 $u\not=v$

Resources

2022 UESTC ICPC Training for Data Structures