카드 게임

Randias는 카드 게임을 하고 있다. 각 카드에는 숫자가 적혀 있다. 숫자가 $a_{1}, a_{2}, \ldots, a_{m}$인 카드들에 대해 Randias는 다음과 같이 게임을 진행한다.

처음에 모든 카드는 Randias의 손에 있다. Randias는 카드 순서열을 관리하며, 처음에는 비어 있다. $i$번째 연산에서 Randias는 $i$번째 카드(숫자 $a_{i}$)를 순서열의 끝에 놓는다. 그다음 다음과 같이 처리한다.

• 순서열에 숫자 $a_{i}$가 적힌 다른 카드가 없으면 $i$번째 연산이 끝난다.
• 그렇지 않으면, 순서열에서 숫자 $a_{i}$가 적힌 $j$번째 카드를 찾는다. Randias는 $j$번째 카드부터 방금 놓은 카드까지, 그 사이의 모든 카드를 두 끝을 포함해 가져간다.

예시로 $a = [2, 1, 3, 1, 2, 3]$이고 카드 순서열 $s = []$에서 시작한다고 하자. 1번 연산 후 $s = [2]$이다. 2번 연산 후 $s = [2, 1]$이다. 3번 연산 후 $s = [2, 1, 3]$이다. 4번 연산 후 $s = [2]$이다(카드 1, 3, 1이 제거된다). 5번 연산 후 $s = []$이다(카드 2, 2가 제거된다). 6번 연산 후 $s = [3]$이다.

Randias에게 $n$장의 카드 $a_{1}, a_{2}, \ldots, a_{n}$와 $q$개의 질의가 주어진다. $i$번째 질의는 쌍 $\ell_i, r_i$이다. 각 질의마다 초기 카드 목록이 $a_{\ell_i}, a_{\ell_i+1}, \ldots, a_{r_i}$일 때 연산이 끝나고 순서열에 남는 카드 수를 구한다. 질의는 온라인으로 답해야 하므로, 각 질의는 이전 질의의 답을 이용해 복호화한다.

첫 줄에 두 정수 $n$과 $q$가 주어진다 ($1 \le n, q \le 3 \cdot 10^5$).

다음 줄에 $n$개의 정수 $a_{1}, a_{2}, \ldots, a_{n}$이 주어진다 ($1 \le a_{i} \le n$).

이어지는 $q$개의 줄에는 각각 두 정수 $\ell'_i$와 $r'_i$가 주어진다 ($0 \le \ell'_i, r'_i \le 2n$). 직전 질의의 답을 $lastans$라 하자. 그러면 복호화된 질의는 $\ell_i = \ell'_i \oplus lastans$, $r_i = r'_i \oplus lastans$이다. 여기서 $\oplus$는 비트 단위 배타적 논리합이다. 복호화한 뒤에는 항상 $1 \le \ell_i \le r_i \le n$이다. 아직 답한 질의가 없으면 $lastans = 0$이다.

각 질의에 대해 답을 한 줄에 하나의 정수로 출력한다.

첫 번째 예시에서 질의의 구간은 $[5, 5]$, $[2, 5]$, $[1, 1]$, $[1, 4]$, $[3, 5]$이다.