Given the string $s$ and a set of its substrings. Substrings are defined by pairs of numbers $l_i,r_i$, the position of the left end and the right end of the substring. You need to sort substrings in lexicographic order. If substrings are equal as words, then use the pairs themselves as an additional sorting key (i.e., first compare by $l$, then by $r$).

The first line contains a non-empty line $s$. Its length does not exceed $4⋅10^5$, it can contain any characters with codes from 33 to 127.

The second line contains $n\ (1≤n≤4⋅10^5)$, the number of substrings in the set. 

The next $n$ lines contain a pairs of integers $l_i,r_i\ (1≤l_i≤r_i≤|s|)$, where $|s|$ is the length of the string $s$. It is possible that a set of substrings contains the same pairs.

Print $n$ lines, each line contains a description of the substring in the same format as in the input. The order of the substrings is specified in the problem statement.