You are given a sequence A[1], A[2] ... A[N]. (0 ≤ A[i] < 2³¹, 1 ≤ N ≤ 12000).

A query is defined as follows:

• Query(x, y) = Max { a[i] xor a[i+1] xor ... xor a[j] ; l ≤ i ≤ j ≤ r }.
• l = min ( ((x+lastans) mod N)+1, ((y+lastans) mod N)+1 ).
• r = max ( ((x+lastans) mod N)+1, ((y+lastans) mod N)+1 ).
• lastans[1] = 0 , lastans[i] = Query[i-1].

Given M queries, your program must output the results of these queries. (0 ≤ M ≤ 6000).

IMPORTANT : PROBLEM ENHANCED. ( I'M SO SORRY.. )

Input

• The first line of the input file contains 2 numbers : N M.
• In the second line, N numbers follow.
• M lines follow, where line i contains 2 numbers xi and yi.

Output

Your program should output the results of the M queries, one query per line.

Example

Input:
3 3
1 4 3
0 1
0 1
4 3

Output:
5
7
7