như ảnh; C++

Mô tả bài toán

Ribonucleic acid (RNA) là một phân tử polymer cơ bản có nhiều vai trò sinh học trong mã hóa, dịch mã, điều hòa, và biểu hiện của gene. RNA là một loại nucleic acid, và, cùng với lipid, protein và carbohydrate, tạo thành bốn loại đại phân tử cơ sở cho mọi dạng sự sống trên Trái Đất.

Giống như DNA, RNA tạo thành từ một chuỗi nucleotide, nhưng không giống DNA là thường tìm thấy nó ở dạng tự nhiên là một sợi đơn gấp lại vào chính nó, hơn là sợi xoắn kép. Các sinh vật tế bào sử dụng RNA thông tin (mRNA) để truyền đạt các thông tin di truyền (sử dụng các base nitric guanine, uracil, adenine, và cytosine, ký hiệu tương ứng bằng các chữ cái G, U, A và C) cho phép tổng hợp trực tiếp lên các protein chuyên biệt. Nhiều virus mã hóa thông tin di truyền của chúng trong bộ gene RNA.

Một nhà khoa học `K` muốn nghiên cứu các đặc tính của `n` chuỗi RNA khác nhau mà phòng thí nghiệm hiện có. Biết rằng các RNA có chung các nucleotide ở đầu hoặc ở cuối chuỗi thường sẽ có các tính chất tương tự nhau, `K` thực hiện `m` thao tác trích xuất RNA với các yêu cầu: ứng với một thao tác trích xuất, `K` cần thu thập tất cả các chuỗi RNA:

• Nhận xâu `P` làm một tiền tố, và

• Nhận xâu `Q` làm một hậu tố.

Trong đó, `P, Q` là đặc trưng của thao tác trích xuất được cho trước.

Với mỗi một thao tác trích xuất, bạn hãy xác định giúp K rằng có bao nhiêu chuỗi RNA thoả mãn các yêu cầu trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương `n, m`, cách nhau bởi một dấu cách `(1 <= n, m <= 10^5).`

• `n` dòng tiếp theo, dòng thứ `i` chứa xâu `S_i (1 <= i <= n, 1 <= |S_i| <= 10^5)`.

• `m` dòng tiếp theo, dòng thứ `j` chứa hai xâu đặc trưng của thao tác trích xuất `P_j, Q_j`, cách nhau bởi một dấu cách `(1 <= j <= m, 1 <= |P_j|, |Q_j| <= m)`.

• `sum(|S_i|), sum(|P_j|), sum(|Q_j|) <= 2 * 10^6.`

Output

Xuất ra m dòng, dòng thứ j chứa một số nguyên là kết quả của thao tác trích xuất thứ j.

Sample Input 1:

2 3

AUGC

AGC

G C

AU C

A C

Sample Output 1:

0

1

2

Sample 2:

3 3

AA

AA

AGA

AA AA

AG GA

AG GA

Sample Output 2:

2

1

1

Notes

Sample 1:

• Thao tác 1: Không có RNA nào bắt đầu bằng G.

• Thao tác 2: AUGC thỏa mãn.

• Thao tác 3: Cả hai xâu đều thỏa mãn.

Sample 2:

• Thao tác 2: Xâu AGA vẫn thỏa mãn, mặc dù hai xâu P = AG và Q = GA bị chồng lên nhau khi xếp trên xâu ban đầu.

link test: oj.vnoi.info/problem/hsg_hue_v2_2324_rna