給定一個長度為 $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$ 的產生方式如下：從空數列開始，首先將 $v_1$ 接在數列後方 $l_1$ 次，接著將 $v_2$ 接在數列後方 $l_2$ 次，依此類推，最後將 $v_n$ 接在數列後方 $l_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$ 可計算為 $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。