背景

一步一步向你靠近
一圈一圈贴我的心
就像夜空舞蹈的流星
一步一步抱我更近
一圈一圈更确定
要陪你旋转不停

描述

情人节舞会就要开始了,男主在女主的一番教导之下终于记住了华尔兹的基本舞步,男主还不能轻松自如的跳出一些连续的舞步,于是把舞会上想要跳的舞步顺序背在心中,可是女主觉得男主说的顺序中有些舞步衔接不那么的好,她准备帮助男主修改舞步,同时也为了帮助男主记忆舞步顺序,她还会不时询问男主某一部分出现次数最多的舞步是什么,男主吓傻了。

输入格式

第一行有两个正整数n和m,表示男主背下来的舞步顺序包含n个基础舞步,女主做出的修改与询问共m次。
第二行有n个正整数(step1,step2,……,stepn),表示男主背下来的舞步顺序(这里为了简化,将舞步用数字代替)。
接下来m行每行一次操作,每行有三个自然数type,x,y:
如果type为0,表示女主将第x个舞步改成y;
如果type为1,表示女主要询问男主:
我们令上次的询问结果为ans(如果这是第一次询问,则ans = 0)
令x = (x + ans - 1) mod n + 1,y = (y + ans - 1) mod n + 1,如果此时的x > y,则交换x和y。
女主询问第x个舞步到第y个舞步中出现最多的基础舞步,如果有多个,选最小的那个step。

输出格式

对于每次的询问,输出一行,包含一个正整数step。
(提示:本题要求您使用在线算法)

样例输入

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

样例输出

1
1
2
5

数据范围与约定

对于100%的数据,1 \leq n,m\leq 21400,1\leq step_{i}\leq 10^{9},1\leq x,y\leq 10^{9},对于type = 0的情况,保证x不大于n。

样例解释

对于第一次询问,舞步顺序为5211314,询问区间为[1,7],答案为1;
对于第二次询问,舞步顺序为5221314,询问区间为[2,6],答案为1;
对于第三次询问,舞步顺序为5221314,询问区间为[2,5],答案为2;
对于第四次询问,舞步顺序为5221515,询问区间为[1,7],答案为5;

来源

灵感来自zkw***,感谢sjy (VariantF) 提供的算法优化。(Orz Orz)