剑桥大学的入学面试包含 $N$ 个任务，编号从 $1$ 到 $N$。Alex 现在就在现场，等待参加面试。刚刚结束面试的 Takahiro Wong 已经完成了所有任务。更准确地说，他在面试开始后的 $D_i$ 秒完成了第 $i$ 个问题。
已知 Alex 完成第 $i$ 个问题需要 $T_i$ 秒，Alex 向自己提出了 $M$ 个问题：$x$ $y$。对于每个问题，Alex 只考虑区间 $[x; y]$ 内的任务，他想知道是否能在 Takahiro Wong 之前完成这些区间内的所有任务。（Alex 可以以任何顺序完成区间 $[x; y]$ 内的任务）。
例如，假设 Alex 必须完成任务 $a$ 和 $b$（按此顺序）。他将在 $T_a$ 秒后完成任务 $a$，在 $T_a + T_b$ 秒后完成任务 $b$。如果 $T_a < D_a$ 且 $T_a + T_b < D_b$，则 Alex 将在 Takahiro Wong 之前完成这两个问题。
Takahiro Wong 和 Alex 的面试都从第 $0$ 秒开始。
请帮助 Alex 正确回答所有 $M$ 个问题。
输入格式
- 第一行包含 $N$ 和 $M$。 $N$ 为任务数量，$M$ 为问题数量。
- 接下来的 $N$ 行，每行包含 $T_i$ 和 $D_i$。 $T_i$ 为 Alex 完成第 $i$ 个问题所需的时间。 $D_i$ 为 Takahiro Wong 完成第 $i$ 个问题的时间（从面试开始算起）。
- 接下来的 $M$ 行，每行包含 $x$ 和 $y$，表示区间 $[x; y]$。
输出格式
输出包含 $M$ 行，即 $M$ 个问题的答案。 第 $i$ 行应包含： 如果 Alex 可以在 Takahiro Wong 之前完成区间 $[x; y]$ 内的所有任务，则输出 $1$； 否则输出 $0$。
数据范围
- $1 \le T_i < D_i \le 10^9$
- $D_i$ 的值不一定唯一（存在多个任务具有相同 $D_i$ 的情况）
- Alex 不能同时解决两个任务，但 Takahiro Wong 可以（$D_i$ 的值不一定唯一）。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 15 分 | $1 \le N, M \le 10$ |
| 2 | 25 分 | $1 \le N \times M \le 10^5$ |
| 3 | 15 分 | $1 \le N \le 10^3, 1 \le M \le 10^5$ |
| 4 | 45 分 | $1 \le N, M \le 10^5$ |
样例
输入 1
4 3 1 10 14 18 2 7 10 12 3 4 2 4 1 3
输出 1
0 0 1
说明
第三个问题涉及区间 $[1; 3]$： Alex 完成任务的方式有 6 种：$(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)$。 如果他按 $(1, 3, 2)$ 的顺序完成任务，我们需要满足以下关系： $T_1 < D_1, T_1 + T_3 < D_3$ 以及 $T_1 + T_3 + T_2 < D_2$。我们可以看到这些条件全部成立。 * 因为 Alex 找到了至少一种在 Takahiro Wong 之前完成所有问题的方法，所以第三个问题的答案是 $1$。