Xors on Segments
You are given an array with *n* integers *a**i* and *m* queries. Each query is described by two integers (*l**j*,<=*r**j*).

Let's define the function . The function is defined for only *u*<=≤<=*v*.

For each query print the maximal value of the function *f*(*a**x*,<=*a**y*) over all *l**j*<=≤<=*x*,<=*y*<=≤<=*r**j*,<= *a**x*<=≤<=*a**y*.
The first line contains two integers *n*,<=*m* (1<=≤<=*n*<=≤<=5·104,<= 1<=≤<=*m*<=≤<=5·103) — the size of the array and the number of the queries.

The second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=106) — the elements of the array *a*.

Each of the next *m* lines contains two integers *l**j*,<=*r**j* (1<=≤<=*l**j*<=≤<=*r**j*<=≤<=*n*) – the parameters of the *j*-th query.
For each query print the value *a**j* on a separate line — the maximal value of the function *f*(*a**x*,<=*a**y*) over all *l**j*<=≤<=*x*,<=*y*<=≤<=*r**j*,<= *a**x*<=≤<=*a**y*.
none