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 is given. A thread starts at nail and visits 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 .

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$

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$.
• is a permutation of .