Text Highlighter

You are given a document text and several substring queries. For each query, you must output the substring of the document specified by a starting index and an ending index. If the starting index is greater than the ending index, or if either index is out of bounds, then the query is invalid and you should output INVALID QUERY.

More formally, suppose the document is represented by a string \(D\) with \(n\) characters indexed from 0 to \(n-1\). For a given query with indices \(s\) and \(e\), the answer is:

[ \text{answer} = \begin{cases} D[s \ldots e] & \text{if } 0 \le s \le e < n, \ \text{INVALID QUERY} & \text{otherwise}. \end{cases} ]

The input begins with an integer \(T\) indicating the number of test cases. For each test case, the first line is the document text \(D\), the second line is an integer \(Q\) representing the number of queries, followed by \(Q\) lines each containing two integers \(s\) and \(e\). For each test case, output a single line with the answers for each query separated by a single space.

inputFormat

The input is read from standard input. The first line contains an integer \(T\), the number of test cases. Each test case is described as follows:

1. A line containing the document text \(D\) (a non-empty string that may contain spaces).
2. A line containing an integer \(Q\), the number of queries.
3. Then \(Q\) lines follow, each with two space-separated integers \(s\) and \(e\) representing the starting and ending indices of a query.

It is guaranteed that the document text and indices are provided on separate lines appropriately.

outputFormat

For each test case, output a single line containing the results for each of the \(Q\) queries separated by a single space. If a query is valid, output the substring \(D[s...e]\); otherwise, output INVALID QUERY.

## sample

2
hello world
3
0 4
6 10
5 15
coding is fun
2
0 5
4 3

hello world INVALID QUERY
coding INVALID QUERY

</p>