Do'konda mahsulotga chegirma e'lon qilingan. Sizga mahsulotning boshlang'ich narxi va chegirma foizi berilgan. Chegirma summasini va chegirmadan keyingi yakuniy narxni hisoblang.

Chegirma summasi quyidagi formula bilan hisoblanadi:

\(D = P \times \frac{R}{100}\)

Yakuniy narx esa:

\(F = P - D\)

Bu yerda: \(P\) — mahsulotning boshlang'ich narxi, \(R\) — chegirma foizi, \(D\) — chegirma summasi, \(F\) — yakuniy narx.

Yagona qatorda ikkita son beriladi, bo'sh joy bilan ajratilgan holda \(P\) — mahsulotning boshlang'ich narxi (butun son, \(1 \le P \le 10^6\)) va \(R\) — chegirma foizi (butun son, \(0 \le R \le 100\)).

Ikki qatorda, verguldan keyin aniq 2 ta raqam bilan chiqaring. Birinchi qatorda — chegirma summasi va ikkinchi qatorda — yakuniy narx.

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).

Rustam raqamlari yig'indisi \(10\) ga teng sonlarni mukammal son deb ataydi. Misol mukammal sonlar qatoriga \(19, 28, 37, \dots\) sonlarni kiritishimiz mumkin, lekin \(1, 17, 99\) lar mukammal son emas.

Sizning vazifangiz \(k\)-mukammal sonni hisoblashda Rustamga yordam berishdan iborat.

Kirish faylida \(k\) (\(1 \le k \le 10^5\)) natural soni beriladi.

Chiqish faylida masalaning yechimini chop eting

Sizga \(n \times m\) maydonning tomonlari beriladi. Maydonda uzunligi \(1\) teng yo'laklar hamda \(1 \times 1\) o'lchamdagi bo'g'lar mavjud bo'lib, ushbu maydonning barcha qismini lampalar orqali yoritish talab etiladi. Lampani faqat istalgan yo'lakning o'rtasiga joylashtirish mumkin. Lampa o'zi turgan ikkita qo'shni bo'g'larni yoritadi ( yoki agar maydon chegarasida bo'lsa, faqat bitta bo'g'ni yoritadi).

Misol: rasmda tasvirlangan \(4 \times 5\) maydonda \(1\) teng yo'laklar soni \(49\) ta, \(1 \times 1\) bo'g'lar soni \(20\) ta ga teng. Aylana shaklda sariq belgilar lampalar hisoblanadi. Yoritilgan joylar sariq bilan belgilangan joriy rasmda maydonning barcha qismi yoritilmagan.

Sizning vazifangiz \(n \times m\) maydonni barcha qismini yoritish uchun kerak bo'ladigan minimal lampalar sonini aniqlashdan iborat. 

Kirish faylida ikkita natural son \(n, m\) (\(1 \le n, m \le 10^5\)) maydon o'lchami beriladi.

Chiqish faylida minimal kerak bo'ladigan lampalar sonini chop eting.

Sizga \(n\) ta butun sondan iborat \(a[1], a[2], \dots, a[n]\) massiv va \(k\) soni berilgan. Massivning qism massivi deb \(1 \le l \le r \le n\) bo'lgan \(a[l], a[l+1], \dots, a[r]\) ketma-ketligiga aytiladi. Yig'indisi \(k\) ga qoldiqsiz bo'linadigan qism massivlar sonini toping.

Birinchi qatorda ikkita butun son \(n\) (\(1 \le n \le 100000\)) va \(k\) (\(1 \le k \le 10^9\)) beriladi. Ikkinchi qatorda \(n\) ta butun son \(a[1], a[2], \dots, a[n]\) (\(0 \le a[i] \le 10^9\)) beriladi.

Yagona qatorda — yig'indisi \(k\) ga bo'linadigan qism massivlar sonini chop eting.

Katta shokolad fabrikasida yangi konveyer liniyasi ishga tushirildi. Lentada qator holda \(2 \times n-1\) ta shokolad bo'lagi joylashgan bo'lib, ularning har biri yo achchiq shokolad yoki sutli shokolad turidan biri hisoblanadi.

Fabrika barcha shokoladlarning turini va tartibini allaqachon belgilab qo'ygan. Shokoladlar turi uzunligi \(2 \times n-1\) bo'lgan \(s\) satri orqali beriladi: \(1 \le i \le 2 \times n-1\) uchun, agar \(s_i = \text{'D'}\) bo'lsa, \(i\)-bo'lak achchiq shokolad, agar \(s_i = \text{'M'}\) bo'lsa, \(i\)-bo'lak sutli shokolad hisoblanadi.

Nazoratga jami \(n\) nafar sifat nazorati inspektori jalb qilingan bo'lib, ular \(1\) dan \(n\) gacha raqamlangan. Har bir \(j\)-inspektor ketma-ket joylashgan bo'laklarni, ya'ni \(a_j, a_j+1, \dots, b_j\) pozitsiyalaridagi bo'laklarni tekshirmoqchi, bunda \(1 \le a_j \le b_j \le 2 \times n-1\). Bundan tashqari:

