D. Dance of Ferrets
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a circle drawn on the ground. The circle has $$$n$$$ equally spaced marks on its perimeter. The $$$i$$$-th mark is said to be adjacent to the $$$(i-1)$$$-th and $$$(i+1)$$$-th marks (if they exist). Marks $$$1$$$ and $$$n$$$ are adjacent as well.

$$$n$$$ ferrets numbered form $$$1$$$ to $$$n$$$ will perform a dance on this circle. Initially, the $$$i$$$-th ferret is standing on the $$$i$$$-th mark. They will dance for $$$2024!^{2024!}$$$ rounds. If a ferret is standing on mark $$$i$$$ at the beginning of a round, it will move to mark $$$p_i$$$ during that round. It is guaranteed that $$$[p_1, p_2, \dots, p_n]$$$ is a permutation.

Some pairs of ferrets are best friends and don't like to be too far from each other for a long time. For that reason, they want to know if they will be standing on adjacent marks at the beginning of any round. Write a program to answer $$$q$$$ queries and help the ferrets to know that. For each query, you are given two integers $$$a$$$ and $$$b$$$, and you must determine if ferrets $$$a$$$ and $$$b$$$ will stand on adjacent marks at the beginning of any round.

Input

The input contains multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) – the number of test cases. The description of each test case follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$ and $$$1 \leq q \leq 5 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots p_n$$$ ($$$1 \leq p_i \leq n$$$). It is guaranteed that $$$[p_1, p_2, \dots, p_n]$$$ forms a permutation.

The following $$$q$$$ lines contain two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq n$$$ and $$$a \neq b$$$).

It is guaranteed that the sum of $$$n$$$ over all the test cases does not exceeds $$$5 \cdot 10^5$$$, and that the sum of $$$q$$$ over all the test cases does not exceeds $$$5 \cdot 10^5$$$.

Output

Print a binary string of size $$$q$$$ for each test case, where the $$$i$$$-th character is '1' if the ferrets in the $$$i$$$-th query will stand on adjacent marks at the beginning of any round, or '0' otherwise.

Examples
Input
1
5 10
2 1 4 3 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output
1011101111
Input
2
2 1
1 2
1 2
2 1
2 1
1 2
Output
1
1