Thread Cutting

There are $N$ nails on the circumference of a circular board. They are numbered $1,2,\cdots,N$ in clockwise order.

A permutation $P_1,P_2,\cdots,P_N$ of $1,2,\cdots,N$ is given. A thread starts at nail $P_1$ and visits $P_2,P_3,\cdots,P_N$ in this order. The part of the thread between two consecutive nails is a taut straight segment.

Each query gives two integers $L,R$. Imagine cutting the thread and keeping only the part from $P_L$ through $P_R$. The remaining thread consists of the segments $P_LP_{L+1},P_{L+1}P_{L+2},\cdots,P_{R-1}P_R$.

Two distinct segments cross if their interiors have a common point. Determine whether the number of crossing pairs of segments in the remaining thread is odd.

• Two consecutive segments sharing a nail as an endpoint are not counted as crossing.
• If three or more segments meet at the same interior point, every crossing pair is counted separately.
• All queries are independent.

The input is given in the following format:

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

Each case is given in the following format:

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

For each test case, print the answers to its $Q$ queries in order, one per line.

Print 1 if the number of crossing pairs is odd, and print 0 otherwise.

• $1 \leq T \leq 100\,000$.
• $2 \leq N,Q \leq 200\,000$.
• $P_1,P_2,\cdots,P_N$ is a permutation of $1,2,\cdots,N$.
• $1 \leq L_i < R_i \leq N$ ($1 \leq i \leq Q$).
• The sum of $N$ over all test cases does not exceed $200\,000$.
• The sum of $Q$ over all test cases does not exceed $200\,000$.