给定一个长度为 $k$ 的整数序列 $A = a_1, a_2, \dots, a_k$，你可以将其划分为若干个非空的连续子数组，使得每个元素恰好属于一个子数组。对于每个子数组，我们计算其元素之和。设 $p$ 为和为奇数的子数组个数，$q$ 为和为偶数的子数组个数。

你需要回答关于该序列的 $m$ 个询问。每个询问由一个整数 $r$ 表示，你需要分别求出在 $p + q = r$ 的条件下，$p$ 和 $q$ 的最大可能值。

由于序列 $A$ 可能很长，我们采用游程编码（run-length encoding）来描述它。更正式地说，给定 $n$ 对整数 $(v_1, l_1), (v_2, l_2), \dots, (v_n, l_n)$，序列 $A$ 的生成方式如下：从空序列开始，首先在序列末尾追加 $l_1$ 个 $v_1$，然后追加 $l_2$ 个 $v_2$，以此类推，最后追加 $l_n$ 个 $v_n$。关于示例的解释请参考下文。

输入格式

每个测试文件中仅包含一组测试数据。

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2 \times 10^5$)，分别表示序列游程编码的长度和询问次数。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $v_i$ 和 $l_i$ ($1 \le v_i, l_i \le 10^9$)。因此，序列 $A$ 的长度可以计算为 $k = \sum_{i=1}^n l_i$。保证对于所有 $1 \le i < n$，都有 $v_i \neq v_{i+1}$。

接下来的 $m$ 行，第 $i$ 行包含一个整数 $r_i$ ($1 \le r_i \le k$)，表示第 $i$ 个询问。

输出格式

对于每个询问，输出一行，包含两个由空格分隔的整数，分别表示在 $p + q = r$ 的条件下，$p$ 和 $q$ 的最大可能值。

样例

输入 1

3 6
5 3
2 2
7 1
1
2
3
4
5
6

输出 1

0 1
2 2
2 1
4 2
4 3
4 2

说明

对于样例测试数据，$A = 5, 5, 5, 2, 2, 7$。

对于第二个询问，我们需要将序列划分为 2 个连续子数组。

• 为了最大化和为奇数的子数组个数，我们可以将 $A$ 划分为 $5, 5, 5 \mid 2, 2, 7$。两个子数组的和均为奇数，因此 $p$ 的最大可能值为 2。
• 为了最大化和为偶数的子数组个数，我们可以将 $A$ 划分为 $5, 5 \mid 5, 2, 2, 7$。两个子数组的和均为偶数，因此 $q$ 的最大可能值为 2。

对于第五个询问，我们需要将序列划分为 5 个连续子数组。

• 为了最大化和为奇数的子数组个数，我们可以将 $A$ 划分为 $5 \mid 5 \mid 5 \mid 2, 2 \mid 7$，其中有 4 个子数组的和为奇数，因此 $p$ 的最大可能值为 4。
• 为了最大化和为偶数的子数组个数，我们可以将 $A$ 划分为 $5, 5 \mid 5 \mid 2 \mid 2 \mid 7$，其中有 3 个子数组的和为偶数，因此 $q$ 的最大可能值为 3。