Helping Fill Bates

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

You are given a string $S$ containing only A..Z and a..z. Its characters are indexed from $0$.

For each query string $T=t_0t_1\ldots t_{m-1}$, determine whether $T$ is a subsequence of $S$. Equivalently, there must exist indices

such that $S[p_j]=t_j$ for every $0\le j<m$. If a match exists, print the first and last selected positions for the match with the smallest starting position; break any remaining tie by the smallest ending position.

Input

The first line contains $S$.

The second line contains $Q$.

The next $Q$ lines contain query strings.

Output

For each query, print Matched l r if it can be matched; otherwise print Not matched.

Subtasks

• 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$.

Examples

Input

aaaaaaaaaaaaaabbbbbbbbbdddddddddddccccccccccccc
3
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaabbbbbbbbbbbc
abccc

Output

Not matched
Not matched
Matched 0 36

Explanation

For abccc, one valid matching starts at position $0$ and ends at position $36$; this pair also satisfies the required tie-breaking rule.