/*  
    BISMILLAHIR RAHMANIR RAHIM
    NAME: Wasi Ur Rahman
    EMAIL: wasiurrahaman247@gmail.com
    FROM RMSTU
*/
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ll                     long long
#define boost                  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(v)                 v.begin(),v.end()
#define revall(v)              v.rbegin(),v.rend()
#define gcd(a,b)                __gcd(a,b)
#define lcm(a,b)               (a*b)/gcd(a,b)
#define pb                      push_back
#define eb                     emplace_back
#define mk                     make_pair
#define F                      first
#define S                      second
#define pi                     acos(-1.0)
#define maxv(v)                *max_element(all(v))
#define minv(v)                *min_element(all(v))
#define countv(v,a)             count(all(v),a)
#define cntone(x)             __builtin_popcountll(x) // number of ones
#define cntzero(x)             __builtin_ctzll(x) // number of zeros
#define rep(i, l, r)           for(long long i = l; i<r; i++)
#define SUM                     accumulate
#define toint(a)                atoi(a.c_str())
#define read                    freopen("input.txt","r",stdin)
#define write                   freopen("output.txt","w",stdout)
#define Unique(c)               (c).resize(unique(all(c))-(c).begin())
#define sp(a)                   fixed<<setprecision(a)
#define printv(container)       for(auto it:container) cout << it << " ";cout << endl
#define vll                     vector <ll>
#define cases(i)                cout << "Case " << i << ":"
#define yes                     cout << "YES" << endl
#define no                      cout << "NO" << endl
#define rand(V)                random_shuffle(all(V))
#define lb(a,X)                lower_bound(all(a),X)-a.begin()
#define ub(a,X)                upper_bound(all(a),X)-a.begin()
#define Testcases               ll t;cin >> t;while(t--)
using namespace std;



