给出一个字符串 s，你需要执行 m 个任务。每个任务给出两个下标 li,ri和一个整数 ki（字符串的下标从 1 开始），表示你需要循环挪动 s 的子串 s[li…ri] ki 次。请从前到后依次执行给出的每个任务。

字符串的循环挪动操作：将最后一个字符移到第一个字符的位置，并且将其他所有字符向右移一个位置。

比如：如果字符串 s 是 abacaba，一个任务为 l1=3,r1=6,k1=1，那么答案为 abbacaa。接下来一个任务为 l2=1,r2=4,k2=2，那么我们会得到 baabcaa。

In this problem, you need to add to the segment tree the operation of finding the k-th one.

Input

The first line contains two numbers n and mm (1≤n,m≤1000001≤n,m≤100000), the size of the array and the number of operations. The next line contains n numbers ai, the initial state of the array (ai∈{0,1} ). The following lines contain the description of the operations. The description of each operation is as follows:

• 1 i: change the element with index ii to the opposite.
• 2 k: find the k-th one (ones are numbered from 0, it is guaranteed that there are enough ones in the array).

Output

For each operation of the second type, print the index of the corresponding one (all indices in this problem are from 0).

Example

input

5 7
1 1 0 1 0
2 0
2 1
2 2
1 2
2 3
1 0
2 0

output

0
1
3
3
1

这题意思就是说，给你一个只有01组成的数组，有两种操作，第一个是把下标为x的元素取反（0变1，1变0），第二个操作是找到数组中的第x个1，让你输出这个的下标（比如数组是101011，那第三个1的下标就是4）。

线段树专题自然是线段树来写。先建树，线段树上的每个节点f[k]的意思是：区间l~r的1的个数。

单点修改操作对于学习过线段树的人来说并不难，这里便不再多说。重点是询问，我们该怎么利用线段树快速找到第x个1的下标。

我们每次先从根节点开始，比较两个孩子的1的个数，如果左孩子的1的个数小于x，说明第x个1应该出现在右区间，反之应该出现在左区间（如果去往右区间，那么x的值要减去左区间1的数量），当走到叶子节点时，得到的就该是第x个1的下标，我们返回并输出。

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>#define endl '\n';
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100050;
int f[4 * N], a[N];void buildtree(int k,int l,int r)
{if (l == r){f[k] = a[l];return;}int m = (l + r) / 2;buildtree(k + k, l, m);buildtree(k + k + 1, m+1, r);f[k] = f[k + k] + f[k + k + 1];
}void revise(int k, int l, int r, int x)
{if (l == r){f[k] = (f[k] == 1 ? 0 : 1);return;}int m = (l + r) / 2;if (x <= m)revise(k + k, l, m, x);else revise(k + k + 1, m + 1, r, x);f[k] = f[k + k] + f[k + k + 1];
}int quire(int k, int l, int r, int x)
{if (l == r)return l;int m = (l + r) / 2;if (f[k + k] >= x)return quire(k + k, l, m, x);else return quire(k + k + 1, m + 1, r, x - f[k + k]);
}int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];buildtree(1, 1, n);while (m--){int st, x;cin >> st >> x;if (st == 1)revise(1, 1, n, x+1);else cout << quire(1, 1, n, x+1)-1 << endl;}return 0;
}

In this task, you need to add to the segment tree the operation of finding the minimum index j such that a[j]≥x

Input

The first line contains two integers nn and mm (1≤n,m≤100000), the size of the array and the number of operations. The next line contains nn numbers aiai, the initial state of the array (0≤ai≤10^9). The following lines contain the description of the operations. The description of each operation is as follows:

• 1 i v: change the item with index i to vv (0≤i<n, 0≤v≤10^9).
• 2 x: find the minimum index j such that a[j]≥x. If there is no such element, print −1. Indices start from 0.

Output

For each operation of the second type, print the answer for the query.

Example

input

5 7
1 3 2 4 6
2 2
2 5
1 2 5
2 4
2 8
1 3 7
2 6

output

1
4
2
-1
3

这题意思就是说，给你一个数组，有两种操作，第一个是把下标为x的变成y，第二个操作是找到数组中的第一个大于x的元素的下标，让你输出这个的下标（比如数组是1 2 3 4 5，那第一个大于2的元素下标就是2，即3）。

建树和单点修改都是基础操作，这题主要点在于怎么利用线段树快速找到第一个大于x的元素。我们可以建树的时候，把每个树的节点f[k]定义为：区间l~r内的最大值。这样我们每次查询的时候，可以比较一下左右子节点的值，先看左节点存储的最大值是否大于x，如果大于，说明第一个大于x的元素应该是出现在左边。如果左节点不大于x，那就去右边找。等找到叶子节点的时候，应该就是我们要找的第一个大于x的节点了。

但是！！题目并没有保证数组里一定有大于x的元素，当数组里没有大于x的元素时，应该输出-1。所以我们到了叶子节点后别急着返回，应该先判断一下叶子节点的值是否大于x，如果大于就返回叶子节点的下标，不大于就返回-1.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>#define endl '\n';
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100050;
int f[4 * N], a[N];void buildtree(int k,int l,int r)
{if (l == r){f[k] = a[l];return;}int m = (l + r) / 2;buildtree(k + k, l, m);buildtree(k + k + 1, m+1, r);f[k] = max(f[k + k], f[k + k + 1]);
}void revise(int k, int l, int r, int x, int y)
{if (l == r){f[k] = y;return;}int m = (l + r) / 2;if (x <= m)revise(k + k, l, m, x, y);else revise(k + k + 1, m + 1, r, x, y);f[k] = max(f[k + k] , f[k + k + 1]);
}int quire(int k, int l, int r, int x)
{if (l == r){if (f[k] >= x)return l;else return -1;}int m = (l + r) / 2;if (f[k + k] >= x)return quire(k + k, l, m, x);else return quire(k + k + 1, m + 1, r, x);
}int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];buildtree(1, 1, n);while (m--){int st, x ,y;cin >> st;if (st == 1){cin >> x >> y;revise(1, 1, n, x + 1, y);}else{cin >> x;int res = quire(1, 1, n, x);if (res != -1)res--;cout << res << endl;}}return 0;
}