長さ $k$ の整数列 $A = a_1, a_2, \dots, a_k$ が与えられます。この数列を、各要素がいずれか一つの部分配列に属するように、空でないいくつかの連続する部分配列に分割することができます。各部分配列について、その要素の和を計算します。和が奇数である部分配列の数を $p$、和が偶数である部分配列の数を $q$ とします。

この数列に関する $m$ 個のクエリに答える必要があります。各クエリは整数 $r$ で表され、$p + q = r$ という条件の下で、$p$ の最大値および $q$ の最大値をそれぞれ求める必要があります。

数列 $A$ は長くなる可能性があるため、ランレングス符号化を用いて記述します。より形式的には、$n$ 個の整数の組 $(v_1, l_1), (v_2, l_2), \dots, (v_n, l_n)$ が与えられ、数列 $A$ は次のように生成されます。空の数列から開始し、まず $v_1$ を数列の末尾に $l_1$ 回追加し、次に $v_2$ を数列の末尾に $l_2$ 回追加し、……、最後に $v_n$ を数列の末尾に $l_n$ 回追加します。例については、以下の入出力例の解説を参照してください。

入力

各テストファイルには1つのテストケースのみが含まれます。

1行目には2つの整数 $n$ と $m$ ($1 \le n, m \le 2 \times 10^5$) が与えられ、それぞれ数列のランレングス符号化の長さとクエリの数を表します。

続く $n$ 行の各行には、2つの整数 $v_i$ と $l_i$ ($1 \le v_i, l_i \le 10^9$) が与えられます。したがって、数列 $A$ の長さ $k$ は $k = \sum_{i=1}^{n} l_i$ として計算できます。すべての $1 \le i < n$ に対して $v_i \neq v_{i+1}$ であることが保証されています。

続く $m$ 行の各行には、整数 $r_i$ ($1 \le r_i \le k$) が与えられ、それぞれ $i$ 番目のクエリを表します。

出力

各クエリに対して、$p + q = r$ という条件の下での $p$ の最大値と $q$ の最大値を、スペース区切りで1行に出力してください。

入出力例

入力 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番目のクエリでは、数列を2つの連続する部分配列に分割する必要があります。

• 和が奇数である部分配列の数を最大化するために、$A$ を $5, 5, 5 \mid 2, 2, 7$ に分割できます。どちらの部分配列も和が奇数であるため、$p$ の最大値は 2 です。
• 和が偶数である部分配列の数を最大化するために、$A$ を $5, 5 \mid 5, 2, 2, 7$ に分割できます。どちらの部分配列も和が偶数であるため、$q$ の最大値は 2 です。

5番目のクエリでは、数列を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 です。