403540: GYM101192 B Sum-and-sum

Little Lyosha has an array, which consists of n integers. Every day he selects a certain continuous segment of the array and carefully examines each of its subsegments. For every subsegment he calculates bitwise AND of its elements, adds the sum of all elements of the subsegment to it and then writes down the calculated value into his Notebook of Important Numbers. Note that numbers in the array can be negative, so when calculating bitwise AND one should use their absolute values. At the end of the day, after Lyosha has carefully examined all the subsegments, he looks through all the written values, takes the maximal number among them and then writes it down into his Notebook of Very Important Numbers. The Notebook of Very Important Numbers is naturally very important for Lyosha, so he wants to make sure that there are no errors. Help the little boy to check his notes.

The first line contains two integers n and m — the length of the array and the number of notes Little Lyosha wants to check. The second line contains n integers a_i — elements of the array. Then m lines follow. The i-th line contains integers l_i and r_i, which means that on the i-th day the boy played with segment [l_i, r_i] of the array.

Print m lines. On the i-th line print the number that Lyosha should have written in his notebook at the i-th day.

7 3
3 -3 3 -3 6 5 -3
2 4
3 7
2 6

6
15
15