Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Trong một lần làm việc ở thư viện, Hùng nhận nhiệm vụ sắp xếp các cuốn sách trên các giá sách. Có một giá sách với N ngăn, mỗi ngăn chứa đúng K cuốn sách. Thư viện mới mua về M cuốn sách. Mỗi cuốn sách (trên giá và mới mua) đều được gắn mã là một xâu gồm đúng P chữ cái in thường từ bảng chữ cái tiếng Anh.

Ta gọi tiền tố của một xâu S là một đoạn đầu bất kỳ của nó. Ta định nghĩa tiền tố chung dài nhất của hai xâu x và y, ký hiệu là maxprefix(x, y), là dãy ký tự dài nhất đồng thời là tiền tố của cả xâu x lẫn xâu y.

Cho hai dãy mã sách A = [c₁, c₂, ..., c_K] và B = [d₁, d₂, ..., d_K], ta gọi độ tương đồng của chúng là

       min{length(maxprefix(c₁, d₁)); length(maxprefix(c₂, d₂)); ...; length(maxprefix(c_K, d_K))},

trong đó ký hiệu length(x) là độ dài của xâu x.

Hùng muốn xếp K cuốn sách trong số M cuốn sách mới mua lên giá sách và vì thế Hùng muốn tìm ngăn trên giá sách có độ tương đồng với chúng là thích hợp nhất.

Yêu cầu: Cho biết mã của tất cả các cuốn sách, cần trả lời Q truy vấn, mỗi truy vấn có dạng: “Cho biết dãy mã của K cuốn sách trong số các cuốn sách mới mua, tìm số lượng ngăn sách trong giá sách mà dãy mã của các cuốn sách trong ngăn có độ tương đồng với dãy mã của K cuốn sách đã cho là đúng bằng giá trị X cho trước.”

Input

• Dòng đầu tiên chứa 5 số nguyên N, K, M, P và Q được ghi cách nhau bởi dấu cách;
• N dòng tiếp theo ghi mã của các cuốn sách trên các ngăn của giá sách, trong đó dòng thứ i chứa K xâu được ghi phân tách nhau bởi dấu cách, mỗi xâu có độ dài P;
• Dòng tiếp theo ghi mã của M cuốn sách mới mua, các cuốn sách được đánh số từ 1 đến M, gồm M xâu (xâu thứ i là mã của cuốn sách thứ i, i = 1, 2, …, M) được ghi phân tách nhau bởi dấu cách, mỗi xâu có độ dài P;
• Q dòng tiếp theo mô tả các truy vấn: Mỗi dòng chứa K+1 số, trong đó số đầu tiên trên dòng là giá trị độ tương đồng đòi hỏi (X), tiếp đến là dãy gồm K chỉ số của K cuốn sách trong số M cuốn sách mới mua. Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Hạn chế đối với dữ liệu: 

• 1 ≤ N ≤ 1000; 1 ≤ M ≤ 1000; 1 ≤ Q ≤ 1000;
• 1 ≤ K ≤ 5; 1 ≤ P ≤ 20; 0 ≤ X ≤ 20.

Output

Q dòng, mỗi dòng chứa một số là số lượng ngăn của giá sách đáp ứng yêu cầu đặt ra trong truy vấn tương ứng ở dữ liệu vào.

Example

Input:

4 2 6 4 4

abcd trzs

gefd fasf

gefa fasw

fwww twww

affw trfs abww trww gefa fasf

1 1 2

1 3 4

3 5 6

1 6 2

Output:

1

0

2

1