You are given a permutation of length $n$ and $m$ queries. Each query asks for the number of inversions in a given range. The problem must be solved online.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ positive integers representing the permutation.

The following $m$ lines each contain two integers representing the query range.

This problem requires an online solution. For each query, the input numbers must be XORed with $lastans$. For the first query, $lastans = 0$.

Output

Output $m$ lines, each containing the answer to the corresponding query.

Constraints

$1\leq n,m\leq 10^5$.

We already have online algorithms with complexity better than $n^{1.5}$.

Examples

Input 1

4 1
1 4 2 3
2 4

Output 1

2