HODOŠAN

문제

Ima jedan mali krug velikih ljudi koji je nedavno proslavio ulazak u bračne vode jednoga od nas. Dio tog kruga i proslave bile su Martina i Paula koje su koristile svaku priliku za ples. Večer ćemo pamtiti i po bendu Romulus koji je tijekom proslave odsvirao ukupno $NN$ pjesama. Svaka je pjesma pripadala nekoj od $KK$ različitih vrsta glazbe.

Iako vole ples, Martina i Paula su plesale samo ako su obje znale plesati na vrstu glazbe kojoj pripada pjesma koju je trenutno svirao bend. Ako barem jedna od njih nije znala plesati na vrstu glazbe koja trenutno svira, prestale bi plesati i malo odmorile.

Ako znamo na kojih $MM$ vrste glazbe zna plesati Martina, a na kojih $PP$ Paula te kojoj vrsti glazbe pripada svaka od $NN$ odsviranih pjesama redom kojim ih je bend svirao, ispiši odgovore na sljedeća pitanja:

1. Uz koliko od $NN$ odsviranih pjesama su plesale Martina i Paula?
2. Koliki je bio najdulji niz pjesama uz koje su njih dvije plesale bez prestanka?

Sljedeće je jutro Ana, novi član našeg kruga, Martini i Pauli počela postavljati pitanja sljedećeg oblika: „Prijateljice $OO$, da si sinoć znala plesati na $XX$-tu vrstu glazbe, koliki bi bio najdulji niz pjesama uz koje bi vas dvije plesale bez prestanka?“

Ako je Ana postavila $QQ$ pitanja, ispiši tražene odgovore.

입력

U prvom retku su prirodni brojevi $NN$, $KK$, $MM$ (1 ≤ M ≤ K) i $PP$ (1 ≤ P ≤ K), brojevi iz teksta zadatka.

U drugom je retku niz od $MM$ prirodnih brojeva $M_{i}M\_i$ (1 ≤ M_i ≤ K), oznake vrste glazbe na koju Martina zna plesati.

U trećem je retku niz od $PP$ prirodnih brojeva $P_{i}P\_i$ (1 ≤ P_i ≤ K), oznake vrste glazbe na koju Paula zna plesati.

U četvrtom je retku niz od $NN$ prirodnih brojeva $R_{i}R\_i$ (1 ≤ R_i ≤ K), oznaka vrste glazbe kojoj pripada $ii$-ta pjesma koju je bend Romulus odsvirao na proslavi.

U petom je retku cijeli broj $QQ$, broj Aninih upita iz teksta zadatka.

U sljedećih $QQ$ redaka nalazi se znak $OO$ ($OO$ je „M“ i ili „P“) i prirodan broj $XX$ (1 ≤ X ≤ K), podaci iz teksta Aninog pitanja.

Napomena: za dodatna ograničenja obratite pozornost na sekciju bodovanje!

출력

U prvi redak ispiši odgovor na prvo pitanje iz teksta zadatka.

U drugi redak ispiši odgovor na drugo pitanje iz teksta zadatka.

U sljedećih $QQ$ redaka ispiši odgovor na $Q_{i}Q\_i$-to Anino pitanje.

힌트

Opis prvog probnog primjera: Martina zna plesati na prvu i drugu, a Paula na prvu i treću vrstu glazbe. Na svadbi su plesale uz tri pjesme: prvu, petu i osmu odsviranu pjesmu. Zato je duljina najduljeg niza pjesama uz koje su plesale jednaka jedan. Kad bi Martina znala plesati uz treću vrstu glazbe, ona i Paula bi mogle plesati uz četiri uzastopne pjesme – od pete do osme. Isto tako, kad bi Paula znala plesati na drugu vrstu glazbe, mogle bi plesati uz pet uzastopnih pjesmi. Na svadbi nije bila odsvirana nijedna pjesma četvrte vrste tako da su odgovori na posljednja dva Anina pitanja jednaki jedan.

8 4 2 2
1 2
1 3
1 2 2 2 1 3 3 1
4
M 3
P 2
M 4
P 4

3
1
4
5
1
1

5 5 3 4
1 2 5
2 3 4 5
1 2 3 4 5
3
P 1
M 3
M 4

2
1
2
2
2

10 4 4 3
1 2 3 4
2 3 4
4 1 1 2 2 1 1 2 2 3
1
P 1

6
3
10