Задача 44312. sea ​​battle

In the old Sea Battle slot machine the player uses torpedoes to shoot down ships moving across the playing field from left to right or right to left.
In our version of the game, several ships can be on the field at the same time. All ships move at the same speed to the left or to the right. In one second, each ship moves one unit of coordinate system length. This means that one second after the start of the game, the ship that was at point 20 and moving to the right will be at point 21, and the ship that was at point 30 and moving to the left will be at point 29.
You can launch torpedoes that will knock out ships. A torpedo fired at a point with a certain coordinate destroys a ship that is at that moment at that point. At the same time, if there are several ships at this point at this moment in time, then the torpedo will hit all these ships. You can even launch multiple torpedoes at the same time!
Destroy all ships using the minimum number of torpedoes.

Input
The first line contains an integer N — the number of ships moving to the left (with decreasing coordinates). The second line contains an integer M — the number of ships moving to the right (with increasing coordinates). It is guaranteed that 1 ≤ N + M ≤ 10⁵, N > 0 and M> 0.
The next N lines contain one integer each l_i — initial coordinates of ships moving to the left. The next M lines contain one integer each ri — initial coordinates of ships moving to the right. The l_i coordinates are in ascending order, the ri  coordinates are also given in ascending order. It is guaranteed that all initial coordinates l_i and r_i are even, distinct and do not exceed 10⁹.
Imprint
The program should output as many lines as there are torpedoes needed to destroy all ships, while the i-th line should contain two integers t_i — time of strike with the i-th torpedo and x_i — i-th torpedo strike coordinate. All t_i and xi must be integers, 0 ≤ t_i ≤ 10¹⁸ , −10¹⁸ ≤ x_i ≤ 10¹⁸. Several torpedoes can be launched at one point in time, several torpedoes can be fired at one point at different points in time.

Examples

#	Input	Output
1	2 1 10 30 20	5 25 28

Remark
In the example from the condition, two ships are moving to the left and one ship is moving to the right. The start coordinates of ships moving to the left are l₁ = 10 and l₂ = 30, and the start coordinates of ships moving to the right are r_{1< /sub> = 20. At time t1 = 5, two ships — moving left from point 20 and moving right from point 30. They can be knocked out with a single torpedo. The remaining ship moving to the left can be hit, for example, at time t2 = 2 at x2 = 8.}