Muallif: shoyim

E. Mandat

Vaqt limiti: 2000 ms Xotira limiti: 256 mb

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

Har bir \(i-\)yo'nalish uchun grant o'rinlari soni \(g_i\) va kontrakt o'rinlari soni \(c_i\) oldindan ma'lum.

Har bir abituriyent quyidagi ma'lumotlarga 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 — abituriyent tanlagan yo'nalishlar, ustuvorlik tartibida (ro'yxatdagi birinchisi eng afzal).

Taqsimlash tartibi

1. Barcha abituriyentlar ball bo'yicha kamayish tartibida navbatga qo'yiladi. Agar 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 tanlovda ham bo'sh grant o'rni topilmasa, tanlovlarini yana boshidan tartib bo'yicha ko'rib chiqadi, 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'rligini 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

Birinchi qatorda ikkita butun son \(n, m\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le m \le 10^4\)) beriladi.

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

Keyingi \(n\) ta abituriyentning har biri uchun \(2\) qatordan iborat ma'lumot beriladi:

• \(1-\)qatorda: ball, turi (\(0\) yoki \(1\)) va \(k\) (\(1 \le k \le 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'sh joy 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) \(\to\) shu yerga grant bilan joylashadi.
• \(85\) ball (yo'nalish-ustuvor, tanlovlar: \(1, 2\)): \(1-\)yo'nalishda grant bo'shligini tekshiradi — bo'sh (\(1\) ta) \(\to\) 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) \(\to\) grant topilmadi. Qayta ko'rib, kontrakt izlaydi — \(1-\)yo'nalishda kontrakt bo'sh (\(1\) ta) \(\to\) shu yerga kontrakt bilan joylashadi.
• \(70\) ball (yo'nalish-ustuvor, tanlovlar: \(3, 2\)): \(3-\)yo'nalishda grant yo'q, kontrakt bo'sh (\(1\) ta) \(\to\) shu yerga kontrakt bilan joylashadi.