В старом игровом автомате «Морской бой» игрок сбивает торпедами корабли, двигающиеся по игровому полю слева направо или справа налево.
В нашем варианте игры на поле может находиться одновременно несколько кораблей. Все корабли движутся с одинаковыми скоростями налево или направо. За одну секунду каждый корабль передвигается на единицу длины системы координат. Это означает, что через одну секунду после начала игры корабль, который находился в точке 20 и двигался направо, будет находиться в точке 21, а корабль, который находился в точке 30 и двигался налево, окажется в точке 29.
Вы можете выпускать торпеды, которые будут подбивать корабли. Торпеда, выпущенная в точке с какой-то координатой, уничтожает корабль, находящийся в этот момент в этой точке. При этом если в этой точке в этот момент времени окажется несколько кораблей, то торпеда подобьёт все эти корабли. Вы даже можете одновременно выпускать несколько торпед!
Подбейте все корабли, используя минимальное число торпед.
Входные данные
В первой строке содержится целое число N — количество кораблей, движущихся влево (с уменьшением координаты). Во второй строке содержится целое число M — количество кораблей, движущихся вправо (с увеличением координаты). Гарантируется, что 1 ≤ N + M ≤ 10
5, N > 0 и M > 0.
Следующие N строк содержат по одному целому числу l
i — начальные координаты кораблей,двигающихся влево. Следующие M строк содержат по одному целому числу ri — начальные координаты кораблей, двигающихся вправо. Координаты l
i идут в порядке возрастания, координаты ri также заданы в порядке возрастания. Гарантируется, что все начальные координаты l
i и r
i чётные, различные и не превосходят по модулю 10
9.
Выходные данные
Программа должна вывести столько строк, сколько торпед необходимо для уничтожения всех кораблей, при этом i-я строка должна содержать два целых числа t
i — время нанесения удара i-й торпедой и x
i — координату удара i-й торпедой. Все t
i и xi должны быть целыми, 0 ≤ t
i ≤ 10
18 , −10
18 ≤ x
i ≤ 10
18. В один момент времени можно выпускать несколько торпед, в одну точку можно выпускать несколько торпед в разные моменты времени.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
1
10
30
20 |
5 25
2 8 |
Замечание
В примере из условия два корабля движутся влево и один корабль движется вправо. Начальные координаты кораблей, двигающихся влево, равны l
1 = 10 и l
2 = 30, а начальная координата корабля, двигающегося вправо, равна r
1 = 20. В момент времени t
1 = 5 в одной точке x
1 = 25 окажутся два корабля — двигающийся влево из точки 20 и двигающийся вправо из точки 30. Их можно подбить одной торпедой. Оставшийся корабль, двигающийся влево, можно подбить, например, в момент времени t
2 = 2 в точке x
2 = 8.