Sonuncu qarışqa#6779
Düz bir tunel var və bu tuneldə heç bir qolu olmayan qarışqalar gəlib-gedir. Bəzi qarışqalar soldan sağa, digərləri isə sağdan sola hərəkət edir. Bütün qarışqalar sabit 1 sm/s sürətlə hərəkət edir. İki qarışqa qarşılaşdıqda, onlar bir-birindən yan keçməyə çalışırlar. Lakin tunelin bəzi hissələri dar olduğundan, iki qarışqa orada yan keçə bilmir. İki qarışqa dar bir hissədə qarşılaşdıqda, onlar geri dönür və əks istiqamətdə hərəkət etməyə başlayırlar. Qarışqa tunelin hər hansı bir ucuna çatdıqda, o, tuneli tərk edir.
Tunelin uzunluğu tam ədəd santimetrlə ifadə edilir. Hər dar hissə tunelin hər iki ucundan tam ədəd məsafədə yerləşir. Bu hissələrdən başqa, tunelin hər yeri qarışqaların bir-birindən yan keçməsi üçün kifayət qədər genişdir. Bütün qarışqalar hərəkətə müxtəlif dar hissələrdən başlayır. Tunelə yeni qarışqalar daxil ola bilməz. Buna görə də, tuneldə olan bütün qarışqalar nəhayət onu tərk edəcək. Sizdən bir proqram yazmağınız tələb olunur ki, hansı qarışqanın sonuncu olaraq tuneli tərk edəcəyini və bunun nə vaxt baş verəcəyini bildirsin.
Şəkil 1 tunelin 6 santimetr uzunluğunda ilk iki saniyə ərzində qarışqaların hərəkətini göstərir. Əvvəlcə 1, 2 və 3 nömrəli üç qarışqa sol kənardan müvafiq olaraq 1, 2 və 5 santimetr məsafədə yerləşən dar hissələrdən hərəkətə başlayır. 0.5 saniyə sonra 1 və 2 nömrəli qarışqalar geniş bir hissədə qarşılaşır və bir-birindən yan keçirlər. Hərəkətə başladıqdan iki saniyə sonra 1 və 3 nömrəli qarışqalar dar bir hissədə qarşılaşır və geri dönürlər.
Şəkil 1 birinci testə uyğundur.
Şəkil 1. Qarışqaların hərəkəti
Bir neçə testdən ibarətdir. Hər test aşağıdakı formatda olur:
n l
d_1 p_1
d_2 p_2
...
d_n p_n
Testin ilk sətiri iki tam ədəd ehtiva edir: n (1 ≤ n ≤ 20) - qarışqaların sayı və l (n + 1 ≤ l ≤ 100) - tunelin uzunluğu santimetrlə. Növbəti n sətir qarışqaların ilkin vəziyyətini təyin edir. Hər sətir iki ədəd ehtiva edir: d_i və p_i. Qarışqalar 1 -dən n -ə qədər nömrələnir. i nömrəli qarışqa ilkin istiqaməti d_i və ilkin mövqeyi p_i ilə başlayır. İstiqamət d_i (1 ≤ i ≤ n) L (sola) və ya R (sağa) dəyərini alır. Tam ədəd ilkin mövqe p_i (1 ≤ i ≤ n) tunelin sol ucundan santimetrlə olan məsafəni göstərir. Qarışqalar soldan sağa doğru sıralanır, yəni 1 ≤ p_1 < p_2 < ... < p_n ≤ l−1.
Son testdən sonra iki sıfırdan ibarət bir sətir gəlir.
Hər test üçün bütün qarışqaların tuneli tərk edəcəyi saniyələrin sayını və sonuncu qarışqanın hansı olacağını çıxış edin. Sonuncu qarışqanın nömrəsini göstərmək lazımdır. Əgər iki qarışqa tuneli eyni vaxtda tərk edərsə, sol tərəfdən tuneli tərk edəcək qarışqanın nömrəsini çıxış edin.
Nümunə 1