sabin

Dat fiind ca mallu' nu era cea mai apropiată locaţie, Sabin s-a hotărât să petreacă ceva timp la bibliotecă. Aici el a dat peste două rafturi cu cărţi.

Primul raft conține N compartimente de cărţi, fiecare compartiment având același număr de cărți, K. Cel de-al doilea raft conţine un singur compartiment cu M cărţi. Toate cărțile din ambele rafturi au titlurile formate din exact P caractere mici ale alfabetului englez.

Un prefix al unui șir de caractere se definește ca o subsecvență a șirului care începe de pe prima poziție a acestuia. Definim cel mai mare prefix comun (maxprefix) a două șiruri de caractere ca fiind lungimea celei mai lungi secvențe de caractere care este prefix și al primului șir și al celui de-al doilea.

Fiind date două compartimente de titluri de cărti $A = [c_1, c_2, ..., c_K]$ şi $B = [d_1, d_2, .., d_K]$ definim gradul de similitudine al acestora ca fiind $min(maxprefix(c_1, d_1), maxprefix(c_2, d_2), …, maxprefix(c_K, d_K))$.

Sabin ar dori să scoată K cărţi din al doilea raft şi să găsească un compartiment din primul raft pentru care gradul de similitudine să aibă o valoare dată.

Ca să intrați în grațiile lui Sabin având la dispozitie cele două rafuri de cărți, trebuie să răspundeți la Q întrebări de forma: “Fiind date K cărţi din al doilea raft, găsiţi toate compartimentele din primul raft care au gradul de similitudine cu compartimentul dat exact X şi afişaţi numărul lor”.

Data de intrare

Pe prima linie a fișierului sabin.in se află N, K, M, P și Q. Următoarele N linii descriu mulțimile de cărți din primul raft: cea de-a i-a linie va conține K șiruri de caractere de lungime P, despărţite printr-un spaţiu, reprezentând cărțile din cel de-al i-lea compartiment. Următoarea linie descrie cele M cărţi din al doilea raft.

Următoarele Q linii vor conține fiecare K + 1 numere. Primul număr reprezintă gradul de similitudine dorit X. Următoarele K numere reprezintă indicii cărţilor din al doilea raft care formează noul compartiment.

Date de ieșire

Fișierul sabin.out va conține Q linii, câte una pentru fiecare întrebare din fișierul de intrare, reprezentând numărul de compartimente din primul raft care satisfac cerința dată.

Restricții

• 1 ≤ N ≤ 20 000
• 1 ≤ M ≤ 30 000
• 1 ≤ Q ≤ 20 000
• 1 ≤ K ≤ 15
• 1 ≤ P ≤ 30
• 0 ≤ X ≤ 30

Exemplu

sabin.in

4 2 6 4 4
abcd trzs
gefd fasf
gefa fasx
fxxx txxx
affx trfs abxx trxx gefa fasf
1 1 2
1 3 4
3 5 6
1 6 2

sabin.out

1
0
2
1

Explicație

Numerele de pe prima linie a fișierului de intrare reprezintă N = 4, K = 2, M = 6, P = 4 și Q = 4.

Primul raft este format din N = 4 compartimente. Fiecare compartiment are K = 2 cărţi, formate din P = 4 caractere: [abcd, trzs] [gefd, fasf] [gefa, fasx], [fxxx, txxx].

Avem M = 6 cărți pe al doilea raft: affx, trfs, abxx, trxx, gefa, fasf.

Primul query cere numărul de compartimente care să aibă coeficientul de similitudine cu [affx, trfs] egal cu 1. Doar compartimentul [abcd, trzs] satisface cerința.

Al doilea query cere numărul de compartimente care să aibă coeficientul de similitudine cu [abxx, trxx] egal cu 1. Nu există niciun astfel de compartiment. Compartimentul [abcd, trzs] are gradul de similitudine 2.

Al treilea query cere numărul de compartimente care să aibă coeficientul de similitudine cu [gefa, fasf] egal cu 3. Soluţia este [gefd, fasf] și [gefa, fasx].

Al patrulea query cere numărul de compartimente care să aibă coeficientul de similitudine cu [fasf, trfs] egal cu 1. Soluţia este [fxxx, txxx].