[Ynoi2014]等这场战争结束之后

题目背景

我真的能变强吗? ![](https://cdn.luogu.com.cn/upload/pic/45502.png) 【就算你不愿意,我也会逼你变强】 那么承蒙你的一片美意,我就直说了吧 ![](https://cdn.luogu.com.cn/upload/pic/45503.png) 那个嘛... 我才不想变强呢~! 【那这样吧,只要你从战场上活着回来】 【我可以答应你随便一个要求,随便什么都行】 诶? ![](https://cdn.luogu.com.cn/upload/pic/45504.png) 【结婚什么的当然免谈啦】 你说什么都行的... ![](https://cdn.luogu.com.cn/upload/pic/45505.png) 点心... 你之前不是在食堂做了点心吗 那么黄油蛋糕你会做吗 ![](https://cdn.luogu.com.cn/upload/pic/45506.png) 我的姐姐...也就是前辈们当中 有一个人每次从战场上活着回来之后 都会一脸陶醉地品尝黄油蛋糕 所以...拜托你了 【偏偏挑这个...】 【没问题,我会让你吃到吐的】 【所以,你一定要活着回来】

题目描述

给你一个图,每个点有点权,最开始没有边。 有一些操作: 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$ 的操作,输出一行,包含一个整数,表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

94271893
223885531

说明

Idea:nzhtl1477, Solution:nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space ),ccz181078( $O( m\sqrt{n\log n} )$ Time , $O(n\sqrt{n\log n} )$ Space ) , shadowice1984( $O( m\sqrt{n\log n} )$ Time , $O( n\log n )$ Space ) Code:nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space ),ccz181078( $O( m\sqrt{n\log n} )$ Time , $O( n\sqrt{n\log n} )$ Space ) , shadowice1984( $O( m\sqrt{n\log n} )$ Time , $O( n\log n )$ Space ), Data:nzhtl1477( partially uploaded ) 对于 $100\%$ 的数据,$1\leq n,m\leq 10^5$,$0\leq a_i\leq 10^9$。