cambridge

The admission interview at the prestigious University of Cambridge consist of $N$ tasks, numbered from $1$ to $N$. Alex is there right now, waiting to attend the interview. Takahiro Wong, who has just finished his interview, solved all the tasks. More precisely, he solved the $i$-th problem after $D_i$ seconds from the beginning of the interview.

Knowing the fact that he can solve the $i$-th problem in $T_i$ seconds, Alex asks himself $M$ questions: $x \ y$. For every question, Alex will consider only the tasks from the interval $[x, y]$ and he wants to know whether he can solve each of these tasks before Takahiro Wong. (Alex can solve the tasks from the interval $[x, y]$ in any order).

For example, let’s consider that Alex has to solve the tasks $a$ and $b$ (in this order). He will finish task $a$ after $T_a$ seconds, and task $b$ after $T_a + T_b$ seconds. Alex will solve both problems before Takahiro Wong if $T_a < D_a$ and $T_a + T_b < D_b$.

Both Takahiro Wong and Alex will start their interviews at second $0$.

Task

Help Alex answer correctly to all $M$ questions.

Input data

• The first line of the standard input will contain $N$ and $M$.
  • $N$ - the number of tasks
  • $M$ - the number of questions.
• On the following $N$ lines, there will be $T_i$ and $D_i$.
  • $T_i$ - the time needed for Alex to solve the $i$-th problem
  • $D_i$ - the time (from the beginning of his interview) after Takahiro Wong will solve the $i$-th problem.
• On the following $M$ lines, there will be $x$ and $y$, representing the interval $[x, y]$.

Output data

The standard output will contain $M$ lines, the answers to the $M$ questions.

The $i$-th line will contain:

• $1$, if Alex cand solve all the tasks from the interval $[x,y]$ before Takahiro Wond
• $0$, otherwise.

Restrictions

• $1 \leq T_i < D_i \leq 10^9$
• The $D_i$ values are not distinct (there can be a value that appears multiple times)
• Alex can’t solve $2$ tasks in the same time, but Takahiro Wong can (The $D_i$ values are not distinct).

Example

stdin

4 3
1 10
14 18
2 7
10 12
3 4
2 4
1 3

stdout

0
0
1

Explanation

The $3$rd question refers to the interval $[1,3]$:

• There are $6$ ways Alex can solve the tasks: $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$, $(3,2,1)$.
• If he solves the tasks in the order $(1,3,2)$, we have to fulfill the following relations: $T_1 < D_1$, $T_1 + T_3 < D_3$ and $T_1 + T_3 + T_2 < D_2$. We can see that all of them are true.
• Because Alex found at least one way to solve all the problems before Takahiro Wong, the answer is $1$ for the third question.