在一个名为 Midsommer 的遥远国度，有一个可爱的小河口三角洲。河里流淌着深紫色的酸液，因此无法在其中游泳。三角洲上有几座岛屿，以及连接某些岛屿对的桥梁。每座桥都被赋予了一个危险等级，用以衡量通过该桥的危险程度，等级越高越危险。

侦探（碰巧也是一位推理小说作家）Richard Hradecki 经常需要在岛屿之间往返以侦破案件。在所有可能的路径中，他更倾向于选择最安全的一条，这意味着路径上所有桥梁的最大危险等级必须尽可能低。

为了便于规划，Richard 通常会请你帮他寻找从一座岛屿到他正在调查的另一座岛屿的最安全路径。为了能够满足他的请求，你需要持续记录以下三种类型的事件：

• 当地部落的成员刚刚在两座岛屿之间新建了一座桥。
• 一只粉色毛茸茸的巨大酸液熊 Lug 出现并摧毁了一座桥。
• Richard 请你寻找两座岛屿之间的最安全路径。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$（$2 \le N \le 10^5$ 且 $1 \le Q \le 10^5$）。$N$ 是岛屿的数量（编号为 $0, 1, \dots, N - 1$），$Q$ 是接下来的事件数量。

接下来的 $Q$ 行中，每行代表一个事件，包含三个或四个整数，其含义如下：

• 0 X Y V：在岛屿 $X$ 和 $Y$ 之间刚刚新建了一座危险等级为 $V$（$0 \le V < 10$）的桥。
• 1 X Y：连接岛屿 $X$ 和 $Y$ 的桥刚刚被摧毁。
• 2 X Y：Richard 询问从岛屿 $X$ 到岛屿 $Y$ 的最安全路径是什么。

对于所有类型的事件，$X$ 和 $Y$ 表示一对合法的岛屿（$0 \le X, Y < N$ 且 $X \neq Y$）。任意两座岛屿之间最多始终只有一座桥。要被摧毁的桥在被摧毁的时刻必定存在。

输出格式

对于每个类型为 2 的事件，输出一行，表示从 $X$ 到 $Y$ 的最安全路径上最危险桥梁的危险等级。如果 $X$ 和 $Y$ 之间不存在路径，则输出 $-1$。

样例

输入样例 1

6 15
0 1 2 1
2 1 4
2 1 5
0 2 3 2
2 1 4
2 1 5
0 3 4 3
2 1 4
2 1 5
0 4 5 4
2 1 4
2 1 5
1 4 5
2 1 4
2 1 5

输出样例 1

-1
-1
-1
-1
3
-1
3
4
3
-1

输入样例 2

6 6
0 2 0 4
0 3 4 3
0 0 4 1
0 2 5 4
2 3 2
2 4 2

输出样例 2

4
4