Дана последовательность целых чисел $A = a_1, a_2, \dots, a_k$ длины $k$. Вы можете разбить её на несколько непустых непрерывных подмассивов так, чтобы каждый элемент принадлежал ровно одному подмассиву. Для каждого подмассива мы вычисляем сумму его элементов. Пусть $p$ — количество подмассивов с нечётной суммой, а $q$ — количество подмассивов с чётной суммой.

Вам нужно ответить на $m$ запросов об этой последовательности. Каждый запрос задаётся целым числом $r$, и вам нужно найти максимально возможные значения $p$ и $q$ при условии, что $p + q = r$, соответственно.

Так как последовательность $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$ строк содержат по два целых числа $v_i$ и $l_i$ ($1 \le v_i, l_i \le 10^9$). Таким образом, длина последовательности $A$ может быть вычислена как $k = \sum_{i=1}^n l_i$. Гарантируется, что $v_i \neq v_{i+1}$ для всех $1 \le i < n$.

Следующие $m$ строк содержат по одному целому числу $r_i$ ($1 \le r_i \le k$), обозначающему $i$-й запрос.

Выходные данные

Для каждого запроса выведите одну строку, содержащую два целых числа, разделённых пробелом, обозначающих максимально возможные значения $p$ и $q$ при условии $p + q = r$, соответственно.

Примеры

Пример 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.