Ketma-ket bir nechta butun son kiritiladi — har bir qatorda bittadan. Kiritish jarayoni maxsus tugash belgisi — \(0\) soni kiritilganda tugaydi (\(0\) ning o'zi yig'indiga qo'shilmaydi va bu oxirgi kiritma hisoblanadi). Kiritilgan barcha sonlarning yig'indisini toping.

Bir nechta qatorda, har birida bitta butun \(n\) son beriladi (\(-1000 \le n \le 1000\)). Ketma-ketlik \(0\) soni kiritilishi bilan tugaydi.

\(0\) dan oldingi barcha sonlarning yig'indisini chiqaring.

Fibonachchi ketma-ketligi quyidagicha aniqlanadi:

\(F(1) = 1\), \(F(2) = 1\), va \(n \ge 3\) uchun \(F(n) = F(n-1) + F(n-2)\) (ya'ni har bir keyingi son, oldingi ikkita sonning yig'indisiga teng).

Ketma-ketlikning boshlanishi: \(1, 1, 2, 3, 5, 8, \ldots\)

Butun son \(n\) berilgan. \(F(n)\) ni toping.

Yagona qatorda butun son \(n\) beriladi (\(1 \le n \le 50\)).

\(F(n)\) ning qiymatini chiqaring.

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.

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.

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.