/*************************************
*          DEBUGGING SECTION         *
**************************************/
template<typename T>void showSTL(T H);template<typename T,typename V>void showSTL(pair<T,V> H);
template<typename T>void showSTL(priority_queue<T> H);template<typename T>void showSTL(stack<T> H);
template<typename T,typename V>void showSTL(map<T,V> H);
template<typename T,typename V>void showSTL(multimap<T,V> H);template<typename T>void showSTL(vector<T> H);
template<typename T>void showSTL(set<T> H);template<typename T>void showSTL(multiset<T> H);
template<typename T>void showSTL(list<T> H);void showSTL(char *H);
template<typename T>void showSTL(deque<T> H);template<typename T>void showSTL(queue<T> H);
template<typename T>void showSTL(T H){stringstream ss;ss<<H;cerr<<ss.str();}
template<typename T,typename V>void showSTL(pair<T,V> H){cerr<<"(";showSTL(H.first);cerr<<"=>";showSTL(H.second);cerr<<")";}
template<typename T>void showSTL(priority_queue<T> H){cerr<<endl;while(!H.empty()){cerr<<H.top()<<endl;H.pop();}cerr<<endl;}
template<typename T>void showSTL(stack<T> H){cerr<<endl;while(!H.empty()){cerr<<H.top()<<endl;H.pop();}}
template<typename T,typename V>void showSTL(map<T,V> H){cerr<<"[ ";for(auto val:H){showSTL(val);cerr<<" ";}cerr<<"]";}
template<typename T,typename V>void showSTL(multimap<T,V> H){cerr<<"[ ";for(auto val:H){showSTL(val);cerr<<" ";}cerr<<"]";}
template<typename T>void showSTL(vector<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(set<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(multiset<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(list<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
void showSTL(char *H){for(int i=0;i<strlen(H);i++){showSTL(H[i]);};}
template<typename T>void showSTL(deque<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(queue<T> H){cerr<<"[ ";while(!H.empty()){showSTL(H.front());cerr<<' ';H.pop();}cerr<<"]";}
vector<string>vec_spltr(string s){s+=',';vector<string>res;while(!s.empty())
res.push_back(s.substr(0, s.find(','))),s=s.substr(s.find(',')+1);return res;}
void dbg_out(vector<string>__attribute__((unused))args,__attribute__((unused))int idx,__attribute__((unused))int LINE_NUM)
{cerr<<endl;}template<typename Head,typename... Tail>
void dbg_out ( vector <string> args, int idx, int LINE_NUM, Head H, Tail... T)
{if(idx>0)cerr<<", ";else cerr << "Line(" << LINE_NUM << "):";
cerr<<" "<<args[idx]<<" = ";showSTL(H);dbg_out(args,idx+1,LINE_NUM, T...);}
#define debug(...) dbg_out(vec_spltr(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)

     /*   CHANGE VALUE OF MOD HERE   */
#define MOD 1000000007
const int N = 1000000;

         /*    MODULAR ARITHMETICS   */
ll add(ll a,ll b,ll mod){a += b;return ((a >= mod) ? a - mod : a);}
ll sub(ll a,ll b,ll mod){a -= b;return ((a < 0) ? a + mod : a);}
ll mult(ll a,ll b,ll mod){ll ans = (a%mod)*(b%mod);if(ans >= mod)ans %= mod;return ans;}
ll bigmod(ll x,ll n,ll mod){if(n == 0)return 1;ll ans = bigmod(x,n/2,mod);ans = mult(ans,ans,mod);if(n & 1) ans = mult(x,n,mod);return ans;}


        /*    CUSTOM FUNCTIONS   */
bool isPowerOfTwo (ll x) {return x && (!(x&(x-1)));}
bool isPerfectSquare(long double x){long double sr = sqrt(x);return ((sr - floor(sr)) == 0);}
ll digNO(ll num){  return floor(log10(num)) + 1; }
int findSqrt(int n) { int lo = 0, hi = n; while (lo <= hi) { int mid = (lo + hi) / 2; if (mid * mid <= n) lo = mid + 1; else hi = mid - 1; }return lo - 1;}
ll fib(ll n){double phi = (1+sqrt(5))/2;return round(pow(phi,n)/sqrt(5));}
ll count_N_in_Fact(ll n,ll k){ll res = 0,sum = 0;for(ll i = k;;i*=k){res = n/i;if(res == 0)break;sum += res;}return sum;}
string v2s(vll &A){ll Z=A.size();string S(Z,' ');rep(i,0,Z)S[i]=A[i]+'0';return S;}
bool isPrime(ll n) {if (n <= 1) return false;if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false; for (ll i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
void solve();
int main() {
    boost;
    //Testcases
        solve();
    return 0;
}
void solve(){
    ll n,q;
    cin >> n >> q;
    vector<ll> v;ll one = 0,zero = 0;
    for(ll i = 0;i<n;i++)
    {
        ll x;
        cin >> x;
        v.pb(x);
        if(x == 1)
            one++;
        else zero++;
    }vector<pair<ll,ll>> vis;
    while(q--)
    {
        ll a,b;
        cin >> a >> b;
        vis.pb({a,b});
    }
    for(ll i = 0;i<vis.size();i++)
    {
        if(vis[i].F == 1)
        {
            ll x = vis[i].S;
            if(v[x-1] == 1)
            {
                v[x-1] = 0;
                zero++;one--;
            }else{
                v[x-1] = 1;
                one++;zero--;
            }
        }else{
            if(vis[i].S > one)
                cout << 0 << endl;
            else cout << 1 << endl;
        }
    }
}
### Prompt

In cpp, your task is to solve the following problem:

You are given an array a consisting of n integers. Initially all elements of a are either 0 or 1. You need to process q queries of two kinds:

  * 1 x : Assign to a_x the value 1 - a_x. 
  * 2 k : Print the k-th largest value of the array. 



As a reminder, k-th largest value of the array b is defined as following:

  * Sort the array in the non-increasing order, return k-th element from it. 



For example, the second largest element in array [0, 1, 0, 1] is 1, as after sorting in non-increasing order it becomes [1, 1, 0, 0], and the second element in this array is equal to 1.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 10^5) — the length of the given array and the number of queries.

The second line contains n integers a_1, a_2, a_3, ..., a_n (0 ≤ a_i ≤ 1) — elements of the initial array.

Each of the following q lines contains two integers. The first integer is t (1 ≤ t ≤ 2) — the type of query. 

  * If t = 1 the second integer is x (1 ≤ x ≤ n) — the position of the modified number. You have to assign to a_x the value 1 - a_x.
  * If t = 2 the second integer is k (1 ≤ k ≤ n) — you need to print the k-th largest value of the array.



It's guaranteed that there will be at least one query of the second type (satisfying t = 2).

Output

For each query of the second type, print a single integer — the answer to the query.

Example

Input


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


Output


1
0
1
0

Note

Initially a = [1, 1, 0, 1, 0].

The first operation is printing the third largest value, which is 1.

The second operation is assigning a_2 the value 0, a becomes [1, 0, 0, 1, 0].

The third operation is printing the third largest value, it is 0.

The fourth operation is printing the first largest value, it is 1.

The last operation is printing the fifth largest value, it is 0.

### Response

```cpp
/*  
    BISMILLAHIR RAHMANIR RAHIM
    NAME: Wasi Ur Rahman
    EMAIL: wasiurrahaman247@gmail.com
    FROM RMSTU
*/
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ll                     long long
#define boost                  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(v)                 v.begin(),v.end()
#define revall(v)              v.rbegin(),v.rend()
#define gcd(a,b)                __gcd(a,b)
#define lcm(a,b)               (a*b)/gcd(a,b)
#define pb                      push_back
#define eb                     emplace_back
#define mk                     make_pair
#define F                      first
#define S                      second
#define pi                     acos(-1.0)
#define maxv(v)                *max_element(all(v))
#define minv(v)                *min_element(all(v))
#define countv(v,a)             count(all(v),a)
#define cntone(x)             __builtin_popcountll(x) // number of ones
#define cntzero(x)             __builtin_ctzll(x) // number of zeros
#define rep(i, l, r)           for(long long i = l; i<r; i++)
#define SUM                     accumulate
#define toint(a)                atoi(a.c_str())
#define read                    freopen("input.txt","r",stdin)
#define write                   freopen("output.txt","w",stdout)
#define Unique(c)               (c).resize(unique(all(c))-(c).begin())
#define sp(a)                   fixed<<setprecision(a)
#define printv(container)       for(auto it:container) cout << it << " ";cout << endl
#define vll                     vector <ll>
#define cases(i)                cout << "Case " << i << ":"
#define yes                     cout << "YES" << endl
#define no                      cout << "NO" << endl
#define rand(V)                random_shuffle(all(V))
#define lb(a,X)                lower_bound(all(a),X)-a.begin()
#define ub(a,X)                upper_bound(all(a),X)-a.begin()
#define Testcases               ll t;cin >> t;while(t--)
using namespace std;



/*************************************
*          DEBUGGING SECTION         *
**************************************/
template<typename T>void showSTL(T H);template<typename T,typename V>void showSTL(pair<T,V> H);
template<typename T>void showSTL(priority_queue<T> H);template<typename T>void showSTL(stack<T> H);
template<typename T,typename V>void showSTL(map<T,V> H);
template<typename T,typename V>void showSTL(multimap<T,V> H);template<typename T>void showSTL(vector<T> H);
template<typename T>void showSTL(set<T> H);template<typename T>void showSTL(multiset<T> H);
template<typename T>void showSTL(list<T> H);void showSTL(char *H);
template<typename T>void showSTL(deque<T> H);template<typename T>void showSTL(queue<T> H);
template<typename T>void showSTL(T H){stringstream ss;ss<<H;cerr<<ss.str();}
template<typename T,typename V>void showSTL(pair<T,V> H){cerr<<"(";showSTL(H.first);cerr<<"=>";showSTL(H.second);cerr<<")";}
template<typename T>void showSTL(priority_queue<T> H){cerr<<endl;while(!H.empty()){cerr<<H.top()<<endl;H.pop();}cerr<<endl;}
template<typename T>void showSTL(stack<T> H){cerr<<endl;while(!H.empty()){cerr<<H.top()<<endl;H.pop();}}
template<typename T,typename V>void showSTL(map<T,V> H){cerr<<"[ ";for(auto val:H){showSTL(val);cerr<<" ";}cerr<<"]";}
template<typename T,typename V>void showSTL(multimap<T,V> H){cerr<<"[ ";for(auto val:H){showSTL(val);cerr<<" ";}cerr<<"]";}
template<typename T>void showSTL(vector<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(set<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(multiset<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(list<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
void showSTL(char *H){for(int i=0;i<strlen(H);i++){showSTL(H[i]);};}
template<typename T>void showSTL(deque<T> H){cerr<<"[ ";for(auto val : H){showSTL(val);cerr<<' ';}cerr<<"]";}
template<typename T>void showSTL(queue<T> H){cerr<<"[ ";while(!H.empty()){showSTL(H.front());cerr<<' ';H.pop();}cerr<<"]";}
vector<string>vec_spltr(string s){s+=',';vector<string>res;while(!s.empty())
res.push_back(s.substr(0, s.find(','))),s=s.substr(s.find(',')+1);return res;}
void dbg_out(vector<string>__attribute__((unused))args,__attribute__((unused))int idx,__attribute__((unused))int LINE_NUM)
{cerr<<endl;}template<typename Head,typename... Tail>
void dbg_out ( vector <string> args, int idx, int LINE_NUM, Head H, Tail... T)
{if(idx>0)cerr<<", ";else cerr << "Line(" << LINE_NUM << "):";
cerr<<" "<<args[idx]<<" = ";showSTL(H);dbg_out(args,idx+1,LINE_NUM, T...);}
#define debug(...) dbg_out(vec_spltr(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)

     /*   CHANGE VALUE OF MOD HERE   */
#define MOD 1000000007
const int N = 1000000;

         /*    MODULAR ARITHMETICS   */
ll add(ll a,ll b,ll mod){a += b;return ((a >= mod) ? a - mod : a);}
ll sub(ll a,ll b,ll mod){a -= b;return ((a < 0) ? a + mod : a);}
ll mult(ll a,ll b,ll mod){ll ans = (a%mod)*(b%mod);if(ans >= mod)ans %= mod;return ans;}
ll bigmod(ll x,ll n,ll mod){if(n == 0)return 1;ll ans = bigmod(x,n/2,mod);ans = mult(ans,ans,mod);if(n & 1) ans = mult(x,n,mod);return ans;}


        /*    CUSTOM FUNCTIONS   */
bool isPowerOfTwo (ll x) {return x && (!(x&(x-1)));}
bool isPerfectSquare(long double x){long double sr = sqrt(x);return ((sr - floor(sr)) == 0);}
ll digNO(ll num){  return floor(log10(num)) + 1; }
int findSqrt(int n) { int lo = 0, hi = n; while (lo <= hi) { int mid = (lo + hi) / 2; if (mid * mid <= n) lo = mid + 1; else hi = mid - 1; }return lo - 1;}
ll fib(ll n){double phi = (1+sqrt(5))/2;return round(pow(phi,n)/sqrt(5));}
ll count_N_in_Fact(ll n,ll k){ll res = 0,sum = 0;for(ll i = k;;i*=k){res = n/i;if(res == 0)break;sum += res;}return sum;}
string v2s(vll &A){ll Z=A.size();string S(Z,' ');rep(i,0,Z)S[i]=A[i]+'0';return S;}
bool isPrime(ll n) {if (n <= 1) return false;if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false; for (ll i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
void solve();
int main() {
    boost;
    //Testcases
        solve();
    return 0;
}
void solve(){
    ll n,q;
    cin >> n >> q;
    vector<ll> v;ll one = 0,zero = 0;
    for(ll i = 0;i<n;i++)
    {
        ll x;
        cin >> x;
        v.pb(x);
        if(x == 1)
            one++;
        else zero++;
    }vector<pair<ll,ll>> vis;
    while(q--)
    {
        ll a,b;
        cin >> a >> b;
        vis.pb({a,b});
    }
    for(ll i = 0;i<vis.size();i++)
    {
        if(vis[i].F == 1)
        {
            ll x = vis[i].S;
            if(v[x-1] == 1)
            {
                v[x-1] = 0;
                zero++;one--;
            }else{
                v[x-1] = 1;
                one++;zero--;
            }
        }else{
            if(vis[i].S > one)
                cout << 0 << endl;
            else cout << 1 << endl;
        }
    }
}
```