F. Xors on Segmentstime limit per test10 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given an array with n integers ai and m queries. Each query is described by two integers (lj, rj).Let's define the function . The function is defined for only u ≤ v.For each query print the maximal value of the function f(ax, ay) over all lj ≤ x, y ≤ rj,  ax ≤ ay.InputThe 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 ai (1 ≤ ai ≤ 106) — the elements of the array a.Each of the next m lines contains two integers lj, rj (1 ≤ lj ≤ rj ≤ n) – the parameters of the j-th query.OutputFor each query print the value aj on a separate line — the maximal value of the function f(ax, ay) over all lj ≤ x, y ≤ rj,  ax ≤ ay.ExamplesInput6 31 2 3 4 5 61 62 53 4Output777Input1 111 1Output1Input6 2010 21312 2314 214 1 3221 11 21 31 41 51 62 22 32 42 52 63 43 53 64 44 54 65 55 66 6Output10213132131321313213132131321312213132131321313213132314231523152142153231323322
Input6 31 2 3 4 5 61 62 53 4
Output777
['data structures', 'strings', 'trees', '*2800']