Có ~n~ chú ếch đang ngồi trên trục tọa độ ~Ox~. Với mỗi chú ếch, ta biết hai giá trị ~x_i~ và ~t_i~ lần lượt là vị trí ngồi và độ dài lưỡi ban đầu của chú ếch thứ ~i~. ~m~ con muỗi sẽ lần lượt hạ cạnh xuống trục ~Ox~. Với mỗi con muỗi, ta biết hai giá trị ~p_j~ và ~b_j~ lần lượt là vị trí hạ cánh và độ lớn của con muỗi thứ ~j~. Các chú ếch và muỗi có thể được biễu diễn bằng các điểm trên trục tọa độ.

Một chú ếch có thể ăn một con muỗi nếu như con muỗi ở cùng vị trí với chú ếch hoặc ở phía bên phải với khoảng cách giữa chú ếch và con muỗi không lớn hơn độ dài lưỡi của chú ếch đó.

Nếu tại cùng một thời điểm, nhiều chú ếch có thể ăn được một con muỗi, thì chú ếch ở vị trí trái nhất sẽ ăn nó (chú ếch có giá trị ~x_i~ bé nhất). Sau khi ăn một con muỗi, độ dài lưỡi của một chú ếch sẽ tăng đúng bằng độ lớn của con muỗi đó. Sau đó, chú ếch sẽ ăn những con muỗi khác nếu như có thể (chưa bị ăn trong các lượt trước đó).

Với mỗi chú ếch, hãy in ra hai giá trị - số lượng con muỗi đã ăn và độ dài lưỡi sau khi tất cả con muỗi đã hạ cánh và không còn con muỗi nào trên trục tọa độ có thể bị ăn.

Những con muỗi sẽ hạ cánh xuống trục tọa theo thứ tự của input. Mỗi con muỗi sẽ chỉ hạ cánh sau khi tất cả con muỗi đã hạ cạnh trước đó đã bị ăn hoặc không thể bị ăn.

Input

Dòng đầu tiên gồm hai số nguyên ~n, m\,(1 \le n, m \le 2 \times 10^5)~ lần lượt là số chú ếch và số con muỗi.

~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x_i, t_i\,(0 \le x_i, t_i \le 10^9)~ lần lượt là vị trí và độ dài lưỡi ban đầu của chú ếch thứ ~i~. Input đảm bảo không có hai chú ếch nào sẽ ngồi ở cùng một vị trí.

~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~p_j, b_j\,(0 \le p_j, b_j \le 10^9)~ lần lượt là vị trí và độ lớn của con muỗi thứ ~j~.

Output

In ra ~n~ dòng, dòng thứ ~i~ gồm hai số nguyên lần lượt là số con muỗi mà chú ếch thứ ~i~ ăn được và độ dài cuối cùng của lưỡi của của chú ếch thứ ~i~.

Sample 1

Input

4 6
10 2
15 0
6 1
0 1
110 10
1 1
6 0
15 10
14 100
12 2

Output

3 114
1 10
1 1
1 2

Sample 2

Input

1 2
10 2
20 2
12 1

Output

1 3