Bobur darsga kechikyapti! U ko'p qavatli maktabning \(a\)-qavatida turibdi, darsi esa \(b\)-qavatda bo'ladi.

Bobur zinapoyadan yurishi yoki liftga chiqishi mumkin. Zinapoyadan bir qavat yuqoriga chiqish yoki pastga tushish uchun \(x\) soniya ketadi.

Lift hozir \(c\)-qavatda turibdi. Bobur tugmani bosgach, lift avval \(c\)-qavatdan Boburning oldiga, ya'ni \(a\)-qavatga keladi, so'ng uni \(b\)-qavatga olib boradi. Lift bir qavatni \(y\) soniyada o'tadi.

Bobur darsga eng tez yetib boradigan yo'lni tanlaydi. U darsga eng kamida necha soniyada yetib borishini toping.

Yagona qatorda beshta butun son \(a\), \(b\), \(c\), \(x\) va \(y\) berilgan (\(1 \le a, b, c \le 100\), \(1 \le x, y \le 100\)).

Bitta son — Bobur darsga yetib borishi uchun kerak bo'ladigan eng kam vaqt (soniyalarda).

Dilnozaga tug'ilgan kunida aqlli bilaguzuk sovg'a qilishdi. Bilaguzuk har kuni nechta qadam yurilganini sanaydi.

Dilnoza o'ziga maqsad qo'ydi: har kuni kamida \(k\) qadam yurish. Agar u maqsadni ketma-ket bir necha kun bajarsa, bilaguzuk ekranida "olov" belgisi paydo bo'ladi va uning yonida shu ketma-ketlik necha kun davom etayotgani yoziladi. Biror kun maqsad bajarilmasa, hisob yana noldan boshlanadi.

Dilnoza \(n\) kun davomida bilaguzukni taqib yurdi. \(i\)-kuni u \(a_i\) qadam yurgan. U eng uzun olovli seriyasi necha kun davom etganini bilmoqchi, ya'ni ketma-ket nechta kun davomida u har kuni kamida \(k\) qadam yurgan.

Birinchi qatorda ikkita butun son \(n\) va \(k\) (\(1 \le n,k \le 10^5\)) — kunlar soni va kunlik maqsad.

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^5\)) — har bir kuni yurilgan qadamlar soni.

Bitta son — eng uzun olovli seriyaning uzunligi. Agar Dilnoza maqsadni birorta ham kun bajarmagan bo'lsa, \(0\) chiqaring.

Bobojonning bobosi hali ham tugmali eski telefondan foydalanadi. Unda SMS yozish oson emas: har bir tugmaga bir nechta harf biriktirilgan, kerakli harfni chiqarish uchun tugmani bir necha marta bosish kerak.

Tugmalarga harflar quyidagi rasmdagidek biriktirilgan:

Masalan, 'a' harfi uchun '2' tugmasini bir marta, 'b' uchun ikki marta, 'c' uchun uch marta bosish kerak. 's' harfi uchun esa '7' tugmasini to'rt marta bosish kerak.

Har bir bosish roppa-rosa 1 soniya oladi. Agar navbatdagi harf oldingi harf bilan bir xil tugmada joylashgan bo'lsa, telefon oldingi harfni "qabul qilishi" uchun yana 1 soniya kutish kerak bo'ladi. Aks holda telefon yangi harfni oldingisining davomi deb o'ylaydi.

Bobo nevarasiga \(s\) so'zini yubormoqchi. Bu so'zni yozish uchun necha soniya ketishini toping.

Yagona qatorda \(s\) satri berilgan (\(1 \le |s| \le 10^5\)). U faqat kichik lotin harflaridan iborat.

Bitta son — so'zni yozish uchun ketadigan vaqt (soniyalarda).

Informatika xonasida bitta printer bor. Dars tugashiga oz qolganda \(n\) nafar o'quvchi uyga vazifasini chop etish uchun printerga keldi. \(i\)-o'quvchining hujjatini chop etish \(t_i\) soniya davom etadi.

Printer bir vaqtda faqat bitta hujjatni chop etadi. Hujjatlar ketma-ket, orada tanaffussiz chop etiladi, birinchi hujjat \(0\)-soniyada boshlanadi. Har bir o'quvchi o'z hujjati to'liq chop etilib bo'lgach darhol uyga ketadi. O'quvchining kutish vaqti deb, \(0\)-soniyadan uning hujjati tayyor bo'lguncha o'tgan vaqtga aytiladi.

O'qituvchi hujjatlarni istalgan tartibda chop etishi mumkin. U barcha o'quvchilarning kutish vaqtlari yig'indisi eng kichik bo'lishini xohlaydi. Shu eng kichik yig'indini toping.

Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — o'quvchilar soni.

Ikkinchi qatorda \(n\) ta butun son \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^6\)) — har bir hujjatni chop etish vaqti.

Bitta son — kutish vaqtlari yig'indisining eng kichik qiymati.

