задание олимпиады

В старом игровом автомате «Морской бой» игрок сбивает торпедами корабли, двигающиеся по игровому полю слева направо или справа налево.

В нашем варианте игры на поле может находиться одновременно несколько кораблей. Все корабли движутся с одинаковыми скоростями налево или направо. За одну секунду каждый корабль передвигается на единицу длины системы координат. Это означает, что через одну секунду после начала игры корабль, который находился в точке 20 и двигался направо, будет находиться в точке 21, а корабль, который находился в точке 30 и двигался налево, окажется в точке 29.

Вы можете выпускать торпеды, которые будут подбивать корабли. Торпеда, выпущенная в точке с какой-то координатой, уничтожает корабль, находящийся в этот момент в этой точке. При этом если в этой точке в этот момент времени окажется несколько кораблей, то торпеда подобьёт все эти корабли. Вы даже можете одновременно выпускать несколько торпед!

Подбейте все корабли, используя минимальное число торпед.

Формат входных данных

В первой строке содержится целое число N — количество кораблей, движущихся влево (с уменьшением координаты). Во второй строке содержится целое число M — количество кораблей, движущихся вправо (с увеличением координаты). Гарантируется, что 1≤N+M≤10^5, N≥0 и M≥0

Следующие N строк содержат по одному целому числу l(i) — начальные координаты кораблей, двигающихся влево. Следующие M строк содержат по одному целому числу r(i) — начальные координаты кораблей, двигающихся вправо. Координаты l(i) идут в порядке возрастания, координаты r(i) также заданы в порядке возрастания. Гарантируется, что все начальные координаты l(i) и r(i) чётные, различные и не превосходят по модулю 10^9

Формат выходных данных

Программа должна вывести столько строк, сколько торпед необходимо для уничтожения всех кораблей, при этом i-я строка должна содержать два целых числа t(i) — время нанесения удара i-й торпедой и x(i) — координату удара i-й торпедой. Все t(i) и x(i) должны быть целыми, 0≤t(i)≤10^18, −10^18≤x(i)≤10^18. один момент времени можно выпускать несколько торпед, в одну точку можно выпускать несколько торпед в разные моменты времени.

Система оценивания

Решения, правильно работающие при N+M≤10, 0≤ l(i) ≤100, 0≤r(i)≤100, будут оцениваться в 20 баллов. Решения, правильно работающие при N+M≤1000, будут оцениваться в 50 баллов.

Замечания к примерам

В примере из условия два корабля движутся влево и один корабль движется вправо. Начальные координаты кораблей, двигающихся влево, равны l1=10 и l2=30, а начальная координата корабля, двигающегося вправо, равна r1=20. В момент времени t1=5 в одной точке x1=25 окажутся два корабля — двигающийся влево из точки 20 и двигающийся вправо из точки 30. Их можно подбить одной торпедой. Оставшийся корабль, двигающийся влево, можно подбить, например, в момент времени t2=2 в точке x2=8.

Ввод Вывод

2 1 10 30 20

5 25 2 8