Dany jest ciąg liczb całkowitych $A = a_1, a_2, \dots, a_k$ o długości $k$. Możesz podzielić go na kilka niepustych, spójnych podciągów tak, aby każdy element należał do dokładnie jednego podciągu. Dla każdego podciągu obliczamy sumę jego elementów. Niech $p$ oznacza liczbę podciągów o nieparzystej sumie, a $q$ liczbę podciągów o parzystej sumie.

Musisz odpowiedzieć na $m$ zapytań dotyczących tego ciągu. Każde zapytanie jest określone przez liczbę całkowitą $r$ i musisz znaleźć maksymalne możliwe wartości odpowiednio $p$ oraz $q$ przy założeniu, że $p + q = r$.

Ponieważ ciąg $A$ może być długi, opiszemy go za pomocą kodowania długości serii (run-length encoding). Formalnie, mając $n$ par liczb całkowitych $(v_1, l_1), (v_2, l_2), \dots, (v_n, l_n)$, ciąg $A$ tworzy się w następujący sposób: zaczynając od pustego ciągu, najpierw dołączamy $v_1$ na koniec ciągu $l_1$ razy, następnie dołączamy $v_2$ na koniec ciągu $l_2$ razy, ..., aż w końcu dołączymy $v_n$ na koniec ciągu $l_n$ razy. Zobacz wyjaśnienie przykładowego przypadku testowego poniżej.

Wejście

W każdym pliku wejściowym znajduje się tylko jeden przypadek testowy.

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 2 \times 10^5$), oznaczające długość kodowania długości serii ciągu oraz liczbę zapytań.

W kolejnych $n$ liniach, $i$-ta linia zawiera dwie liczby całkowite $v_i$ oraz $l_i$ ($1 \le v_i, l_i \le 10^9$). Zatem długość ciągu $A$ można obliczyć jako $k = \sum_{i=1}^n l_i$. Gwarantuje się, że $v_i \neq v_{i+1}$ dla wszystkich $1 \le i < n$.

W kolejnych $m$ liniach, $i$-ta linia zawiera liczbę całkowitą $r_i$ ($1 \le r_i \le k$), oznaczającą $i$-te zapytanie.

Wyjście

Dla każdego zapytania wypisz w jednej linii dwie liczby całkowite oddzielone spacją, oznaczające odpowiednio maksymalne możliwe wartości $p$ oraz $q$ przy założeniu, że $p + q = r$.

Przykład

Wejście 1

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

Wyjście 1

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

Uwagi

Dla przykładowego przypadku testowego $A = 5, 5, 5, 2, 2, 7$.

Dla drugiego zapytania musimy podzielić ciąg na 2 spójne podciągi.

• Aby zmaksymalizować liczbę podciągów o nieparzystych sumach, możemy podzielić $A$ na $5, 5, 5 \mid 2, 2, 7$. Oba podciągi mają nieparzyste sumy, więc maksymalne możliwe $p$ wynosi 2.
• Aby zmaksymalizować liczbę podciągów o parzystych sumach, możemy podzielić $A$ na $5, 5 \mid 5, 2, 2, 7$. Oba podciągi mają parzyste sumy, więc maksymalne możliwe $q$ wynosi 2.

Dla piątego zapytania musimy podzielić ciąg na 5 spójnych podciągów.

• Aby zmaksymalizować liczbę podciągów o nieparzystych sumach, możemy podzielić $A$ na $5 \mid 5 \mid 5 \mid 2, 2 \mid 7$, gdzie 4 z nich mają nieparzyste sumy, więc maksymalne możliwe $p$ wynosi 4.
• Aby zmaksymalizować liczbę podciągów o parzystych sumach, możemy podzielić $A$ na $5, 5 \mid 5 \mid 2 \mid 2 \mid 7$, gdzie 3 z nich mają parzyste sumy, więc maksymalne możliwe $q$ wynosi 3.