D. Odd and Even
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an integer sequence $$$A = a_1, a_2, \cdots, a_k$$$ of length $$$k$$$, you can split it into several non-empty contiguous subarrays such that each element belongs to exactly one subarray. For each subarray, we calculate the sum of its elements. Let $$$p$$$ be the number of subarrays with an odd sum, and $$$q$$$ be the number of subarrays with an even sum.

You need to answer $$$m$$$ queries about this sequence. Each query is denoted as an integer $$$r$$$, and you need to find the maximum possible values of $$$p$$$ and $$$q$$$ under the condition that $$$p + q = r$$$, respectively.

As sequence $$$A$$$ might be long, we'll describe it in run-length encoding. More formally, given $$$n$$$ pairs of integers $$$(v_1, l_1), (v_2, l_2), \cdots, (v_n, l_n)$$$, sequence $$$A$$$ is derived as follows: starting from an empty sequence, first append $$$v_1$$$ to the back of the sequence $$$l_1$$$ times, then append $$$v_2$$$ to the back of the sequence $$$l_2$$$ times, ..., finally append $$$v_n$$$ to the back of the sequence $$$l_n$$$ times. See the explanation of the sample test case below for an example.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \times 10^5$$$), indicating the length of the run-length encoding of the sequence, and the number of queries.

For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$v_i$$$ and $$$l_i$$$ ($$$1 \le v_i, l_i \le 10^9$$$). Therefore, the length of sequence $$$A$$$ can be calculated as $$$k = \sum\limits_{i = 1}^n l_i$$$. It is guaranteed that $$$v_i \ne v_{i + 1}$$$ for all $$$1 \le i \lt n$$$.

For the following $$$m$$$ lines, the $$$i$$$-th line contains an integer $$$r_i$$$ ($$$1 \le r_i \le k$$$), indicating the $$$i$$$-th query.

Output

For each query, output one line containing two integers separated by a space, indicating the maximum possible values of $$$p$$$ and $$$q$$$ under the condition that $$$p + q = r$$$, respectively.

Example
Input
3 6
5 3
2 2
7 1
1
2
3
4
5
6
Output
0 1
2 2
2 1
4 2
4 3
4 2
Note

For the sample test case, $$$A = 5, 5, 5, 2, 2, 7$$$.

For the second query, we need to split the sequence into $$$2$$$ contiguous subarrays.

  • To maximize the number of subarrays with odd sums, we can split $$$A$$$ into $$$5, 5, 5 \,|\, 2, 2, 7$$$. Both subarrays have odd sums, so the maximum possible $$$p$$$ is $$$2$$$.
  • To maximize the number of subarrays with even sums, we can split $$$A$$$ into $$$5, 5 \,|\, 5, 2, 2, 7$$$. Both subarrays have even sums, so the maximum possible $$$q$$$ is $$$2$$$.

For the fifth query, we need to split the sequence into $$$5$$$ contiguous subarrays.

  • To maximize the number of subarrays with odd sums, we can split $$$A$$$ into $$$5 \,|\, 5 \,|\, 5 \,|\, 2, 2 \,|\, 7$$$, where $$$4$$$ of them have odd sums, so the maximum possible $$$p$$$ is $$$4$$$.
  • To maximize the number of subarrays with even sums, we can split $$$A$$$ into $$$5, 5 \,|\, 5 \,|\, 2 \,|\, 2 \,|\, 7$$$, where $$$3$$$ of them have even sums, so the maximum possible $$$q$$$ is $$$3$$$.