Bajnoki Ajándékok#243
A Bitakulandia bolygón minden évben megrendezésre kerül egy neves verseny, amit Miss M szervez — egy nemzetközi csapatbajnokság házigazdája —.
A versenyen Bitakulandia összes országának lakói részt vesznek. A bajnokság feladatok megoldásából is áll, amelyeknek nagyon érdekes a történetük, mint ez is, de csapatokban. A legjobb csapatok, a bajnokság eredményei alapján, díjakat kapnak.
Miss M végre megkapta a régóta várt ajándékokat a bajnokságra, amelyeket el kell küldeni a győzteseknek. Rájött, hogy sok az ajándék. És míg a bögrékkel és csomagokkal minden világos, addig a pólókkal probléma adódott. Minden csapatnak három tagja van, és mindegyikük egy-egy pólót rendelt szín és méret közül. De Miss M nem biztos abban, hogy minden győztes kívánságát teljesíteni tudja...
Ezért Miss M kifejlesztett egy algoritmust, amely szerint összeállítja az ajándékokat a csapatok számára.
Ha a kívánt méretű és színű póló még elérhető, akkor azt veszi.
Ellenkező esetben keres egy azonos méretű, de más színű pólót. Ha több is van, akkor a legkisebb számú színt választja.
Ellenkező esetben keres egy nagyobb méretű pólót a lehető legkisebbet a méretek között, de a csapat által kezdetben megadott szín prioritásával. Ha több is van, akkor a legkisebb számú színt választja.
Ha egyik sem megfelelő a maradék pólók közül, akkor a csapat által jelzett pólót hiányzóként rögzíti.
Miss M úgy döntött, hogy vissza kell küldenie a raktárba azokat a pólókat, amelyek feleslegessé váltak, és többet kell rendelnie azokból a pólókból, amelyeket hiányzóként rögzített, hogy minden bajnokságon résztvevő elégedett legyen. Hogy elkerülje az összes póló kézi szortírozását, Miss M megkér téged, hogy írj egy programot, amely:
Kimutatja, mely konkrét pólók váltak feleslegessé n \times m méretű táblázat formájában, ahol l_{ij} — az -edik színű és -edik méretű pólók száma, amelyek megmaradtak, miután ő kiosztotta a pólókat minden résztvevőnek.
Kimutatja, mely pólókat kell megrendelni n \times m méretű táblázat formájában, ahol n_{ij} — az -edik színű és -edik méretű pólók száma, amelyeket a résztvevők kértek, de a szervezők nem tudtak adni.
Az első sor két egész számot tartalmaz és (1 \leq n \leq 100, 1 \leq m \leq 6) — a pólók különböző színeinek és méreteinek száma, rendre.
A második sor elemet tartalmaz — a Miss M-hez szállított pólók méreteit. A méretek — XS, S, M, L, XL, 2XL. Garantált, hogy a méretek növekvő sorrendben vannak megadva.
Az ezt követő sor mindegyike egész számot tartalmaz t_{i1}, t_{i2}, \dots, t_{im} (0 \leq t_{ij} \leq 5 \cdot 10^{3}) — az -edik színű és -edik méretű pólók száma.
A következő sor egy egész számot tartalmaz (1 \leq k \leq 10^{5}) — a győztesek száma.
Az ezt követő sor mindegyike egy egész számot c_i (1 \leq c_i \leq n) és egy karaktert s_i tartalmaz — minden egyes póló színét és méretét, rendre. Garantált, hogy s_i egyike azoknak a méretnek, amelyeket megadtak.
A győztesek kéréseit pontosan a megadott sorrendben kell feldolgozni.
Az ezt követő sor mindegyikében írj ki egész számot l_{i1}, l_{i2}, \dots, l_{im} — az -edik színű és -edik méretű pólók száma, amelyek megmaradtak.
Az ezt követő sor mindegyikében írj ki egész számot n_{i1}, n_{i2}, \dots, n_{im} — az -edik színű és -edik méretű pólók száma, amelyeket meg kell vásárolni.
Példa
Tegyük fel, hogy van fehér pólónk (első index) és fekete pólónk (második index). Tehát van egy fehér pólónk S méretben, és három fehér pólónk M méretben. Három fekete pólónk van S méretben, és szintén három fekete pólónk XL méretben.
Vegyük figyelembe minden egyes győztest:
A győztesnek fehér pólóra van szüksége S méretben, van egy, tehát odaadjuk neki. Ez volt az utolsó ilyen póló.
A győztesnek fekete pólóra van szüksége XL méretben, van egy, tehát odaadjuk neki. Még kettő maradt.
A győztesnek fehér pólóra van szüksége M méretben, van egy, tehát odaadjuk neki. Még kettő maradt.
A győztesnek fekete pólóra van szüksége XL méretben, van egy, tehát odaadjuk neki. Még egy maradt.
A győztesnek fehér pólóra van szüksége M méretben, van egy, tehát odaadjuk neki. Még egy maradt.
A győztesnek fekete pólóra van szüksége M méretben, nincs egy sem. Azonban van egy fehér pólónk M méretben, tehát odaadjuk neki. Már nincs több fehér pólónk M méretben.
A győztesnek fehér pólóra van szüksége M méretben, nincs egy sem. Fekete pólónk M méretben sincs, tehát nem tudunk neki pólót adni M méretben. Ezért megnézzük a következő méretet — XL. A győztes fehér pólót szeretne kapni, de XL méretben sincs ilyen pólónk. Tehát adunk neki egy fekete pólót XL méretben. Ez volt az utolsó ilyen póló.
A győztesnek fekete pólóra van szüksége S méretben, van egy, tehát odaadjuk neki. Még egy maradt.
A győztesnek fehér pólóra van szüksége XL méretben, de nincs sem fehér, sem fekete pólónk ebben a méretben. Mivel nincs nagyobb méretű pólónk sem, nem tudjuk odaadni a résztvevőnek a jelzett pólót, ezért felírjuk a listára.
Két fekete pólónk maradt S méretben.
Nem tudtunk kiosztani egy fehér pólót sem XL méretben.