Частицы
Два линейных ускорителя частиц A и B, расположенные друг напротив друга на расстоянии L, ускоряют элементарные частицы. Ускоритель A выпускает x-частицы, а B — y-частицы. Эти частицы движутся навстречу друг другу, и при встрече x-частицы с y-частицей происходит их столкновение и аннигиляция. При этом x-частицы могут обгонять другие x-частицы, а y-частицы могут обгонять другие y-частицы без каких-либо последствий.
В момент времени, который мы принимаем за ноль, начинается выпуск N x-частиц и N y-частиц из двух ускорителей. Каждая частица движется с собственной постоянной скоростью. Частицы нумеруются в порядке их выпуска от 1 до N, как для x-частиц, так и для y-частиц.
Замечание: Для времени t, частица со скоростью v проходит расстояние s = vt.
Моменты выпуска для x-частиц: 0=tx[1] < tx[2] < tx[3] < ... < tx[N], и их скорости: vx[1], vx[2], vx[3], ..., vx[N].
Аналогично, для y-частиц моменты выпуска: 0=ty[1] < ty[2] < ty[3] < … < ty[N], и их скорости: vy[1], vy[2], vy[3], ..., vy[N].
Выпуск частиц организован так, чтобы соблюдались следующие условия:
Каждая частица столкнется с частицей противоположного типа;
В момент столкновения двух частиц все остальные частицы будут находиться на расстоянии не менее 1 от точки столкновения. Это условие выполняется для первых К столкновений.
Напишите программу particles, чтобы определить первые K столкновений между частицами двух видов.
Входные данные
Первая строка содержит три положительных целых числа, разделенных пробелами: N (1 ≤ N ≤ 50000), L (1 ≤ L ≤ 10^9), и K (1 ≤ K ≤ 100).
Следующие N строк содержат по два неотрицательных целых числа, разделенных пробелами: tx[i] (0 ≤ tx[i] ≤ 10^9) и vx[i] (1 ≤ vx[i] ≤ 10^9), которые представляют момент выпуска и скорость соответствующей x-частицы.
Последние N строк содержат момент выпуска ty[i] (0 ≤ ty[i] ≤ 10^9) и скорость vy[i] (1 ≤ vy[i] ≤ 10^9) соответствующей y-частицы в том же формате.
Выходные данные
Программа должна вывести K строк, каждая из которых содержит два положительных целых числа, разделенных пробелами: номера x-частицы и y-частицы, которые участвуют в соответствующем столкновении.
Строки выводятся в порядке увеличения номеров столкновений — от первого до K-го.