Muallif: __thecrash__
E. Javondagi kitoblar
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
Kutubxonada ikki qavatli javon bor. Yuqori qavatda chapdan o'ngga \(n\) ta kitob, pastki qavatda esa \(m\) ta kitob turibdi. Har bir kitobning muqovasida raqam yozilgan. Yuqori qavatdagi kitoblar raqamlari \(a_1, a_2, \ldots, a_n\), pastki qavatdagilar esa \(b_1, b_2, \ldots, b_m\). Barcha \(n + m\) ta kitobning raqamlari har xil va ular \(1\) dan \(n + m\) gacha bo'lgan sonlardan iborat.
Kutubxonaga yangi robot-kutubxonachi keltirildi va u \(k\) qadam ishlaydi. Har bir qadamda robot yuqori qavatdan bitta kitobni va pastki qavatdan bitta kitobni oladi. \(1\)-qadamda u har ikki qavatning \(1\)-kitobini oladi, \(2\)-qadamda \(2\)-kitobini va hokazo. Qavatdagi kitoblar tugasa, robot shu qavatning \(1\)-kitobiga qaytadi. Masalan, yuqori qavatda \(2\) ta kitob bo'lsa, robot u yerdan navbat bilan \(1, 2, 1, 2, \ldots\) kitoblarni oladi. Agar yuqoridan olingan kitobning raqami pastdan olinganidan katta bo'lsa, robot ikki kitobning o'rnini almashtiradi, aks holda hech narsa qilmaydi.
Robot \(k\) qadamni tugatgandan keyin javonda kitoblar qanday tartibda turishini aniqlang.
Kiruvchi ma'lumotlar
Birinchi qatorda bitta butun son \(t\) (\(1 \le t \le 10^4\)), testlar soni. Keyin testlar ketma-ket beriladi.
Har bir testning birinchi qatorida uchta butun son \(n\), \(m\) va \(k\) (\(1 \le n, m \le 2 \cdot 10^5\), \(0 \le k \le 10^{18}\)).
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\), uchinchi qatorda \(m\) ta butun son \(b_1, b_2, \ldots, b_m\) berilgan. Bu \(n + m\) ta son \(1\) dan \(n + m\) gacha bo'lgan sonlarning o'rin almashtirishi ekani kafolatlanadi.
Barcha testlar bo'yicha \(n + m\) yig'indisi \(2 \cdot 10^5\) dan oshmaydi.
Chiquvchi ma'lumotlar
Har bir test uchun ikki qator chiqaring, birinchisida yuqori qavatdagi, ikkinchisida pastki qavatdagi kitoblar raqamlarini chapdan o'ngga tartibda.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
3 2 3 5 4 2 5 1 3 1 4 6 5 3 4 1 2 3 2 4 5 1 4 2 3 |
2 1 5 3 4 1 5 4 3 2 2 1 4 5 3 |
Izoh
Birinchi testda robot quyidagicha ishlaydi.
| Qadam | Yuqoridagi kitob | Pastdagi kitob | Solishtirish | Natija | Yuqori qavat | Pastki qavat |
|---|---|---|---|---|---|---|
| 1 | 1-kitob (4) | 1-kitob (5) | 4<5 | o’zgarmaydi | [4, 2] | [5, 1, 3] |
| 2 | 2-kitob (2) | 2-kitob (1) | 2>1 | almashadi | [4, 1] | [5, 2, 3] |
| 3 | 1-kitob (4) | 3-kitob (3) | 4>3 | almashadi | [3, 1] | [5, 2, 4] |
| 4 | 2-kitob (1) | 1-kitob (5) | 1<5 | o’zgarmaydi | [3, 1] | [5, 2, 4] |
| 5 | 1-kitob (3) | 2-kitob (2) | 3>2 | almashadi | [2, 1] | [5, 3, 4] |