Giúp Fill Bates (Helping Fill Bates)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một chuỗi $S$ chỉ gồm các chữ cái A..Z và a..z. Vị trí các ký tự trong $S$ được đánh số từ $0$.

Với mỗi chuỗi truy vấn $T=t_0t_1\ldots t_{m-1}$, hãy kiểm tra xem $T$ có phải là một dãy con của $S$ hay không. Nói cách khác, cần tồn tại các chỉ số:

sao cho $S[p_j]=t_j$ với mọi $0\le j<m$.

Nếu ghép được $T$, hãy in chỉ số của ký tự đầu tiên và ký tự cuối cùng trong một cách ghép có chỉ số bắt đầu nhỏ nhất; nếu vẫn còn nhiều cách thì chọn cách có chỉ số kết thúc nhỏ nhất.

Input

Dòng đầu chứa chuỗi $S$.

Dòng thứ hai chứa số nguyên $Q$.

$Q$ dòng tiếp theo, mỗi dòng chứa một chuỗi truy vấn $T$.

Output

Với mỗi truy vấn:

• nếu ghép được, in Matched l r;
• nếu không ghép được, in Not matched.

Subtask

• Subtask 1 — 20%: $|S|\le2000$, $Q\le100$.
• Subtask 2 — 30%: $|S|\le100000$, $Q\le1000$.
• Subtask 3 — 50%: $|S|\le10^6$, $1\le Q\le3500$, $|T|\le100$.

Mọi chuỗi chỉ gồm chữ cái tiếng Anh hoa hoặc thường.

Ví dụ

Input

aaaaaaaaaaaaaabbbbbbbbbdddddddddddccccccccccccc
3
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaabbbbbbbbbbbc
abccc

Output

Not matched
Not matched
Matched 0 36

Giải thích

Truy vấn abccc có thể lấy a ở vị trí $0$, b ở vị trí $14$ và ba ký tự c đầu tiên sau đó; ký tự cuối cùng được dùng ở vị trí $36$.