Oxatanlar
Oxatanların yarışları aşağıdakı qaydalara əsasən keçirilir. n hədəf var, bunlar bir sıra üzrə yerləşdirilib və sıra üzrə 1-dən n-ə qədər nömrələnib (ən sol hədəf 1 nömrəlidir, ən sağ hədəf isə n nömrəlidir). Həmçinin 2*n oxatan var. Turnir zamanı hər bir hədəfə iki oxatan atəş açır. Hər yarış turu aşağıdakı prosedura uyğun keçirilir:
- Hər hədəfə atəş açan iki oxatan bir-biri ilə yarışır və qalib və məğlub müəyyən edilir. Bundan sonra bütün oxatanlar aşağıdakı şəkildə hərəkət edirlər:
- 2-dən n-ə qədər nömrəli hədəflərdəki qaliblər bir hədəf sola hərəkət edirlər (yəni müvafiq olaraq 1-dən n-1-ə qədər hədəflərə),
- 2-dən n-ə qədər nömrəli hədəflərdəki məğlublar və 1 nömrəli hədəfdəki qalib eyni hədəflərdə qalırlar,
- 1 nömrəli hədəfdəki məğlub n nömrəli hədəfə keçir.
Yarış r raunddan ibarətdir, raundların sayı oxatanların sayından az deyil (yəni r ≥ 2*n). Siz turnirə vaxtında gələn yeganə oxatansınız. Digər 2*n - 1 oxatanlar daha əvvəl gəlib və artıq sıraya düzülüblər. İndi siz onların arasında bir yerə "daxil olmalısınız". Siz bilirsiniz ki, siz yerinizi tutduqdan sonra, ən sol iki oxatan 1 nömrəli hədəfdə, növbəti iki oxatan 2 nömrəli hədəfdə və s. turnirə başlayacaq. Ən sağ iki oxatan n nömrəli hədəfdə turnirə başlayacaq.
Turnirdə iştirak edən bütün 2*n oxatanın (siz də daxil olmaqla) bacarıqlarına uyğun olaraq müəyyən edilmiş rütbələri var, burada kiçik rütbə daha yüksək bacarıqlara uyğun gəlir. Eyni rütbəyə malik iki oxatan yoxdur. Həmçinin, iki oxatan yarışdıqda, həmişə daha kiçik rütbəyə malik olan oxatan qalib gəlir.
Rəqiblərinizin atəş gücünü bildiyiniz üçün turniri mümkün olan ən kiçik nömrəli hədəfdə bitirmək üçün elə yerləşmək istəyirsiniz. Əgər bunu etmək üçün bir neçə yol varsa, ən böyük nömrəli hədəfdə başlayan yolu seçin.
Bütün oxatanların rütbələri, o cümlədən sizin rütbəniz və rəqiblərinizin sıradakı yerləşməsi verildikdə, yuxarıda təsvir edilən məqsədə çatmaq üçün turnirə hansı hədəfdən başlamalı olduğunuzu müəyyən edən bir proqram yazın.
Giriş verilənləri
Birinci sətir iki tam ədədi - hədəflərin sayı n (1 ≤ n ≤ 200,000), bu oxatanların sayının yarısına bərabərdir, və yarışın raundlarının sayı r (2*n ≤ r ≤ 1,000,000,000), boşluqla ayrılmış şəkildə ehtiva edir.
Növbəti 2*n sətir oxatanların rütbələrini ehtiva edir. Bu sətirlərdən birincisi sizin rütbənizi ehtiva edir. Digər sətirlər rəqiblərinizin rütbələrini sıradakı yerləşmə qaydasında (soldan sağa) bir-bir sətirdə ehtiva edir. Bu 2*n sətirin hər biri 1 ilə 2*n arasında olan bir tam ədəd ehtiva edir. Rütbə 1 ən yaxşıdır, rütbə 2*n ən pisdir. Heç bir iki oxatan eyni rütbəyə malik deyil. Məlumdur ki, 1 ≤ S_k ≤ 2*n, burada S_k k nömrəli oxatanın rütbəsidir.
Çıxış verilənləri
Turnirə başlayacağınız hədəfin nömrəsi olan 1 ilə n arasında bir tam ədəd çap edin.