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 \leq N \leq 20 000$

• $1 \leq M \leq 30 000$

• $1 \leq Q \leq 20 000$

• $1 \leq K \leq 15$

• $1 \leq P \leq 30$

• $0 \leq X \leq 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]$.