Частинки
Два лінійні прискорювачі частинок 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) і vxi (1 ≤ vx[i] ≤ 10^9) кожен: момент вистрілу і швидкість відповідної x-частинки.
Останні N рядків вхідних даних містять, відповідно, кожен момент вистрілу ty[i] (0 ≤ ty[i] ≤ 10^9) і швидкість vyi (1 ≤ vy[i] ≤ 10^9) відповідної y-частинки у тому ж форматі.
Вихідні дані
Програма повинна вивести на стандартний вихід K рядків, кожен з яких містить два розділені пробілом додатні цілі числа: номери x-частинки та y-частинки, які беруть участь у відповідному зіткненні.
Рядки виводяться у порядку зростання за порядком зіткнень – від першого до K-го.