#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

template<typename T, int NUM> class SyntaxRangeParser {
private:
    class segtree {
    private:
        int opr, size;
        const SyntaxRangeParser* obj;
        vector<T> val;
    public:
        void init(const int opr_, const SyntaxRangeParser* obj_){
            obj = obj_, opr = opr_;
            size = 1;
            while(size < obj->n){
                size *= 2;
            }
            val.resize(2 * size, obj->ie[opr]);
        }
        void update(int k, const T a) {
        	val[k+=obj->n] = a;
        	while(k >>= 1){
        		val[k] = obj->func[opr](val[2 * k], val[2 * k + 1]);
        	}
        }
        T query(int a, int b) {
            T res1 = obj->ie[opr], res2 = obj->ie[opr];
            a += obj->n, b += obj->n;
            while(a != b){
                if(a % 2) res1 = obj->func[opr](res1, val[a++]);
                if(b % 2) res2 = obj->func[opr](res2, val[--b]);
                a >>= 1, b >>= 1;
            }
            return obj->func[opr](res1, res2);
        }
    };
    using pti = pair<T, int>;
    string s;
    int n;
    T ie[NUM];
    map<char, int> optoi;
    function<T(T, T)> func[NUM];
    vector<int> opr_id[NUM], st[NUM - 1], ed[NUM - 1], num_id;
    int opr_cnt[NUM], num_cnt;
    segtree sg[NUM];
    pti factor(const int l, const int r) {
        num_cnt++;
        T res = 0;
        for(int i = l; i < r; i++){
            res = res * 10 + s[i] - '0';
            num_id[i] = num_cnt;
        }
        return make_pair(res, num_cnt);
    }
    pti term(const int opr, const int l, const int r) {
        if(opr < 0) return factor(l, r);
        opr_cnt[opr]++;
        int pos = l;
        bool flag = true;
        T res = ie[opr];
        for(int i = l; i < r; i++){
            if(optoi[s[i]] == opr + 1){
                pti p = term(opr - 1, pos, i);
                pos = i + 1;
                sg[opr].update(p.second, p.first);
                res = func[opr](res, p.first);
                opr_id[opr][p.second] = opr_cnt[opr];
                if(flag) flag = false, st[opr][opr_cnt[opr]] = p.second;
            }
        }
        pti p = term(opr - 1, pos, r);
        sg[opr].update(p.second, p.first);
        res = func[opr](res, p.first);
        opr_id[opr][p.second] = opr_cnt[opr];
        if(flag) st[opr][opr_cnt[opr]] = p.second;
        ed[opr][opr_cnt[opr]] = p.second + 1;
        return make_pair(res, opr_cnt[opr]);
    }
    pti expr(const int l, const int r) {
        opr_cnt[NUM - 1]++;
        int pos = l;
        T res = ie[NUM - 1];
        for(int i = l; i < r; i++){
            if(optoi[s[i]] == NUM){
                pti p = term(NUM - 2, pos, i);
                pos = i + 1;
                sg[NUM - 1].update(p.second, p.first);
                res = func[NUM - 1](res, p.first);
                opr_id[NUM - 1][p.second] = opr_cnt[NUM - 1];
            }
        }
        pti p = term(NUM - 2, pos, r);
        sg[NUM - 1].update(p.second, p.first);
        res = func[NUM - 1](res, p.first);
        opr_id[NUM - 1][p.second] = opr_cnt[NUM - 1];
        return make_pair(res, opr_cnt[NUM - 1]);
    }
    T number(const int l, const int r){
        T res = 0;
        int pos = l;
        while(pos < r && isdigit(s[pos])){
            res = res * 10 + s[pos++] - '0';
        }
        return res;
    }
    T number_rev(const int l, const int r){
        T res = 0, dig = 1;
        int pos = r-1;
        while(l <= pos && isdigit(s[pos])){
            res += (s[pos--] - '0') * dig, dig *= 10;
        }
        return res;
    }
    void init(){
        func[0] = [&](T x, T y){ return x ^ y; }, optoi['^'] = 1, ie[0] = 0;
        func[1] = [&](T x, T y){ return x & y; }, optoi['&'] = 2, ie[1] = numeric_limits<T>::max();
        func[2] = [&](T x, T y){ return x | y; }, optoi['|'] = 3, ie[2] = 0;
    }
public:
    SyntaxRangeParser(string& s_) : s(s_), n(len(s_)), num_id(n), opr_cnt{}, num_cnt(0){
        rep(i, NUM) sg[i].init(i, this), opr_id[i].resize(n);
        rep(i, NUM - 1) st[i].resize(n), ed[i].resize(n);
        init();
        expr(0, n);
    }
    T query(const int l, const int r) {
        T lnum = number(l, n), rnum = number_rev(0, r);
        int lpre = num_id[l], rpre = num_id[r - 1];
        if(lpre == rpre) return number(l, r);
        for(int i = 0; i < NUM; i++){
            int lnow = opr_id[i][lpre], rnow = opr_id[i][rpre];
            if(lnow == rnow) return func[i](func[i](lnum, sg[i].query(lpre + 1, rpre)), rnum);
            if(i == NUM - 1) break;
            lnum = func[i](lnum, sg[i].query(lpre + 1, ed[i][lnow]));
            rnum = func[i](sg[i].query(st[i][rnow], rpre), rnum);
            lpre = lnow, rpre = rnow;
        }
        return -1;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string s;
    cin >> s;
    SyntaxRangeParser<int, 3> srp(s);
    int q;
    cin >> q;
    rep(i,q){
        int l,r;
        cin >> l >> r;
        ++r;
        cout << srp.query(l, r) << "\n";
    }
    return 0;
}


### Prompt

Please formulate a cpp solution to the following problem:

problem

Given the formula $ S $ of length $ N $. The formula is in the format shown in BNF below.


<expr> :: = <number> | <expr> <op> <expr>

<op> :: = ‘^’ | ‘&’ | ‘|’



<number> represents an integer greater than or equal to $ 0 $ and less than or equal to $ 2 ^ {31} -1 $.

The operators ‘^’ ‘&’ ‘|’ represent exclusive OR, AND, and OR, respectively. The precedence of operators is as follows.

High ‘^’> ‘&’> ‘|’ Low

$ Q $ intervals $ [i, j] $ are given. Output the calculation result of $ S_i, \ dots, S_j $.

It is guaranteed that the formulas $ S_i, \ dots, S_j $ are in the format shown by the above BNF. Also, the formula does not contain zero-padded values.



output

Output the calculation result of $ S_i, \ dots, S_j $. Also, output a line break at the end.

Example

Input

7
9^2&1|2
4
0 6
0 2
2 6
4 4


Output

3
11
2
1

### Response

```cpp
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

template<typename T, int NUM> class SyntaxRangeParser {
private:
    class segtree {
    private:
        int opr, size;
        const SyntaxRangeParser* obj;
        vector<T> val;
    public:
        void init(const int opr_, const SyntaxRangeParser* obj_){
            obj = obj_, opr = opr_;
            size = 1;
            while(size < obj->n){
                size *= 2;
            }
            val.resize(2 * size, obj->ie[opr]);
        }
        void update(int k, const T a) {
        	val[k+=obj->n] = a;
        	while(k >>= 1){
        		val[k] = obj->func[opr](val[2 * k], val[2 * k + 1]);
        	}
        }
        T query(int a, int b) {
            T res1 = obj->ie[opr], res2 = obj->ie[opr];
            a += obj->n, b += obj->n;
            while(a != b){
                if(a % 2) res1 = obj->func[opr](res1, val[a++]);
                if(b % 2) res2 = obj->func[opr](res2, val[--b]);
                a >>= 1, b >>= 1;
            }
            return obj->func[opr](res1, res2);
        }
    };
    using pti = pair<T, int>;
    string s;
    int n;
    T ie[NUM];
    map<char, int> optoi;
    function<T(T, T)> func[NUM];
    vector<int> opr_id[NUM], st[NUM - 1], ed[NUM - 1], num_id;
    int opr_cnt[NUM], num_cnt;
    segtree sg[NUM];
    pti factor(const int l, const int r) {
        num_cnt++;
        T res = 0;
        for(int i = l; i < r; i++){
            res = res * 10 + s[i] - '0';
            num_id[i] = num_cnt;
        }
        return make_pair(res, num_cnt);
    }
    pti term(const int opr, const int l, const int r) {
        if(opr < 0) return factor(l, r);
        opr_cnt[opr]++;
        int pos = l;
        bool flag = true;
        T res = ie[opr];
        for(int i = l; i < r; i++){
            if(optoi[s[i]] == opr + 1){
                pti p = term(opr - 1, pos, i);
                pos = i + 1;
                sg[opr].update(p.second, p.first);
                res = func[opr](res, p.first);
                opr_id[opr][p.second] = opr_cnt[opr];
                if(flag) flag = false, st[opr][opr_cnt[opr]] = p.second;
            }
        }
        pti p = term(opr - 1, pos, r);
        sg[opr].update(p.second, p.first);
        res = func[opr](res, p.first);
        opr_id[opr][p.second] = opr_cnt[opr];
        if(flag) st[opr][opr_cnt[opr]] = p.second;
        ed[opr][opr_cnt[opr]] = p.second + 1;
        return make_pair(res, opr_cnt[opr]);
    }
    pti expr(const int l, const int r) {
        opr_cnt[NUM - 1]++;
        int pos = l;
        T res = ie[NUM - 1];
        for(int i = l; i < r; i++){
            if(optoi[s[i]] == NUM){
                pti p = term(NUM - 2, pos, i);
                pos = i + 1;
                sg[NUM - 1].update(p.second, p.first);
                res = func[NUM - 1](res, p.first);
                opr_id[NUM - 1][p.second] = opr_cnt[NUM - 1];
            }
        }
        pti p = term(NUM - 2, pos, r);
        sg[NUM - 1].update(p.second, p.first);
        res = func[NUM - 1](res, p.first);
        opr_id[NUM - 1][p.second] = opr_cnt[NUM - 1];
        return make_pair(res, opr_cnt[NUM - 1]);
    }
    T number(const int l, const int r){
        T res = 0;
        int pos = l;
        while(pos < r && isdigit(s[pos])){
            res = res * 10 + s[pos++] - '0';
        }
        return res;
    }
    T number_rev(const int l, const int r){
        T res = 0, dig = 1;
        int pos = r-1;
        while(l <= pos && isdigit(s[pos])){
            res += (s[pos--] - '0') * dig, dig *= 10;
        }
        return res;
    }
    void init(){
        func[0] = [&](T x, T y){ return x ^ y; }, optoi['^'] = 1, ie[0] = 0;
        func[1] = [&](T x, T y){ return x & y; }, optoi['&'] = 2, ie[1] = numeric_limits<T>::max();
        func[2] = [&](T x, T y){ return x | y; }, optoi['|'] = 3, ie[2] = 0;
    }
public:
    SyntaxRangeParser(string& s_) : s(s_), n(len(s_)), num_id(n), opr_cnt{}, num_cnt(0){
        rep(i, NUM) sg[i].init(i, this), opr_id[i].resize(n);
        rep(i, NUM - 1) st[i].resize(n), ed[i].resize(n);
        init();
        expr(0, n);
    }
    T query(const int l, const int r) {
        T lnum = number(l, n), rnum = number_rev(0, r);
        int lpre = num_id[l], rpre = num_id[r - 1];
        if(lpre == rpre) return number(l, r);
        for(int i = 0; i < NUM; i++){
            int lnow = opr_id[i][lpre], rnow = opr_id[i][rpre];
            if(lnow == rnow) return func[i](func[i](lnum, sg[i].query(lpre + 1, rpre)), rnum);
            if(i == NUM - 1) break;
            lnum = func[i](lnum, sg[i].query(lpre + 1, ed[i][lnow]));
            rnum = func[i](sg[i].query(st[i][rnow], rpre), rnum);
            lpre = lnow, rpre = rnow;
        }
        return -1;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string s;
    cin >> s;
    SyntaxRangeParser<int, 3> srp(s);
    int q;
    cin >> q;
    rep(i,q){
        int l,r;
        cin >> l >> r;
        ++r;
        cout << srp.query(l, r) << "\n";
    }
    return 0;
}


```