Tester_Catch_Me_If_You_Can

    #include <stdio.h>
    #include <iostream>
    #include <map>
    #include <vector>
    #include <utility>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    typedef long long int ll;
    typedef pair<ll, ll> ipair;
    #define mod 1000000007
    #define pb push_back
    #define mp make_pair
    #define ff first
    #define ss second
    #define sz size()
    #define ln length()
    #define rep(i,n) for(i=0;i<n;i++)
    #define fu(i,a,n) for(i=a;i<=n;i++)
    #define fd(i,n,a) for(i=n;i>=a;i--)
    #define all(a)  a.begin(),a.end()
    #define gi(n) scanf("%d",&n)
    #define gl(n) scanf("%lld",&n)
    #define pi(n) printf("%d",n)
    #define pl(n) printf("%lld",n);
    #define pp printf(" ")
    #define pn printf("\n")
    #define LN 31
    #define MAX 100005


    struct trie {
        trie *child[2];
        ll cnt;
        trie(ll c, trie *a, trie *b) {
            child[0] = a;
            child[1] = b;
            cnt = c;
        }
    };
    trie *null = new trie(0, NULL, NULL);
    ll arr[MAX];
    trie * root[MAX];
    trie *insert(trie *proot, ll val) {
        trie *nroot = new trie(0, null, null);
        trie *cur = nroot;
        ll i;
        fd(i, LN - 1, 0) {
            int ch = (val >> i)&1;
            cur->child[ch] = new trie(0, null, null);
            cur->child[1^ch] = proot->child[1^ch];
            cur = cur->child[ch];
            proot = proot->child[ch];
            cur->cnt = proot->cnt + 1;
        }
        return nroot;
    }
    ll queryRes(trie *a, trie *b, ll x, ll y) {
        ll ans = 0;
        ll i;
        fd(i, LN - 1, 0) {
            int ch = (x >> i)&1;
            int req = (y >> i)&1;
            if(!req) {
                ans = ans + a->child[1^ch]->cnt - b->child[1^ch]->cnt;
                a = a->child[ch];
                b = b->child[ch];
            }
            else {
                a = a->child[1^ch];
                b = b->child[1^ch];
            }
        }
        ans = ans + a->cnt - b->cnt;
        return ans;
    }


    int main() {
        null->child[0] = null->child[1] = null;
        root[0] = null;
        int t;
        t = 1;
        while(t--) {
            ll n, q;
            gl(n);
            gl(q);
            ll i, k;
            fu(i, 1, n) {
                gl(k);
                root[i] = insert(root[i - 1], k);
            }
            while(q--) {
                ll l, r, x, y;
                gl(l);
                gl(r);
                gl(x);
                gl(y);
                ll ans = queryRes(root[r], root[l - 1], x, y);
                pl(ans);
                pn;
            }
        }
        return 0;
    }