E. Mandat

Davlat Test Markazi (Agentlik) tomonidan n ta abituriyent va m ta yo'nalish bo'yicha mandat (grant va kontrakt o'rinlarini) taqsimlash kerak.

Har bir yo'nalish uchun grant o'rinlari soni (g) va kontrakt o'rinlari soni (c) oldindan ma'lum.

Har bir abituriyent quyidagilarga ega:
- ball — uning test balli (butun son);
- ustuvorlik turi — 0 (grant-ustuvor) yoki 1 (yo'nalish-ustuvor);
- 1 dan 5 gacha bo'lgan tanlovlar ro'yxati — u tanlagan yo'nalishlar, ustuvorlik tartibida (birinchisi eng afzal).

Taqsimlash quyidagi tartibda amalga oshiriladi:

1. Barcha abituriyentlar ball bo'yicha kamayish tartibida navbatga qo'yiladi (ballari teng bo'lsa, kirish faylida oldinroq berilgan abituriyent ustun turadi).
2. Har bir abituriyent navbatga yetganda, o'z ustuvorlik turiga qarab quyidagicha joylashtiriladi:

• Grant-ustuvor (0): avval o'zining BARCHA tanlovlarini tartib bo'yicha ko'rib chiqadi va bo'sh grant o'rni bor birinchi yo'nalishga joylashadi. Agar birorta tanlovida ham bo'sh grant o'rni topilmasa, tanlovlarini yana tartib bo'yicha ko'rib chiqib, bo'sh kontrakt o'rni bor birinchi yo'nalishga joylashadi.
• Yo'nalish-ustuvor (1): tanlovlarini tartib bo'yicha birma-bir ko'rib chiqadi; har bir tanlov uchun avval grant o'rni bo'shligini tekshiradi (bo'sh bo'lsa — o'sha yerga grant asosida joylashadi va to'xtaydi), bo'lmasa kontrakt o'rnini tekshiradi (bo'sh bo'lsa — kontrakt asosida joylashadi va to'xtaydi). Agar bu tanlovda ikkalasi ham band bo'lsa, keyingi tanlovga o'tadi.

3. Agar abituriyentning barcha tanlovlaridagi o'rinlar band bo'lsa, u hech qayerga joylashmaydi.

Har bir abituriyent uchun (kirishda berilgan asl tartibda) qaysi yo'nalishga va qanday asosda (grant yoki kontrakt) joylashganini aniqlang.

Kiruvchi ma'lumotlar

1-qatorda ikkita butun son: n va m (\(1 ≤ n ≤ 2×10^5\), \(1 ≤ m ≤ 10^4\)).

Keyingi m qatorning har birida ikkita butun son \(g_i \)va \(c_i \)(\(0 ≤ g_i, c_i ≤ 10^5\)) — i-yo'nalishning grant va kontrakt o'rinlari soni.

Keyingi n ta abituriyentning har biri uchun 2 qatordan iborat ma'lumot:

• 1-qatorda: ball, turi (0 yoki 1) va k (\(1 ≤ k ≤ 5\)) — ball, ustuvorlik turi va tanlovlar soni;
• 2-qatorda: k ta son — tanlangan yo'nalishlar raqamlari (1 dan m gacha), ustuvorlik tartibida, takrorlanmaydi.

Chiquvchi ma'lumotlar

Har bir abituriyent uchun (kirishdagi tartibda), alohida qatorda:
- agar u biror yo'nalishga joylashgan bo'lsa — yo'nalish raqami va grant yoki kontrakt so'zini, bo'shliq bilan ajratib;
- aks holda — yagona -1.

Misollar

1

4 3
1 1
1 0
0 1
90 0 3
2 1 3
85 1 2
1 2
80 0 2
1 3
70 1 2
3 2

2 grant
1 grant
1 kontrakt
3 kontrakt

2

1 1
1 0
150 0 1
1

1 grant

Izoh

 Abituriyentlar ball bo'yicha kamayish tartibida ko'riladi: 90, 85, 80, 70.
- 90 ball (grant-ustuvor, tanlovlar: 2,1,3): avval barcha tanlovlaridan grant izlaydi — 2-yo'nalishda grant bo'sh (1 ta) → shu yerga grant bilan joylashadi.
- 85 ball (yo'nalish-ustuvor, tanlovlar: 1,2): 1-yo'nalishda grant bo'shligini tekshiradi — bo'sh (1 ta) → shu yerga grant bilan joylashadi.
- 80 ball (grant-ustuvor, tanlovlar: 1,3): grant izlaydi — 1-yo'nalish grant band, 3-yo'nalishda grant yo'q (0 ta) → grant topilmadi. Qayta ko'rib, kontrakt izlaydi — 1-yo'nalishda kontrakt bo'sh (1 ta) → shu yerga kontrakt bilan joylashadi.
- 70 ball (yo'nalish-ustuvor, tanlovlar: 3,2): 3-yo'nalishda grant yo'q, kontrakt bo'sh (1 ta) → shu yerga kontrakt bilan joylashadi.