Muallif: __thecrash__
E. Gilam naqshi
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
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.
Kiruvchi ma'lumotlar
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\)).
Chiquvchi ma'lumotlar
Har bir savol uchun alohida qatorda bitta belgi chiqaring: katak qora bo'lsa '#', oq bo'lsa '.' (nuqta).
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
5 1 2 2 1 1 3 2 2 5 2 4 4 2 4 1 |
. # . . # |
2 |
2 15 7174454 7174454 15 1 1 |
. # |
Izoh
Birinchi misoldagi barcha savollarning javobini rasmdan ko'rish mumkin. Masalan, \(2\)-darajali gilamda \((2, 5)\) katak oq, chunki u yuqori o'rtadagi \(1\)-darajali nusxaning markazida joylashgan.
Ikkinchi misolda \(15\)-darajali gilamning o'lchami \(3^{15} = 14348907\). Birinchi savoldagi katak butun gilamning aynan markazida, shuning uchun oq.