Description

维护一个长度为n的正整数序列a_1,a_2,...,a_n，支持以下两种操作：

1 k，将序列a从小到大排序，输出a_k的值。

2 k，将所有严格大于k的数a_i减去k。

Input

第一行包含两个正整数n,m(1<=n,m<=100000)，分别表示序列的长度和操作的个数。

第二行包含n个正整数a_1,a_2,...,a_n(1<=a_i<=10^9)，分别表示序列中的每个元素。

接下来m行，每行两个正整数op(1<=op<=2),k，若op=1，则1<=k<=n；若op=2，则1<=k<=10^9；依次描述每个操作。

Output

输出若干行，对于每个询问输出一行一个整数，即第k小的值。

Sample Input

4 5

1 5 6 12

2 5

1 1

1 2

1 3

1 4

Sample Output

1

1

5

7

Solution

把数排个序然后建$Splay$，每次修改对值域为$[1,k]$中的不管，$[k+1,k\times 2]$中的拆出来改完了再暴力插回去，对于$[k\times 2+1,MAX]$中打标记。我也不知道为什么复杂度是对的。

以后别有事没事把标记下传到$0$点，修改着修改着$0$下标的值就不知道被修改成什么鬼畜的数了。

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #define N (100009)  5 using namespace std;  6   7 int n,m,opt,k,a[N];  8 int Root,Father[N],Son[N][2];  9 int Val[N],Size[N],Max[N],Add[N]; 10  11 int Get(int x) {
   return Son[Father[x]][1]==x;} 12  13 void Pushup(int x) 14 { 15     Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+1; 16     Max[x]=max(Val[x],max(Max[Son[x][0]],Max[Son[x][1]])); 17 } 18  19 int Build(int fa,int l,int r) 20 { 21     if (l>r) return 0; 22     int mid=(l+r)>>1; 23     Father[mid]=fa; Val[mid]=a[mid]; 24     Son[mid][0]=Build(mid,l,mid-1); 25     Son[mid][1]=Build(mid,mid+1,r); 26     Pushup(mid); return mid; 27 } 28  29 void Rotate(int x) 30 { 31     int wh=Get(x); 32     int fa=Father[x],fafa=Father[fa]; 33     if (fafa) Son[fafa][Son[fafa][1]==fa]=x; 34     Father[fa]=x; Son[fa][wh]=Son[x][wh^1]; 35     if (Son[fa][wh]) Father[Son[fa][wh]]=fa; 36     Father[x]=fafa; Son[x][wh^1]=fa; 37     Pushup(fa); Pushup(x); 38 } 39  40 void Pushdown(int x) 41 { 42     if (Add[x]!=0) 43     { 44         if (Son[x][0]) 45         { 46             Val[Son[x][0]]+=Add[x]; 47             Add[Son[x][0]]+=Add[x]; 48             Max[Son[x][0]]+=Add[x]; 49         } 50         if (Son[x][1]) 51         { 52             Val[Son[x][1]]+=Add[x]; 53             Add[Son[x][1]]+=Add[x]; 54             Max[Son[x][1]]+=Add[x]; 55         } 56         Add[x]=0; 57     } 58 } 59  60 void Push(int x) 61 { 62     if (Father[x]) Push(Father[x]); 63     Pushdown(x); 64 } 65  66 void Splay(int x,int tar) 67 { 68     Push(x); 69     for (int fa; (fa=Father[x])!=tar; Rotate(x)) 70         if (Father[fa]!=tar) 71             Rotate(Get(fa)==Get(x)?fa:x); 72     if (!tar) Root=x; 73 } 74  75 int Findkth(int x) 76 { 77     int now=Root; 78     while (1) 79     { 80         Pushdown(now); 81         if (Size[Son[now][0]]>=x) now=Son[now][0]; 82         else 83         { 84             x-=Size[Son[now][0]]; 85             if (x==1) {Splay(now,0); return Val[now];} 86             x--; now=Son[now][1]; 87         } 88     } 89 } 90  91 int Find(int x) 92 { 93     int now=Root,ans=0; 94     while (1) 95     { 96         Pushdown(now); 97         if (Max[Son[now][0]]>x) now=Son[now][0]; 98         else 99         {100             if (Val[now]>x) {Splay(now,0); return now;}101             now=Son[now][1];102         }103     }104 }105 106 int Pre(int x)107 {108     Splay(x,0);109     x=Son[x][0];110     while (Son[x][1]) x=Son[x][1];111     return x;112 }113 114 void Insert(int x)115 {116     int now=Root,fa=0;117     while (1)118     {119         Pushdown(now);120         if (!now)121         {122             Father[x]=fa;123             Son[fa][Val[fa]