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]
Yechim yuborish uchun tizimga kiring yoki ro'yxatdan o'ting.

Navbatdagi musobaqa

Biriktirilgan musobaqa

SamCoding Round 11 (Div. 1)

Natijalar