Description: You 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 $$f(u,v) = u \oplus (u+1) \oplus \ldots \oplus v$$. 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. Input Format: 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 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. Output Format: For 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. Note: None