실 자르기

원형 판의 둘레에 $N$개의 못이 놓여 있다. 못에는 시계 방향으로 $1,2,\cdots,N$번이 붙어 있다. 못은 모두 원 위의 서로 다른 점이므로, 어떤 세 못도 한 직선 위에 있지 않다.

$1$부터 $N$까지의 순열 $P_1,P_2,\cdots,P_N$이 주어진다. 하나의 실이 못 $P_1$에서 시작하여 $P_2,P_3,\cdots,P_N$을 차례로 지난다. 연속한 두 못 사이의 실은 팽팽한 직선 선분이다.

각 질의에서는 두 정수 $L,R$이 주어진다. 실을 잘라 $P_L$부터 $P_R$까지의 부분만 남겼다고 생각하자. 남은 실은 선분 $P_LP_{L+1},P_{L+1}P_{L+2},\cdots,P_{R-1}P_R$로 이루어진다.

서로 다른 두 선분에 대하여, 두 선분의 내부(양 끝점을 제외한 부분)에 동시에 속하는 점이 하나라도 존재하면 두 선분이 교차한다고 한다. 남은 실에 포함된 선분 쌍 중 교차하는 쌍의 개수가 홀수인지 판별하여라.

• 연속한 두 선분이 같은 못을 끝점으로 공유하는 것은 교차로 세지 않는다. 그 공유점이 두 선분 모두의 끝점이기 때문이다.
• 어떤 못이 다른 선분의 내부에 놓이는 일은 없으며, 두 선분이 일부 구간을 공유하며 겹치는 일도 없다. 어떤 세 못도 한 직선 위에 있지 않기 때문이다.
• 세 개 이상의 선분이 같은 내부 점에서 만나는 경우에도 교차하는 선분 쌍을 각각 하나씩 센다.
• 남은 실에 선분이 하나 이하이면 선분 쌍이 존재하지 않으므로 답은 $0$이다.
• 모든 질의는 서로 독립적이다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ Q$ $P_1\ P_2\ \cdots\ P_N$ $L_1\ R_1$ $L_2\ R_2$ $\vdots$ $L_Q\ R_Q$

각 테스트 케이스에서 $Q$개의 질의에 대한 답을 순서대로 출력한다. 각 답은 한 줄에 출력한다.

교차하는 선분 쌍의 개수가 홀수이면 1, 짝수이면 0을 출력한다.

• $1 \leq T \leq 100\,000$.
• $2 \leq N,Q \leq 200\,000$.
• $P_1,P_2,\cdots,P_N$은 $1,2,\cdots,N$의 순열이다.
• $1 \leq L_i < R_i \leq N$ ($1 \leq i \leq Q$).
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $Q$의 합은 $200\,000$ 이하이다.