Bạn có biết Công ty TNHH Just Odd Inventions không? Công việc kinh doanh của công ty này là tạo ra “những phát minh kỳ lạ”. Trong bài này, ta gọi tắt là công ty JOI.

Gần đây, lợi nhuận của công ty JOI sụt giảm nghiêm trọng vì chỉ kinh doanh những phát minh kỳ lạ. Công ty dự định bắt đầu một hoạt động kinh doanh mới: bán dung dịch chứa các chuỗi RNA. Một chuỗi RNA được xem là một xâu chỉ gồm bốn ký tự A, G, C, U. Công ty JOI đã chuẩn bị \(N\) chuỗi RNA để kinh doanh.

Công ty nhận đơn hàng từ khách hàng theo hình thức sau: khách hàng chọn hai xâu \(P,Q\). Trong số các chuỗi RNA đã chuẩn bị, công ty bán những chuỗi có \(|P|\) ký tự đầu tiên là \(P\) và \(|Q|\) ký tự cuối cùng là \(Q\). Ở đây, \(|P|\) và \(|Q|\) lần lượt là độ dài của \(P\) và \(Q\).

Có bao nhiêu chuỗi RNA mà công ty đã chuẩn bị thỏa mãn điều kiện của từng đơn hàng?

Yêu cầu

Cho thông tin về các chuỗi RNA đã chuẩn bị và các đơn hàng của khách hàng, hãy tính số chuỗi RNA thỏa mãn điều kiện của mỗi đơn hàng.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,M\) cách nhau bởi một dấu cách: số chuỗi RNA công ty đã chuẩn bị và số đơn hàng.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1\le i\le N\)) chứa xâu \(S_i\), là chuỗi RNA thứ \(i\).
• Dòng thứ \(j\) trong \(M\) dòng tiếp theo (\(1\le j\le M\)) chứa hai xâu \(P_j,Q_j\) cách nhau bởi một dấu cách, là hai xâu khách hàng chọn trong đơn hàng thứ \(j\).

Dữ liệu ra

In \(M\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1\le j\le M\)) chứa một số nguyên: số chuỗi RNA đã chuẩn bị thỏa mãn điều kiện của đơn hàng thứ \(j\).

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le M\le 100\,000\).
• Mỗi xâu chỉ chứa các ký tự A, G, C, U.
• \(1\le |S_i|\le 100\,000\) với mọi \(1\le i\le N\).
• \(1\le |P_j|\le 100\,000\) với mọi \(1\le j\le M\).
• \(1\le |Q_j|\le 100\,000\) với mọi \(1\le j\le M\).

Các tổng độ dài thỏa mãn riêng từng giới hạn sau:

• \(|S_1|+|S_2|+\cdots+|S_N|\le 2\,000\,000\).
• \(|P_1|+|P_2|+\cdots+|P_M|\le 2\,000\,000\).
• \(|Q_1|+|Q_2|+\cdots+|Q_M|\le 2\,000\,000\).

Phân nhóm

Subtask 1 (10 điểm)

• \(N\le 100\).
• \(M\le 100\).
• \(|S_i|\le 100\) với mọi \(1\le i\le N\).
• \(|P_j|\le 100\) với mọi \(1\le j\le M\).
• \(|Q_j|\le 100\) với mọi \(1\le j\le M\).

Subtask 2 (25 điểm)

• \(N\le 5\,000\).
• \(M\le 5\,000\).

Subtask 3 (25 điểm)

Các tổng độ dài thỏa mãn riêng từng giới hạn sau:

• \(|S_1|+|S_2|+\cdots+|S_N|\le 100\,000\).
• \(|P_1|+|P_2|+\cdots+|P_M|\le 100\,000\).
• \(|Q_1|+|Q_2|+\cdots+|Q_M|\le 100\,000\).

Subtask 4 (40 điểm)

Không có ràng buộc bổ sung.

Ví dụ

2 3
AUGC
AGC
G C
AU C
A C

0
1
2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

2
1
1

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA

1
0
1
2
3
2
0