Manfiy bo'lmagan butun son \(n\) berilgan. Uning raqamlarini teskari tartibda joylashtirib hosil bo'lgan sonni toping.

Masalan, \(n = 1234\) uchun javob \(4321\) bo'ladi.

Yagona qatorda butun son \(n\) beriladi (\(0 \le n \le 10^9\)).

\(n\) sonining raqamlari teskari tartibda joylashtirilgandan hosil bo'lgan sonni chiqaring.

Bir kuni Aziz akaning kalkulyatoridagi "\(+\)" tugmasi buzilib qoldi. Endi u ikkita sonni qo'shish kerak bo'lsa ham, bu tugmadan foydalana olmaydi. Aziz akaga yordam bering — dasturingiz ikkita sonning yig'indisini topsin, lekin kodingizda hech qanday joyda "\(+\)" belgisidan foydalanmasligingiz kerak, agar foydalansangiz xatolik xabarini olasiz!

Bitta qatorda probel bilan ajratilgan ikkita butun son \(a\) va \(b\) beriladi (\(−10^9 \le a, b \le 10^9\)).

\(a\) va \(b\) ning yig'indisini chiqaring.

Aziz akaning noutbukida klaviaturaning butun raqamlar qatori (\(0\) dan \(9\) gachasi) birdaniga ishlamay qoldi. Ammo unga topshiriq berishgan: \(n\) ta sondan iborat \(a_1, a_2, \dots, a_n\) ro'yxat berilgan, shulardan eng kattasi bilan eng kichigini topib, ularning o'rta arifmetigini (pastga yaxlitlab) hisoblash kerak.

Sizning vazifangiz — Aziz akaga shunday dastur tuzib berinki, dastur kodingizning hech qanday joyida \(0\) dan \(9\) gacha bo'lgan raqam belgilaridan foydalanmang. Agar foydalansangiz, tekshiruvchi dastur kodingizni rad etadi va xatolik xabarini beradi.

Birinchi qatorda bitta butun son \(n\) — sonlar soni beriladi (\(2 \leq n \leq 10^5\)). Ikkinchi qatorda probel bilan ajratilgan \(n\) ta butun son beriladi \(a_1, a_2, \dots, a_n\) (\(−10^9 \le a_i \le 10^9\)).

Bitta butun son chiqaring — ro'yxatdagi eng katta va eng kichik sonlarning o'rta arifmetigini (pastga yaxlitlab).

Marsga yuborilgan "Roverchik" nomli tadqiqot roboti uzun tog' tizmasi bo'ylab harakatlanmoqda. Tizma \(N\) ta nuqtadan iborat (\(1\) dan \(N\) gacha raqamlangan), har bir nuqtaning o'z balandligi bor va barcha balandliklar bir-biridan farq qiladi.

Yer nazorat markazi Roverchikka topshiriq berdi: tizmada "vodiy nuqtasi"ni toping — ya'ni shunday nuqtaki, uning balandligi ikkala qo'shnisining balandligidan past bo'lsin (agar nuqta chekkada bo'lsa, yo'q qo'shni cheksiz baland tog' deb hisoblanadi). Bunday nuqta tizmada albatta topiladi.

Muammo shundaki, Roverchikning balandlik o'lchagichi juda ko'p energiya sarflaydi — shuning uchun siz ko'pi bilan \(130\) marta o'lchov qilishingiz mumkin. Ortiqcha o'lchov qilsangiz, missiya muvaffaqiyatsiz deb topiladi.

Yer nazorat markazi bilan aloqa quyidagicha ishlaydi:

• Siz "\(? \,\, i\)" deb yuborsangiz (\(1 \le i \le N\)), markaz sizga \(i\)-nuqtaning balandligini qaytaradi.
• Javobni topgach, "\(! \,\, i\)" deb yuborasiz — bu sizning yakuniy javobingiz (\(i\) — vodiy nuqtasi indeksi). Shundan so'ng dasturingiz darhol ishini tugatishi kerak.

Roverchikka yordam bering!

Birinchi qatorda \(N\) butun soni beriladi — bu tog' tizimidagi nuqtalar soni (\(1 \le N \le 10^{18}\)).

Har bir so'rov "\(? \,\, i\)" ko'rinishida yuboriladi (\(1 \le i \le N \le 10^{18}\)) va flush qilinadi. Javobida \(i\)-nuqtaning balandligi qaytadi (barcha balandliklar [\(-10^{18}, 10^{18}\)], bir-biridan farqli).

Yakuniy javob "\(! \,\, i\)" ko'rinishida chiqariladi, shundan so'ng dastur darhol tugaydi. Ruxsat etilgan so'rovlar soni — ko'pi bilan \(130\) ta ("\(i\)" bunga kirmaydi).

Dasturingiz alohida "javob fayli" chiqarmaydi — u faqat "\(?\)" so'rovlarini yuboradi va oxirida "\(! \,\, i\)" bilan yakuniy javobini beradi.

