Bajnoki Ajándékok
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $$$n$$$ szín és $$$m$$$ 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.

  1. Ha a kívánt méretű és színű póló még elérhető, akkor azt veszi.
  2. 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.
  3. 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.
  4. 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:

  1. 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 $$$i$$$-edik színű és $$$j$$$-edik méretű pólók száma, amelyek megmaradtak, miután ő kiosztotta a pólókat minden résztvevőnek.
  2. Kimutatja, mely pólókat kell megrendelni $$$n \times m$$$ méretű táblázat formájában, ahol $$$n_{ij}$$$ — az $$$i$$$-edik színű és $$$j$$$-edik méretű pólók száma, amelyeket a résztvevők kértek, de a szervezők nem tudtak adni.

Input

Az első sor két egész számot tartalmaz $$$n$$$ és $$$m$$$ ($$$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 $$$m$$$ 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ő $$$n$$$ sor mindegyike $$$m$$$ egész számot tartalmaz $$$t_{i1}, t_{i2}, \dots, t_{im}$$$ ($$$0 \leq t_{ij} \leq 5 \cdot 10^{3}$$$) — az $$$i$$$-edik színű és $$$j$$$-edik méretű pólók száma.

A következő sor egy egész számot tartalmaz $$$k$$$ ($$$1 \leq k \leq 10^{5}$$$) — a győztesek száma.

Az ezt követő $$$k$$$ 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$$$ méretnek, amelyeket megadtak.

A győztesek kéréseit pontosan a megadott sorrendben kell feldolgozni.

Output

Az ezt követő $$$n$$$ sor mindegyikében írj ki $$$m$$$ egész számot $$$l_{i1}, l_{i2}, \dots, l_{im}$$$ — az $$$i$$$-edik színű és $$$j$$$-edik méretű pólók száma, amelyek megmaradtak.

Az ezt követő $$$n$$$ sor mindegyikében írj ki $$$m$$$ egész számot $$$n_{i1}, n_{i2}, \dots, n_{im}$$$ — az $$$i$$$-edik színű és $$$j$$$-edik méretű pólók száma, amelyeket meg kell vásárolni.

Example

Input
2 3
S M XL
1 3 0
3 0 3
9
1 S
2 XL
1 M
2 XL
1 M
2 M
1 M
2 S
1 XL
Output
0 0 0 
2 0 0 
0 0 1 
0 0 0 

Note

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:

  1. 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ó.
  2. A győztesnek fekete pólóra van szüksége XL méretben, van egy, tehát odaadjuk neki. Még kettő maradt.
  3. 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.
  4. A győztesnek fekete pólóra van szüksége XL méretben, van egy, tehát odaadjuk neki. Még egy maradt.
  5. 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.
  6. 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.
  7. 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ó.
  8. A győztesnek fekete pólóra van szüksége S méretben, van egy, tehát odaadjuk neki. Még egy maradt.
  9. 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.