#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <unordered_map>
// #include<multiset>
#include <climits>
#include<unordered_set>
#include <iterator>
#include<random>
using namespace std;
// #define LOCAL
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
typedef pair<int, LL> PIL;
const int N = 1005;
const int MOD = 1000000007;
int n, m;
int ans = INT_MAX;
const LL INF = 1e15;
vector<PLI>f;
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        int a, t;
        scanf("%d%d", &a, &t);
        if(i == 0){
            f.push_back({a,t});
        }else{
            if(f.back().second == t){
                if(t == 1){
                    f.back().first += a;
                }else if(t == 2){
                    f.back().first = max(1ll*a, f.back().first);
                }else{
                    f.back().first = min(1ll*a, f.back().first);
                }
            }else{
                f.push_back({a,t});
            }
        }
    }
    m = f.size();
    LL low = INF, high = -INF, bias = 0;
    for(int i = 0; i < m; ++i){
        auto p = f[i];
        if(p.second == 1){
            low += p.first;
            high += p.first;
            bias += p.first;
        }else if(p.second == 2){
            low = min(INF, max(p.first, low));
            high = max(high, p.first);
        }else{
            low = min(p.first, max(-INF, low));
            high = max(high, -INF);
        }
    }
    // cout << low << ' ' << bias << ' ' << high << endl;
    int q;
    scanf("%d", &q);
    while(q--){
        int x;
        scanf("%d", &x);
        LL res = x + bias;
        res = min(low, max(high, res));
        printf("%lld\n", res);
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll INF = 1000000000000000;
struct segment_tree{
    int n; vector<ll> seg;
    segment_tree(vector<ll> v){
        n = v.size(); seg.resize(2*n);
        for(int i=0;i<n;i++) seg[i + n] = v[i];
        for(int i=n - 1;i>0;i--) seg[i] = seg[i<<1]^seg[i<<1|1];
    }
    void update(int p,ll val){
        for(seg[p += n] ^= val;p>1;p>>=1) seg[p>>1] = seg[p]^seg[p^1];
    }
    ll query(int l,int r){
        ll res = 0;
        for(l += n,r += n; l<r;l>>=1,r>>=1){
            if(l&1) res ^= seg[l++];
            if(r&1) res ^= seg[--r];
        }
        return res;
    }
    void clear(){for(int i=0;i<2*n;i++) seg[i] = 0;}
};

int main(){
    int i,n,q; cin >> n >> q;
    vector<ll> v(n);
    for(i=0;i<n;i++) cin >> v[i];
    segment_tree seg(v);
    for(i=0;i<q;i++){
        ll t,x,y; cin >> t >> x >> y;
        if(t==1){
            x--;
            seg.update(x,y);
        }
        if(t==2){
            x--;
            cout << seg.query(x,y) << "\n";
        }
    }
}