Beware of the potentially tight time limit.

After completing the tasks and checking the log, the crewmates have successfully determined the impostors and kicked them out of the spaceship. There are now only $N$ crewmates numbered from $1$ to $N$ inside the spaceship without imposters. However, some suspectful crewmates thought that there were still some impostors among them and suspect someone.

For the $i^{\text{th}}$ crewmate, if $A_i = -1$, he doesn’t suspect anyone to be an impostor. However, if $A_i \ge 1$, he suspects the $A_i^{\text{th}}$ crewmate to be an impostor. In this case, crewmate $i$ will vote crewmate $A_i$. Note that some crewmate might be so dumb that he suspects himself to be an imposter!

The game lasts for several rounds (see below for details), starting from round $1$. In each round, there is a voting section. If both crewmates $i$ and $A_i$ are both still in the spaceship, crewmate $i$ will vote crewmate $A_i$. After everyone votes, the crewmate who received highest number of votes will be kicked off the spaceship. If multiple crewmates received the same number of votes, the one with smaller crewmate number will be kicked off. If no person is being voted, the round will simply skip.

Please note that once a crewmate was kicked off, his vote will not be considered for further rounds. Moreover, each crewmate insists what he think. Therefore, each crewmate votes the same crewmate throughout all rounds.

You imagined $Q$ scenarios. For the $i^{\text{th}}$ scenario, you imagined you as the $Y_i^{\text{th}}$ crewmate. The game starts at round $1$ and ends of round $X_i$. Your task is to determine whether you, as the $Y_i^{\text{th}}$ crewmate, remains in the spaceship (i.e. didn't get kicked out) after round $X_i$. Note that everything is just your imagination. Therefore, after each scenario, all $N$ crewmates will recover into the spaceship and everything resets.

Input

The first line contains two integers $N$ and $Q$.

The second line contains $N$ integers $A_1, A_2, ...\ , A_N$.

For the next $Q$ lines, the $i^{th}$ line contains two integers $X_i$ and $Y_i$.

Output

Output $Q$ lines, the $i^{th}$ line denotes the answer to the $i^{th}$ scenario, which is either 1 if you remain in the spaceship or 0 if you do not.

Subtasks

For all test cases:

• $1 \le N \le 3 \times 10^6$
• $1 \le Q \le 5 \times 10^5$
• $1 \le A_i \le N$ or $A_i = -1$ for $1 \le i \le N$
• $1 \le X_i \le 10^9$ for $1 \le i \le Q$
• $1 \le Y_i \le N$ for $1 \le i \le Q$

Hints

As this problem involves large input/output, please add the following code inside int main() (before cin / cout) to improve I/O speed:

ios::sync_with_stdio(0);
cin.tie(0);

Additionally, avoid using endl in large test cases as it is slow. Instead, use \n.