Sizga \(n\) ta butun sondan iborat \(a_1, a_2, \dots, a_n\) massiv berilgan. Shu massivning bo'sh bo'lmagan ketma-ket bo'lagini (subarray, ya'ni \(a_l, a_{l+1}, \dots, a_r\) ko'rinishidagi, \(1 \le l \le r \le n\)) tanlang, shunday qilib uning elementlari yig'indisi eng katta bo'lsin. Shu maksimal yig'indini toping.

Diqqat: Bo'lak bo'sh bo'lishi mumkin emas — kamida bitta element tanlanishi shart (massivdagi barcha sonlar manfiy bo'lsa ham).

Birinchi qatorda \(n\) (\(1 \le n \le 10^6\)) soni 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 — maksimal bo'lak yig'indisini chiqaring.

Sizda \(n\) ta ish bor. \(i\)-ish \(l_i\) vaqtda boshlanadi va \(r_i\) vaqtda tugaydi (\(l_i < r_i\)). Bir vaqtning o'zida faqat bitta ish bajarilishi mumkin — ya'ni tanlangan ishlar orasida vaqt oralig'i kesishmasligi kerak (bitta ish tugagan vaqtda boshqasi boshlansa, bu kesishish hisoblanmaydi). Maksimal nechta ishni bajarish mumkinligini toping.

Birinchi qatorda \(n\) (\(1 \le n \le 10^6\)) soni beriladi. Keyingi \(n\) ta qatorning har birida ikkita butun son \(l_i, r_i\) (\(1 \le l_i < r_i \le 10^9\)) beriladi.

Yagona qatorda — bajarish mumkin bo'lgan maksimal ishlar sonini chiqaring.

Kengligi \(2\) va uzunligi \(n\) bo'lgan to'g'ri to'rtburchak panel berilgan (ya'ni \(2 \times n\) o'lchamli katakcha panel). Panelni to'liq, bo'sh joy qoldirmasdan va bir-birining ustiga chiqmasdan, \(1 \times 2\) o'lchamli domino bo'laklari bilan qoplamoqchisiz (har bir domino gorizontal yoki vertikal joylashishi mumkin).

\(q\) ta so'rov beriladi, har birida \(n\) soni beriladi. Har bir so'rov uchun panelni qoplashning nechta xil usuli borligini \(10^9+7\) ga bo'lgandagi qolig'ini toping.

Eslatma: agar \(n=0\) bo'lsa, panel bo'sh hisoblanadi va uni qoplashning yagona (hech narsa qo'ymaslik) usuli bor deb hisoblang.

Birinchi qatorda \(q\) (\(1 \le q \le 10^5\)) soni beriladi. Ikkinchi qatorda \(q\) ta butun son \(n_1, \dots, n_q\) (\(0 \le n_i \le 10^{18}\)) beriladi.

\(q\) qatorda — har bir so'rov uchun javobni chiqaring (har birini alohida qatorda).

Yosh arxeolog Laylo ikkita turli qazishma hududidan topilgan qadimgiy bitiklarni (yozuvlarni) tekshirmoqda. Ikkala bitik ham faqat kichik lotin harflaridan iborat maxsus belgilar tizimida bitilgan. Agar bu ikki bitikda bir xil tartibda ketma-ket takrorlanadigan yetarlicha uzun umumiy parcha topilsa, bu ular bir xil qadimiy sivilizatsiyaga tegishli ekanligidan dalolat beradi.

Laylaga yordam bering: ikkita \(s\) (uzunligi \(n\)) va \(t\) (uzunligi \(m\)) bitik matni berilgan. Ikkalasida ham birgalikda uchraydigan eng uzun umumiy qism-satr (ketma-ket parcha)ning uzunligini toping. Agar umuman umumiy parcha (bo'sh bo'lmagan) topilmasa, \(0\) chiqaring.

Birinchi qatorda ikkita butun son \(n\), \(m\) (\(1 \le n, m \le 2 \times 10^5\)) — bitiklar uzunligi. Ikkinchi qatorda birinchi bitik matni \(s\), uchinchi qatorda ikkinchi bitik matni \(t\) beriladi.

Yagona qatorda — eng uzun umumiy qism-satr uzunligini chiqaring.

Sizda \(n\) ta buyum bor, har birining og'irligi \(w_i\) va qiymati \(v_i\). Yukxaltaning sig'imi \(W\). Yukxaltaga og'irliklari yig'indisi \(W\) dan oshmaydigan buyumlarni tanlab (har bir buyum yo olinadi, yo olinmaydi — takrorlab bo'lmaydi), tanlangan buyumlar qiymatining yig'indisini maksimal qiling.

Birinchi qatorda ikkita butun son \(n\) va \(W\) (\(1 \le n \le 2000\), \(1 \le W \le 10^9\)) beriladi. Keyingi \(n\) ta qatorning har birida ikkita butun son \(w_i, v_i\) (\(1 \le w_i \le 10^9\), \(1 \le v_i \le 60000\),  kafolatlanadiki \(v_1+\dots+v_n \le 60000\)) beriladi.

Yagona qatorda — maksimal mumkin bo'lgan qiymat yig'indisini chiqaring.

Qadimgi shohlikda \(n\) ta pochta bekati bor, ular \(m\) ta yo'l orqali juft-juft bog'langan (har bir yo'l ikki tomonlama, ya'ni ikkala yo'nalishda ham yurish mumkin). \(i\) - yo'ldan o'tish uchun aynan \(w_i\) soat vaqt kerak.

Chopar \(1\) - bekatdan xat olib, uni \(n\) - bekatga eltishi kerak. U bekatlar orasida istalgan yo'llar zanjiri orqali harakatlanishi mumkin (bir nechta yo'lni ketma-ket bosib o'tib). Choparning \(n\) - bekatga yetib borishi uchun ketadigan eng kam umumiy vaqtni toping. Agar chopar umuman \(n\) - bekatga yetib bora olmasa, \(-1\) chiqaring.

Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n \le 2\times10^5\), \(0 \le m \le 4\times10^5\)) beriladi. Keyingi \(m\) ta qatorning har birida uchta butun son \(u_i, v_i, w_i\) (\(1 \le w_i \le 10^9\), \(1 \le u_i, v_i \le n\), \(u_i \neq v_i\)) beriladi — \(u_i\) va \(v_i\) bekatlar orasida o'tish \(w_i\) soat vaqt oladigan yo'l borligini bildiradi.

Yagona qatorda — choparning \(n\) - bekatga yetib borishi uchun ketadigan eng kam vaqtni (yoki \(-1\)) chiqaring.

\(n\) ta elementdan iborat \(a_1, a_2, \dots, a_n\) massiv berilgan. Uni aynan \(K\) ta bo'sh bo'lmagan, ketma-ket (uzluksiz) qismga bo'lish kerak. Agar bo'laklar yig'indisi mos ravishda \(s_1, s_2, \dots, s_K\) bo'lsa, bo'linishning narxi \(s_1^2 + s_2^2 + \dots + s_K^2\) ga teng. Massivni aynan \(K\) ta qismga bo'lishning eng kichik mumkin bo'lgan narxini toping.

Birinchi qatorda ikkita butun son \(n\) va \(K\) (\(1 \le n \le 1000\), \(1 \le K \le n\)) beriladi. Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6\)) beriladi.

Yagona qatorda — massivni aynan \(K\) ta uzluksiz qismga bo'lishning eng kichik narxini chiqaring.