Description

左偏树一开始有$N$个小根堆，每个堆都包含且仅包含一个数，它支持两种操作：

①$1$ $x$ $y$，将第$x$个数和第$y$个数所在的小根堆合并（若第$x$个数或第$y$个数已经被删除或两个数在同一个堆内，则无视此操作）；

②$2$ $x$，输出第$x$个数所在堆的最小值，并将其删除（若第$x$个数已被删除，则输出$-1$且无视删除操作）。

Format

Input

第$1$行包含两个正整数$N、M（N≤10^5，M≤10^5）$，分别表示开始时小根堆的个数和接下来的操作个数；第$2$行输入$N$个正整数，其中第$i$个正整数表示第$i$个小根堆初始时包含的数；接下来的$M$行，每行都包含$2$或$3$个正整数，表示一个操作。

Output

对每个操作，都单行输出结果。

Samples

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

1
2

来源

P3377