• har bir inspektor kamida \(n\) ta shokolad tekshirishi kerak, ya'ni \(b_j - a_j + 1 \ge n\);
• hech qanday ikkita inspektor aynan bir xil bo'laklarni tekshirmasligi kerak: \(j \neq k\) bo'lsa, \(a_j \neq a_k\) yoki \(b_j \neq b_k\).

Sutli shokolad tarkibidagi sut mahsuloti tufayli saqlash va harorat nazorati talablari ancha qattiqroq, shuning uchun rahbariyat barcha inspektorlar bir xil miqdordagi sutli shokolad bo'lagini tekshirishini xohlaydi — bu nazoratni adolatli taqsimlash uchun ham muhim.

Rahbariyatga yordam bering: shunday \(x\) (\(0 \le x \le 2 \times n-1\)) sonini toping, unda har bir inspektor aynan \(x\) ta sutli shokolad tekshiradigan qilib intervallarni taqsimlash mumkin bo'lsin. Bunday \(x\) doimo mavjud.

Birinchi qatorda \(n\) (\(1 \le n \le 10^6\)) — bunda \(2 \times n-1\) shokolad bo'laklari soni, \(n\) esa inspektorlar soni. Ikkinchi qatorda uzunligi \(2 \times n-1\) bo'lgan \(s\) satri: \(i\)-bo'lak achchiq bo'lsa 'D', sutli bo'lsa 'M'.

Har bir inspektor tekshiradigan sutli shokoladlar sonini — \(x\) ni chop eting. Bir nechta yechim bo'lsa, istalganini chiqarish mumkin.

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.

Sizga \(n\) ta butun sondan iborat \(a[1], a[2], \dots, a[n]\) massiv va ikkita butun son \(L, R\) (\(L \le R\)) berilgan. Massivning qism massivi deb \(1 \le l \le r \le n\) bo'lgan \(a[l], a[l+1], \dots, a[r]\) ketma-ketligiga aytiladi.

Yig'indisi \([L, R]\) oralig'ida (chegaralar bilan birga) yotadigan qism massivlar sonini toping.

Diqqat: massiv elementlari manfiy ham bo'lishi mumkin.

Birinchi qatorda uchta butun son \(n, L, R\) (\(1 \le n \le 100000\), \(-10^{14} \le L \le R \le 10^{14}\)) beriladi. Ikkinchi qatorda \(n\) ta butun son \(a[1], a[2], \dots, a[n]\) (\(-10^9 \le a[i] \le 10^9\)) beriladi.

Yagona qatorda — yig'indisi \([L, R]\) oralig'ida bo'lgan qism massivlar sonini chop eting.

\(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.

Shahar arxitektura byurosida \(n\) ta bino balandligini ko'rsatuvchi \([b_1, b_2, \dots, b_n]\) massivi saqlanadi — bu yerda har bir \(b_i\) musbat butun son.

Har bir \(i\) \((1 \le i \le n)\) uchun \(g(b)\) massivini quyidagicha aniqlaymiz:

• Agar shunday \(j < i\) mavjud bo'lsaki, \(b_j < b_i\) bo'lsa, u holda \(g(b)_i = \max\limits_{j < i, \, b_j < b_i} j\). Ya'ni, \(g(b)_i\) — bu \(i\)-binodan chapda joylashgan, balandligi \(b_i\) dan qat'iy kichik bo'lgan eng o'ngdagi binoning raqami.
• Aks holda \(g(b)_i = 0\).

\([y_1, y_2, \dots, y_n]\) manfiy bo'lmagan butun sonlar massivini tiklanadigan massiv deb ataymiz, agar shunday \(b\) balandliklar massivi mavjud bo'lsaki, \(g(b) = y\) bo'lsa.

Yaqinda yomg'ir arxivdagi qog'ozlarni yuvib yubordi — uzunligi \(n\) bo'lgan \(x\) massivda ba'zi raqamlar o'chib ketdi (o'chgan joy \(-1\) bilan belgilanadi), qolganlari esa \(-1 \le x_i \le n\) shartini qanoatlantiradi. \(x\) dagi har bir \(-1\) ni \([0, n]\) oralig'idagi butun songa almashtirib, nechta usulda \(x\) ni tiklanadigan massivga aylantirish mumkinligini hisoblang. Javobni \(10^9 + 7\) ga bo'lgandagi qoldiqni chiqaring.

Har bir test bir nechta sinovdan iborat. Birinchi qatorda bitta butun son \(t\) \((1 \le t \le 10^3)\) — sinovlar soni. Keyin sinovlar tavsifi keladi.

Har bir sinovning birinchi qatorda \(x\) ning uzunligini bildiruvchi bitta butun son \(n\) \((1 \le n \le 5000)\) beriladi.

Ikkinchi qatorda \(n\) ta butun son \(x_1, x_2, \dots, x_n\) \((-1 \le x_i \le n)\) beriladi.

Barcha sinovlar bo'yicha \(n\) yig'indisi \(5000\) dan oshmasligi kafolatlanadi.

Har bir sinov uchun, \(x'\) tiklanadigan massiv bo'lgan \(x'\) massivlari sonini \(10^9 + 7\) bo'yicha qoldiqni ifodalovchi bitta butun son chiqaring.

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.