Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT016B - ACM PTIT 2016 B - MAXPREFIX

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 xy, 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 = [c1, c2, ..., cK] và B = [d1, d2, ..., dK], ta gọi độ tương đồng của chúng là

       min{length(maxprefix(c1, d1)); length(maxprefix(c2, d2)); ...; length(maxprefix(cK, dK))},

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, PQ đượ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


Được gửi lên bởi:Admin
Ngày:2016-04-26
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.