#519. 「LibreOJ β Round #2」数学上来先打表

内存限制:50 MiB 时间限制:2333 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: nzhtl1477

题目描述

给你一个图,每个点有点权,最开始没有边。

有一些操作:

  1. 添加一条 x y 之间的双向边。

  2. 回到第 x 次操作后的状态。(注意这里的 x 可以是 0 ,即回到初始状态)

  3. 查询 x 所在联通块能到的点中点权第 y 小的值,如果不存在,那么输出 -1

输入格式

第一行输入两个数 n,m ,表示有 n 个点, m 个操作。
之后一行 n 个数,表示每个点的点权。
之后 m 行,每行有三种可能的操作:

  • 1 x y
  • 2 x
  • 3 x y

意义见题面。

输出格式

对于所有的 3 操作,输出一个数表示答案。

样例

样例输入

6 10
816801151 223885531 110182151 94271893 319888699 106363731 
1 1 3
1 3 5
1 2 4
1 4 6
1 1 2
3 1 1
2 4
1 1 2
3 1 4
2 7

样例输出

94271893
223885531

数据范围与提示

1 \le n,m \le 100000

点权在 int 范围内。