#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<pll,pll> ppp;
typedef vector<ll> vll;
typedef vector<pll> vp;
typedef priority_queue<pll,vp,greater<pll> > pqpll;
typedef priority_queue<ll, vll, greater<ll> > pqll;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second
#define EPS 1e-10
#define ALL(a) (a.begin(), a.end())

template<typename T>
ll sz(vector<T> &vec){ return (ll)vec.size(); }
template<typename T>
ll sz(priority_queue<T, vector<T> > &pq) {return (ll)pq.size(); }
template<typename T>
ll sz(priority_queue<T, vector<T>, greater<T> > &pq) {return (ll)pq.size(); }
ll sz(string &s) {return (ll)s.size(); } 
ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b; }
bool checkindex(ll i,ll n){ return (i < n && i >= 0); }
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

#define SEG_LEN (1 << 19)

ll seg[SEG_LEN*2];

void add(ll ind,ll v){
    ind += SEG_LEN;
    seg[ind] ^= v;
    while(1){
        ind /= 2;
        if(ind <= 0) break;
        seg[ind] = seg[ind*2] ^ seg[ind*2+1];
    }
    return;
}

ll sum(ll l, ll r){
    l += SEG_LEN; r += SEG_LEN;
    ll res = 0;
    while(l < r){
        if(l % 2 == 1){
            res ^= seg[l];
            l++;
        }
        l /= 2;
        
        if(r % 2 == 1){
            res ^= seg[r-1];
            r--;
        }
        r /= 2;
    }
    return res;
}

int main(){
    ll n,q;
    cin >> n >> q;
    vll a(n);
    rep(i,0,n) cin >> a[i];
    rep(i,0,n) add(i+1,a[i]);

    ll t,x,y;
    rep(i,0,q){
        cin >> t >> x >> y;
        if(t == 1){
            add(x,y);
        }
        else{
            cout << sum(x,y+1) << endl;
        }
    }
}



#include <bits/stdc++.h>
using namespace std;

int main() {
	long long N, Q; cin >> N >> Q;
	vector<long long> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];

	vector<pair<long long, long long>> vec;
	for (int i = 0; i < N; i++) {
		vec.emplace_back(A[i], i);
	}
	sort(vec.begin(), vec.end());

	for (int i = 0; i < Q; i++) {
		long long K; cin >> K;
		long long left = 0, right = 1100000000000000000;
		while (right - left > 1) {
			long long mid = left + (right - left) / 2;
			long long left_ = -1, right_ = N;
			bool flag = false;
			while (right_ - left_ > 1) {
				long long mid_ = left_ + (right_ - left_) / 2;
				if (A[mid_] > mid) right_ = mid_;
				else if (A[mid_] < mid) left_ = mid_;
				else {
					flag = true;
					right_ = mid_; left_ = mid_;
				}
			}
			if (!flag) {
				if (right_ + K > mid) left = mid;
				else right = mid;
			}
			else {
				if (right_ + K >= mid) left = mid;
				else right = mid;
			}
		}
		cout << right << endl;
	}
}