\(1\) dan \(N\) gacha bo'lgan sonlar orasida sirli son \(T\) yashiringan. Siz uni topishga harakat qilasiz — lekin sizga javob beradigan qorovul ayyor: u butun o'yin davomida jami bor-yo'g'i bir marta yolg'on gapirishi mumkin — qachon yolg'on gapirishini siz oldindan bilmaysiz. Ustiga-ustak, qorovul \(T\) qiymatini o'yin boshidanoq belgilab qo'ymaydi, faqat barcha javoblari qandaydir \(T\) bilan mos kelishi kerak.

Diqqat: yolg'on istalgan javobda bo'lishi mumkin — hatto "\(=\)" deb aytgan joyida ham yolg'on gapirgan bo'lishi mumkin!

Sizning vazifangiz — qorovulning yagona yolg'onidan aldanib qolmasdan, \(T\) ni aniq topib berish.

Dastlab sizga bitta \(N\) (\(1 \le N \le 10^{18}\)) soni beriladi.

Shundan so'ng, qarovul sizning so'rovlaringizga \(3\) xil usuldan birida javob beradi: "\(>\)" (\(T > i\)), "\(<\)" (\(T < i\)) yoki "\(=\)" (\(T = i\)). 

Qarovulga siz so'rovni "\(? \,\, i\)" (\(1 \le i \le N\)) ko'rinishida yuborasiz (jami so'rovlar soni \(190\) tadan oshlamsligi shart). Qorovulning javobidan so'ng sirli \(T\) sonini aniq topganingizda, natijani  "\(! \,\, T\)" ko'rinishida chiqarishingiz kerak, har bir so'rovdan kiyin buferni darhol tozalab tashlang.

Kosmik aloqa markazi \(n\) xil signal turini qo'llab-quvvatlaydi, ular \(1\) dan \(n\) gacha raqamlangan. \(i\)-turdagi signal uchun ruxsat etilgan chastota oralig'i \([a_i, b_i]\) berilgan.

Tarmoq deb \(T = (V, E)\) ildizli daraxtga aytiladi, unda har bir bog'lanish (qirra) yuqoridagi \(n\) turdan biriga tegishli. Tarmoq barqaror deyiladi, agar quyidagi ikki shart bajarilsa:

• Ixtiyoriy uchta \(X, Y, Z \in V\) tugun uchun, agar \((X, Y)\) va \((Y, Z)\) bog'lanishlari ikkalasi ham mavjud bo'lsa, ularning turlari har xil bo'lishi shart. (Boshqacha aytganda: bitta tugunga ulangan barcha bog'lanishlar — u yuqoriga ham, pastga ham bo'lsin — juft-jufti bilan turlari bo'yicha farqlanishi kerak.)
• Har bir signal turi \(i \in [1, n]\) uchun \(g(X, i)\) orqali \(X\) tugunidan markaz (ildiz)gacha bo'lgan yo'ldagi \(i\)-turdagi bog'lanishlar sonini belgilaymiz. U holda \(\max_{X \in V}\) \(g(X, i)\) qiymati \([a_i, b_i]\) oralig'ida yotishi shart.

Ikkita tarmoq \(T = (V, E)\) va \(T' = (V', E')\) bir xil tuzilishga ega (isomorf) deyiladi, agar:

• \(\vert{}V\vert{} = \vert{}V'\vert{}\);
• shunday biyeksiya \(f : V \to V'\) mavjudki: \(r\) va \(r'\) mos ravishda \(T\) va \(T'\)ning markazlari bo'lsa, \(f(r) = r'\); va har qanday \((X, Y) \in E\) uchun \((f(X), f(Y)) \in E'\) bo'lib, bu bog'lanishning turi \((f(X), f(Y))\) bog'lanishining turi bilan bir xil.

Sizga topshiriq — juft-jufti bilan izomorf bo'lmagan barqaror tarmoqlardan iloji boricha ko'prog'ini tanlash, va ularning maksimal sonini 2 moduli bo'yicha chiqarish.

Birinchi qatorda \(t\) (\(1 \le t \le 10^4\)) — test holatlari soni. Har bir test holati uchun: birinchi qatorda \(n\) (\(1 \le n \le 2 \times 10^6\)) — signal turlari soni; keyingi \(n\) qatorning har birida ikkita butun son \(a_i, b_i\) (\(0 \le a_i \le b_i \le 2 \times 10^5\), \(b_i \ge 1\)).

Kafolatlanadiki, barcha test holatlari bo'yicha \(n\) larning yig'indisi \(2 \times 10^6\) dan oshmaydi. \(m = \max_i b_i\) bo'lsin — barcha test holatlari bo'yicha \(m\) larning yig'indisi \(2 \times 10^5\) dan oshmaydi.

Har bir test holati uchun — tanlash mumkin bo'lgan maksimal tarmoqlar sonini \(2\) moduli bo'yicha (\(0\) yoki \(1\)) chop eting.