Hissəciklər#8722
İki xətti hissəcik sürətləndiricisi A və B bir-birinə qarşı yerləşdirilib və aralarındakı məsafə L-dir. A sürətləndiricisi x-hissəcikləri, B isə y-hissəcikləri atır. Hər iki cür hissəcik bir-birlərinin üzərinə doğru hərəkət edir və bir x-hissəciyi bir y-hissəciyi ilə qarşılaşdıqda onlar toqquşur və yox olurlar. Bilmək lazımdır ki, bir x-hissəciyi digər x-hissəcikləri, eləcə də bir y-hissəciyi digər y-hissəcikləri heç bir nəticə olmadan ötüb keçə bilər.
Beləliklə, müəyyən bir zaman anında (bunu sıfır qəbul edək), hər iki sürətləndiricidən N x-hissəciyi və N y-hissəciyi atılır. Hər bir hissəcik öz sabit sürəti ilə hərəkət edir. Hissəciklər hər iki tip üçün atıldığı ardıcıllıqda 1-dən N-ə qədər nömrələniblər.
Qeyd: Zaman t üçün, sürəti v olan bir hissəcik s = vt məsafəsini gedir.
x-hissəcikləri üçün atılma zamanları 0=tx[1] < tx[2] < tx[3] < ... < tx[N], onların sürətləri isə vx[1], vx[2], vx[3], ..., vx[N]-dir.
Müvafiq olaraq, y-hissəcikləri üçün atılma anları 0=ty[1] < ty[2] < ty[3] < ... < ty[N], onların sürətləri isə vy[1], vy[2], vy[3], ..., vy[N]-dir.
Atış belə həyata keçirilir ki, aşağıdakı şərtlər təmin olunur:
Hər bir hissəciyin əks tipli hissəciklə toqquşması baş verəcək;
İki hissəcik toqquşanda, digər bütün hissəciklər toqquşma nöqtəsindən ən azı 1 uzaqlıqdadır. Bu, ilk K toqquşma üçün zəmanət verilir.
İki tip hissəcik arasında baş verən ilk K toqquşmanı müəyyən edən particles proqramı yazın.
Birinci sətirdə üç boşluqla ayrılmış müsbət tam ədəd verilir: N (1 ≤ N ≤ 50000), L (1 ≤ L ≤ 10^9), və K (1 ≤ K ≤ 100).
Növbəti N sətirin hər birində iki boşluqla ayrılmış, müvafiq x-hissəciyi üçün atılma anı tx[i] (0 ≤ tx[i] ≤ 10^9) və sürəti vxi (1 ≤ vx[i] ≤ 10^9) verilir.
Sonrakı N giriş sətrində isə müvafiq y-hissəciyi üçün atılma anı ty[i] (0 ≤ ty[i] ≤ 10^9) və sürəti vyi (1 ≤ vy[i] ≤ 10^9) eyni formatda verilir.
Proqram K sətr çap etməlidir. Hər sətirdə iki boşluqla ayrılmış müsbət tam ədəd: müvafiq toqquşmada iştirak edən x-hissəciyi və y-hissəciyi nömrəsi olmalıdır.
Sətirlər toqquşma ardıcıllığına görə - birincidən K-cıya qədər artan qaydada çap olunmalıdır.
Nümunə 1