Ruudukon jokainen ruutu on alussa maalaamaton. Ruudukkoon suoritetaan operaatioita, joissa ruudukon rivi tai sarake maalataan tietyllä värillä. Jos jokin ruutu maalataan useita kertoja, sen väriksi tulee viimeisin väri.

Tehtäväsi on laskea jokaiselle värille, moniko ruutu on lopussa tämän värinen.

Syöte

Ensimmäisellä rivillä on neljä kokonaislukua n, m, k ja q: ruudukon korkeus ja leveys, värien määrä sekä operaatioiden määrä. Ruudukon rivit on numeroitu 1,2,\dots,n ja sarakkeet on numeroitu 1,2,\dots,m. Värit on numeroitu 1,2,\dots,k.

Seuraavat q riviä kuvaavat operaatiot, jotka maalaavat ruudukkoa. Jokaisen rivin muoto on jompikumpi seuraavista:

• "R i c": ruudukon rivi i maalataan värillä c
• "C i c": ruudukon sarake i maalataan värillä c

Operaatiot suoritetaan siinä järjestyksessä kuin ne on annettu syötteessä.

Tuloste

Tulosta jokaiselle värille c=1,2,\dots,k, monenko ruudun väri on lopussa c.

Esimerkki

Syöte:

3 4 4 4
R 1 1
C 3 4
R 2 2
R 1 1

Tuloste:

4 4 0 1

Selitys: Ruudukko maalataan seuraavasti:

Osatehtävä 1 (10 pistettä)

• 1\le n,m,k,q\le 10

Osatehtävä 2 (16 pistettä)

• 1\le n,m\le 10^9
• k=1
• 1\le q\le 2\cdot10^5

Osatehtävä 3 (32 pistettä)

• 1\le n,m\le 10^9
• 1\le k,q\le 2000

Osatehtävä 4 (42 pistettä)

• 1\le n,m\le 10^9
• 1\le k,q\le 2\cdot10^5