Coin Toss Game

Younghee and Dongsu play a coin toss game. The game runs for $K$ rounds under these rules.

1. In one round each player tosses a coin once, and Younghee always tosses first.
2. A head scores 1 point and a tail scores nothing.
3. After every single toss the players check whether the result is already settled. If one player would stay below the opponent's current score even after getting a head on every toss they have left, the game stops right there, even in the middle of a round.

Let $M$ be Younghee's score and $N$ be Dongsu's score at the moment the game stops. Picking any two integers $M$ and $N$ between $0$ and $K$ does not give a pair that a game can actually produce. For $K = 2$, the nine pairs split like this.

Here is why $(M, N) = (0, 2)$ is impossible. Dongsu needs a head in both rounds to reach 2 points, so he already holds 1 point when the second round starts. Younghee has to toss a tail to stay at 0 points, and at that moment she has no tosses left, so she can never pass Dongsu. Rule 3 stops the game at 0 and 1, and Dongsu never tosses his second coin.

Given $M$ and $N$, decide whether the two numbers can be Younghee's and Dongsu's scores once the game has ended.

The first line has the number of rounds $K$ ($1 \le K \le 1000$).

The second line has the number of queries $C$ ($1 \le C \le 100000$).

Each of the next $C$ lines has two integers $M$ and $N$ separated by a space ($0 \le M, N \le K$).

Print $C$ lines. On the $i$-th line print 1 if the $M$ and $N$ of the $i$-th query can be the scores of Younghee and Dongsu once the game has ended, and 0 otherwise.