Polycarpus has a sequence, consisting of *n* non-negative integers: *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>.

Let's define function *f*(*l*, *r*) (*l*, *r* are integer, 1 ≤ *l* ≤ *r* ≤ *n*) for sequence *a* as an operation of bitwise OR of all the sequence elements with indexes from *l* to *r*. Formally: *f*(*l*, *r*) = *a*<sub class="lower-index">*l*</sub> | *a*<sub class="lower-index">*l* + 1</sub> | ...  | *a*<sub class="lower-index">*r*</sub>. 

Polycarpus took a piece of paper and wrote out the values of function *f*(*l*, *r*) for all *l*, *r* (*l*, *r* are integer, 1 ≤ *l* ≤ *r* ≤ *n*). Now he wants to know, how many distinct values he's got in the end. 

Help Polycarpus, count the number of distinct values of function *f*(*l*, *r*) for the given sequence *a*.

Expression *x* | *y* means applying the operation of bitwise OR to numbers *x* and *y*. This operation exists in all modern programming languages, for example, in language C++ and Java it is marked as "|", in Pascal — as "or".
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the number of elements of sequence *a*. The second line contains *n* space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the elements of sequence *a*.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define F(i) for(int i=1;i<=n;i++)
int bits[100100][31]={0};
int a[100100];
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	F(i)scanf("%d",&a[i]);
	F(k){
		for(int i=30;i>=0;i--){
			bits[k][i]=(a[k]&(1<<i))?1:0;
			bits[k][i]+=bits[k-1][i];
		}
	}
	for(int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		int len=r-l+1;
		int x=0;
		for(int i=30;i>=0;i--){
			int b0=len-(bits[r][i]-bits[l-1][i]);
			if(b0*2>len)x|=(1<<i);
		}
		printf("%d\n",x);
	}
	return 0;
}
