A10234. 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·10^{4},\ 1<=m<=5·10^{3}$ ) — the size of the array and the number of the queries.

The second line contains $n$ integers $a_{i}$ ( $1<=a_{i}<=10^{6}$ ) — 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}$ .