Việc tổ chức các cuộc thi CS không mang lại nhiều lợi nhuận cho Mirko nên anh đã mở một cửa hàng kem và bánh ngọt. Công việc kinh doanh phát đạt cho đến một ngày, cơ quan thanh tra y tế của Liên minh Châu Âu quyết định đến thăm ông.

Một chỉ thị mới quy định ~M~ thành phần bị cấm không được xuất hiện trong thực phẩm ngay cả với lượng nhỏ. Mỗi thành phần có một số sê-ri bao gồm các chữ số từ ~0~ đến ~9~. Tờ khai trên mỗi gói thực phẩm liệt kê tất cả các số sê-ri của các thành phần có trong mặt hàng thực phẩm tương ứng.

Mirko phải kiểm tra xem có sản phẩm nào của mình có số sê-ri thành phần bị cấm được liệt kê trên tờ khai hay không. Tuy nhiên, Mirko, vẫn luôn thiếu năng lực và liều lĩnh, đã quyết định ghép tất cả các số sê-ri thành một số dài có độ dài ~N~ vì tin rằng điều đó sẽ giúp công việc của anh trở nên dễ dàng hơn. Anh ấy đã mượn một con robot từ người bạn Slavko của mình. Robot được lập trình để kiểm tra xem số sê-ri ~A~ có chứa số sê-ri ~B~ khác làm chuỗi con hay không. Chúng ta hãy ký hiệu độ dài của ~B~ bằng ~L~. Robot thực hiện tìm kiếm như sau:

• Đầu tiên, nó so sánh đoạn của ~A~ từ vị trí ~1~ đến vị trí ~L~, từng chữ số, với các chữ số trong ~B~. Việc so sánh dừng lại khi tìm thấy một chữ số khác nhau hoặc khi các đoạn được xác định là bằng nhau. Nếu các phân đoạn bằng nhau, việc tìm kiếm sẽ dừng lại và kết quả trùng khớp sẽ được báo cáo.

• Nếu các đoạn không bằng nhau, quy trình trên được lặp lại với đoạn từ ~2~ đến ~L+1~. Nếu các phân đoạn đó không bằng nhau thì việc tìm kiếm sẽ tiếp tục với các phân đoạn từ ~3~ đến ~L+2~, ~4~ đến ~L+3~, v.v.

• Nếu robot không có đủ số chữ số để có được một đoạn đầy đủ có độ dài ~L~ (ví dụ: bắt đầu từ ký tự ~5~ trong một số sê-ri có độ dài ~8~ thì cần có một đoạn có độ dài ~6~), nó sẽ đệm số có dấu '#'. Ví dụ: đoạn "563232" từ vị trí ~4~ đến vị trí ~10~ là "232####".

• Nếu robot đến cuối dãy số (đã thử hết ~N~ đoạn) mà không tìm thấy ~B~ thì báo cáo không khớp.

Robot mất một giây cho mỗi lần so sánh giữa hai chữ số và Slavko tính phí Mirko một đô la mỗi giây khi sử dụng robot.

Hãy giúp Mirko xác định số tiền anh ấy sẽ phải trả cho Slavko để khớp mẫu!

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 ≤ N \le 100 000)~, độ dài của dãy số dài.
• Dòng đầu vào thứ hai chứa ~N~ chữ số từ ~0~ đến ~9~, số sê-ri dài.
• Dòng thứ ~3~ chứa số nguyên dương ~M~ ~(1 \le M \le 50 000)~, số lượng thành phần bị cấm.
• Mỗi ~M~ hàng sau đây chứa một số sê-ri bị cấm,
• Số serial bị cấm sẽ không dài quá ~100 000~ chữ số.
• Tổng chiều dài của tất cả các số serial bị cấm sẽ không vượt quá ~3 000 000~ chữ số.

Output

Xuất ra ~M~ số nguyên, mỗi số một dòng. Dòng ~i~ phải chứa số tiền mà Mirko cần trả cho Slavko để tìm kiếm số sê-ri thành phần ~i~.

Scoring

Trong dữ liệu thử nghiệm có giá trị ít nhất 20% tổng số điểm, các ràng buộc sau được giữ nguyên: • 1 \le N \le 1000 • 1 \le M \le 500 • Độ dài của một dãy số thành phần bị cấm không vượt quá ~1000~.

Sample Input 1

7
1090901
4
87650
0901
109
090

Sample Ouput 1

7
10
3
4

Sample Input 2

10
5821052680
4
210526
2105
582
105268

Sample Ouput 2

8
6
3
9

Sample Input 3

3
001
1
11

Sample Ouput 3

4

Làm rõ ví dụ đầu tiên:

Số sê-ri đầu tiên: rô-bốt tìm các chữ số đầu tiên khác nhau cho mỗi phân đoạn – tổng cộng có ~7~ phép so sánh.

Số thứ hai: thử vị trí đầu tiên, tìm ngay sự khác biệt (~1~ so sánh). Thử vị trí thứ hai, tìm sự khác biệt ở chữ số thứ tư (~4~ so sánh). Thử vị trí thứ ba, tìm ngay sự khác biệt (~1~ so sánh). Thử vị trí thứ tư, tìm sự trùng khớp (~4~ so sánh). Tổng cộng: ~10~ so sánh.

Số thứ ba: tìm ngay kết quả trùng khớp (~3~ lần so sánh).

Số thứ tư: tìm kết quả trùng khớp ở vị trí thứ hai (so sánh ~1 + 3 = 4~).

Làm rõ ví dụ thứ ba:

Robot so sánh số sê-ri '11' theo thứ tự với các đoạn '00' (~1~ so sánh), '01' (~1~ so sánh) và '1#' (~2~ so sánh). Tổng cộng: ~4~ so sánh.