Usta Akmal kvadrat gilamlar to'qiydi. Har bir gilam kvadrat kataklardan iborat bo'lib, har bir katak qora yoki oq ip bilan to'qiladi. Usta gilamlarni darajalar bo'yicha to'qiydi.

\(0\)-darajali gilam bitta qora katakdan iborat. \(n\)-darajali gilamni to'qish uchun usta \((n-1)\)-darajali gilamdan \(9\) ta nusxa oladi va ularni \(3 \times 3\) jadval ko'rinishida joylashtiradi. Faqat markazdagi nusxa o'rniga xuddi shu o'lchamdagi butunlay oq kvadrat qo'yiladi. Shunday qilib, \(n\)-darajali gilam \(3^n \times 3^n\) o'lchamli bo'ladi.

Quyidagi rasmda chapdan o'ngga \(0\)-, \(1\)-, \(2\)- va \(3\)-darajali gilamlar ko'rsatilgan:

Gilam qatorlari yuqoridan pastga, ustunlari chapdan o'ngga \(1\) dan \(3^n\) gacha raqamlangan. Ustaning shogirdi \(q\) ta savol berdi: "\(n\)-darajali gilamning \(r\)-qatori va \(c\)-ustunidagi katak qanday rangda?" Har bir savolga javob bering.

Birinchi qatorda bitta butun son \(q\) (\(1 \le q \le 10^5\)) — savollar soni.

Keyingi \(q\) ta qatorning har birida uchta butun son \(n\), \(r\) va \(c\) berilgan (\(0 \le n \le 30\), \(1 \le r, c \le 3^n\)).

Har bir savol uchun alohida qatorda bitta belgi chiqaring: katak qora bo'lsa '#', oq bo'lsa '.' (nuqta).

\(n\) ta uch va \(m\) ta qirradan iborat yo'naltirilmagan graf berilgan. Uchlar \(1\) dan \(n\) gacha raqamlangan. Grafda bir xil ikki uchni tutashtiruvchi bir nechta qirra bo'lishi mumkin, lekin uchni o'zi bilan tutashtiruvchi qirra yo'q. Graf bog'liq bo'lmasligi ham mumkin.

Grafning har bir uchini oq yoki qora rangga bo'yash kerak. Bunda har bir qirraning ikki uchi har xil rangda bo'lishi shart.

Shunday bo'yashlar ichida qora uchlar soni eng kam bo'lganini toping va shu sonni chiqaring. Agar grafni bu shartga ko'ra umuman bo'yab bo'lmasa, \(-1\) chiqaring.

Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n \le 2 \times 10^5\), \(0 \le m \le 2 \times 10^5\)) — uchlar va qirralar soni.

Keyingi \(m\) ta qatorning har birida ikkita butun son \(u\) va \(v\) (\(1 \le u, v \le n\), \(u \ne v\)) berilgan — \(u\) va \(v\) uchlarni tutashtiruvchi qirra.

Bitta son — qora uchlarning eng kam soni yoki \(-1\).

Imtihon kuni o'qituvchi o'quvchilarni bir-biridan ko'chirmasliklari uchun maxsus tartibda o'tqazmoqchi: hech qaysi ikki o'quvchi yonma-yon stullarda o'tirmasligi kerak.

Imtihon ikki xil xonada o'tkaziladi. Birinchi turdagi xonada \(n\) ta stul bir qatorga terilgan va chapdan o'ngga \(1\) dan \(n\) gacha raqamlangan. Bunda \(i\)-stul faqat \((i-1)\)- va \((i+1)\)-stullar bilan yonma-yon. Ikkinchi turdagi xonada \(n\) ta stul dumaloq stol atrofida joylashgan. Bu holda ham \(i\)-stul \((i-1)\)- va \((i+1)\)-stullar bilan yonma-yon, lekin qo'shimcha ravishda \(1\)- va \(n\)-stullar ham yonma-yon bo'ladi.

O'qituvchi \(k\) ta o'quvchini o'tqazishi kerak. Faqat qaysi stullar band bo'lishi muhim, ya'ni o'quvchilarning o'zaro o'rni almashsa, bu yangi usul hisoblanmaydi. O'tqazish usullari sonini toping. Javob juda katta bo'lishi mumkin, shuning uchun uni \(10^9 + 7\) ga bo'lgandagi qoldig'ini chiqaring.

O'qituvchiga \(q\) ta savol bo'yicha yordam bering.

Birinchi qatorda bitta butun son \(q\) (\(1 \le q \le 10^5\)) — savollar soni.

Keyingi \(q\) ta qatorning har birida uchta butun son \(t\), \(n\) va \(k\) berilgan (\(t \in \{1, 2\}\), \(3 \le n \le 10^6\), \(0 \le k \le n\)). Bunda \(t = 1\) stullar qatorga terilganini, \(t = 2\) esa dumaloq stol atrofida joylashganini bildiradi.

Har bir savol uchun alohida qatorda bitta son chiqaring: o'tqazish usullari sonining \(10^9 + 7\) ga bo'lgandagi qoldig'i.