#include<bits/stdc++.h>
#define cps CLOCKS_PER_SEC

using namespace std ;

/// DATA TYPEs
#define mp make_pair
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<pii> vpii ;
typedef vector<pll> vpll ;

/// MEMBER FUNCTIONS
#define X first
#define Y second

/// CONSTANTS
#define M       1000000007
#define INF         1011111111
#define EPS         (double)1e-8
#define PI          3.14159265358979

/// INPUT ARRAYS
template<class T>
inline void getar(T a, int n, int m){ for (int i = 0; i < n; i++) for (int j = 0; j < m;++j) { scanf("%d", &a[i][j]); } }
inline void getar(int *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%d", a + ii); } }
inline void getar(pii *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("d", &a[ii].first, &a[ii].second); } }
inline void getar(ll *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%I64d", a + ii); } }
inline void getv( vi &a , int n ){ for(int ii = 0 ; ii < n ; ii++){ scanf("%d",&a[ii]) ; } }
inline void getv( vll &a , int n ){ for(int ii = 0 ; ii < n ; ii++){ scanf("%I64d",&a[ii]) ; } }
inline void getv(vpii &a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%d", &a[ii].first, &a[ii].second); } }
inline void getv(vpll &a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%I64d", &a[ii].first, &a[ii].second); } }
inline void getvv(vvi &a, int n, int m){ for (int i = 0; i < n; i++) for (int j = 0; j < m;++j) { scanf("%d", &a[i][j]); } }

/// OUTPUT
inline void printa( int *a , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%d " , a[ ii ] ); } }
inline void printa( ll *a , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%I64d " , a[ ii ] ); } }
inline void printv( vi &a , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%d " , a[ ii ] ); } }
inline void printv( vll &a , int n , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%I64d " , a[ ii ] ); } }

/// MAX AND MIN
inline ll max(ll a,ll b){return (a>b)?a:b;}
inline int max(int a,int b){return (a>b)?a:b;}
inline double max(double a,double b){return (a>b)?a:b;}
inline ll max(ll a,ll b,ll c){return max(a,max(b,c));}
inline int max(int a,int b,int c){return max(a,max(b,c));}
inline double max(double a,double b,double c){return max(a,max(b,c));}
inline ll min(ll a,ll b){return (a<b)?a:b;}
inline int min(int a,int b){return (a<b)?a:b;}
inline double min(double a,double b){return (a<b)?a:b;}
inline ll min(ll a,ll b,ll c){return min(a,min(b,c));}
inline int min(int a,int b,int c){return min(a,min(b,c));}
inline double min(double a,double b,double c){return min(a,min(b,c));}

///BASIC MATH OPERATIONS
#define sqrt(x) sqrt(1.0*(x))
inline ll pow(ll x,ll n){ll res=1;while(n){if(n&1)res*=x;x*=x;n>>=1;}return res;}
inline ll powmod(ll x,ll n, ll _mod){ll res=1;while(n){if(n&1)res=(res*x)%_mod;x=(x*x)%_mod;n>>=1;}return res;}
inline ll gcd(ll a,ll b){ll t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
inline int gcd(int a,int b){int t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
inline ll lcm(int a,int b){return a/gcd(a,b)*(ll)b;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll gcd(ll a,ll b,ll c){return gcd(gcd(a,b),c);}
inline int gcd(int a,int b,int c){return gcd(gcd(a,b),c);}
inline ll lcm(ll a,ll b,ll c){return lcm(lcm(a,b),c);}
inline ll lcm(int a,int b,int c){return lcm(lcm(a,b),(ll)c);}

/// BITWISE OPERATIONS
inline int bits_count(int v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
inline int bits_count(ll v){ ll t = v >> 32; ll p = (v & ((1LL << 32) - 1)); return bits_count(t) + bits_count(p); }
inline bool ispow2(int x){return (x!=0 && (x&(x-1))==0);}

/// SORTING
#define all(a)  a.begin(), a.end()
#define sor(a)  sort(all(a))
#define rsor(a) sort(all(a)); reverse(all(a));
#define INDEX(arr,ind)       (lower_bound(all(arr),ind)-arr.begin())
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define lb lower_bound
#define ub upper_bound

/// ESSCAPE SEQUENCE
const char nl = '\n';

//int some_primes[10] = {100271, 500179, 1000003, 2000227, 5000321}

void solve()
{
    /// IF THERE IS SINGLE TEST CASE MAKE t = 1 in main()

    int n , q ;
    cin >> n >> q ;

    vi a( n ) ;

    int zero = 0 , one = 0 ;

    for( int i = 0 ; i < n ; i++ )
    {
        cin >> a[ i ] ;
        if( a[ i ] == 0 )
            zero++ ;
        else
            one++ ;
    }

    while( q-- )
    {
        int x , k ;
        cin >> x >> k ;

        if( x == 1 )
        {
            --k ;
            if( a[ k ] == 0 )
                a[ k ] += 1 , zero-- , one++ ;
            else
                a[ k ] -= 1 , zero++ , one-- ;
        }
        else
        {
            if( one >= k )
                cout << "1\n" ;
            else
                cout << "0\n" ;
        }
    }
}

int main()
{
    clock_t clk = clock();
    cerr << "Hey P..\n";

    int t ;
    t = 1 ;

    while( t-- )
        solve() ;

    cerr << "Look at the sky.\n";
    cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';

    return 0 ;
}


### Prompt

Your challenge is to write a CPP solution to 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
#include<bits/stdc++.h>
#define cps CLOCKS_PER_SEC

using namespace std ;

/// DATA TYPEs
#define mp make_pair
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<pii> vpii ;
typedef vector<pll> vpll ;

/// MEMBER FUNCTIONS
#define X first
#define Y second

/// CONSTANTS
#define M       1000000007
#define INF         1011111111
#define EPS         (double)1e-8
#define PI          3.14159265358979

/// INPUT ARRAYS
template<class T>
inline void getar(T a, int n, int m){ for (int i = 0; i < n; i++) for (int j = 0; j < m;++j) { scanf("%d", &a[i][j]); } }
inline void getar(int *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%d", a + ii); } }
inline void getar(pii *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("d", &a[ii].first, &a[ii].second); } }
inline void getar(ll *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%I64d", a + ii); } }
inline void getv( vi &a , int n ){ for(int ii = 0 ; ii < n ; ii++){ scanf("%d",&a[ii]) ; } }
inline void getv( vll &a , int n ){ for(int ii = 0 ; ii < n ; ii++){ scanf("%I64d",&a[ii]) ; } }
inline void getv(vpii &a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%d", &a[ii].first, &a[ii].second); } }
inline void getv(vpll &a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%I64d", &a[ii].first, &a[ii].second); } }
inline void getvv(vvi &a, int n, int m){ for (int i = 0; i < n; i++) for (int j = 0; j < m;++j) { scanf("%d", &a[i][j]); } }

/// OUTPUT
inline void printa( int *a , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%d " , a[ ii ] ); } }
inline void printa( ll *a , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%I64d " , a[ ii ] ); } }
inline void printv( vi &a , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%d " , a[ ii ] ); } }
inline void printv( vll &a , int n , int i , int j ){ for(int ii=i ; ii <= j ; ii++){ printf("%I64d " , a[ ii ] ); } }

/// MAX AND MIN
inline ll max(ll a,ll b){return (a>b)?a:b;}
inline int max(int a,int b){return (a>b)?a:b;}
inline double max(double a,double b){return (a>b)?a:b;}
inline ll max(ll a,ll b,ll c){return max(a,max(b,c));}
inline int max(int a,int b,int c){return max(a,max(b,c));}
inline double max(double a,double b,double c){return max(a,max(b,c));}
inline ll min(ll a,ll b){return (a<b)?a:b;}
inline int min(int a,int b){return (a<b)?a:b;}
inline double min(double a,double b){return (a<b)?a:b;}
inline ll min(ll a,ll b,ll c){return min(a,min(b,c));}
inline int min(int a,int b,int c){return min(a,min(b,c));}
inline double min(double a,double b,double c){return min(a,min(b,c));}

///BASIC MATH OPERATIONS
#define sqrt(x) sqrt(1.0*(x))
inline ll pow(ll x,ll n){ll res=1;while(n){if(n&1)res*=x;x*=x;n>>=1;}return res;}
inline ll powmod(ll x,ll n, ll _mod){ll res=1;while(n){if(n&1)res=(res*x)%_mod;x=(x*x)%_mod;n>>=1;}return res;}
inline ll gcd(ll a,ll b){ll t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
inline int gcd(int a,int b){int t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
inline ll lcm(int a,int b){return a/gcd(a,b)*(ll)b;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll gcd(ll a,ll b,ll c){return gcd(gcd(a,b),c);}
inline int gcd(int a,int b,int c){return gcd(gcd(a,b),c);}
inline ll lcm(ll a,ll b,ll c){return lcm(lcm(a,b),c);}
inline ll lcm(int a,int b,int c){return lcm(lcm(a,b),(ll)c);}

/// BITWISE OPERATIONS
inline int bits_count(int v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
inline int bits_count(ll v){ ll t = v >> 32; ll p = (v & ((1LL << 32) - 1)); return bits_count(t) + bits_count(p); }
inline bool ispow2(int x){return (x!=0 && (x&(x-1))==0);}

/// SORTING
#define all(a)  a.begin(), a.end()
#define sor(a)  sort(all(a))
#define rsor(a) sort(all(a)); reverse(all(a));
#define INDEX(arr,ind)       (lower_bound(all(arr),ind)-arr.begin())
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define lb lower_bound
#define ub upper_bound

/// ESSCAPE SEQUENCE
const char nl = '\n';

//int some_primes[10] = {100271, 500179, 1000003, 2000227, 5000321}

void solve()
{
    /// IF THERE IS SINGLE TEST CASE MAKE t = 1 in main()

    int n , q ;
    cin >> n >> q ;

    vi a( n ) ;

    int zero = 0 , one = 0 ;

    for( int i = 0 ; i < n ; i++ )
    {
        cin >> a[ i ] ;
        if( a[ i ] == 0 )
            zero++ ;
        else
            one++ ;
    }

    while( q-- )
    {
        int x , k ;
        cin >> x >> k ;

        if( x == 1 )
        {
            --k ;
            if( a[ k ] == 0 )
                a[ k ] += 1 , zero-- , one++ ;
            else
                a[ k ] -= 1 , zero++ , one-- ;
        }
        else
        {
            if( one >= k )
                cout << "1\n" ;
            else
                cout << "0\n" ;
        }
    }
}

int main()
{
    clock_t clk = clock();
    cerr << "Hey P..\n";

    int t ;
    t = 1 ;

    while( t-- )
        solve() ;

    cerr << "Look at the sky.\n";
    cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';

    return 0 ;
}


```