地下城的生活有时很无聊。地下城里有 $N$ 个孩子，他们决定玩一个新游戏——组队！（Team Up!）。每个玩家都属于一个队伍。每回合，系统会等概率随机选择一个队伍。如果玩家 $i$ 和 $j$ 属于当前被选中的队伍，他们可以利用该队伍的回合来“拉拢”玩家 $k$，当且仅当 $i < k < j$。在此之后，玩家 $k$ 将加入 $i$ 和 $j$ 所在的队伍。一个队伍在任何给定的回合中也可以选择跳过（什么都不做）。

图 1：玩家 2 和 6 拉拢玩家 5。

只剩下一个玩家的队伍被视为被淘汰，因为该队伍再也无法进行任何操作。当只有一个队伍未被淘汰时，该队伍获胜。如果一个队伍在所有队伍都采取完美策略的情况下，获胜的概率为 $1$，则称该队伍为实质获胜者（effective winner）。

图 2：队伍 3 获胜。

图 3：队伍 3 是实质获胜者；对手的任何随机运气或完美发挥都无法阻止队伍 3 最终获胜。

注意，有些游戏可能没有获胜者。在以下示例中，两个队伍都无法获胜，游戏以平局结束：

图 4：两个队伍都无法取得任何进展。

孩子们想记录谁在获胜。给你 $Q$ 个查询，格式如下：

• 1 t i：玩家 $i$ 加入队伍 $t$。这一步不一定符合游戏规则（地下城的孩子们并不总是遵守规则）；玩家何时更换队伍没有任何限制。
• 2 t：输出该队伍要达到实质获胜所需的连续回合数，假设孩子们完美发挥并遵守所有规则。如果即使拥有无限个连续回合也无法获胜，则输出 $-1$。

这里，一个队伍拥有 $k$ 个连续回合意味着该队伍被选中，并且可以在接下来的 $k$ 个连续回合中进行操作。你能帮助孩子们记录谁在获胜吗？

输入格式

第一行包含两个整数 $N$ ($2 \le N \le 3 \cdot 10^5$) 和 $Q$ ($1 \le Q \le 3 \cdot 10^5$)。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，其中 $1 \le a_i \le N$ 表示第 $i$ 个玩家的初始队伍。

接下来的 $Q$ 行，每行包含以下格式之一的查询：

• 1 t i：这里 $t$ 是队伍标识符 ($1 \le t \le N$)，$i$ 是玩家编号 ($1 \le i \le N$)。
• 2 t：这里 $t$ 是队伍标识符 ($1 \le t \le N$)。

保证至少有一个第二种类型的查询。

输出格式

对于每个格式为 2 t 的查询，输出单行，包含一个整数——该队伍要达到实质获胜所需的连续回合数，如果该队伍即使拥有无限个连续回合也无法获胜，则输出 $-1$。

样例

输入样例 1

4 5
1 2 1 2
2 1
2 2
1 1 2
2 1
2 2

输出样例 1

1
1
0
-1

输入样例 2

5 2
1 2 1 2 1
2 1
2 2

输出样例 2

0
-1

输入样例 3

4 2
1 1 2 2
2 1
2 2

输出样例 3

-1
-1

输入样例 4

6 8
2 3 2 1 3 1
2 3
2 1
1 3 3
2 3
2 1
1 1 5
2 3
2 1

输出样例 4

2
-1
1
-1
-1
-1