Cannons

A certain kingdom is preparing for war. Its army consists mainly of cannons, and the tactics for using them are very simple. The kingdom owns $n$ cannons. During a battle they are placed one after another along the front line. The cannons are numbered from $1$ to $n$, from left to right. Each cannon $i$ has an associated integer $p_i$ denoting its combat strength.

The Royal Combat Analysis Center (CAB) is responsible for battle tactics. While preparing for war, CAB considers various battle scenarios. A scenario assumes that the front is attacked along the segment from cannon $a$ to cannon $b$. To choose the most effective tactic, CAB needs to know the minimum and maximum combat strength among the cannons on that segment. Help CAB solve this quickly.

The first line contains a natural number $d$ ($1 \le d \le 100$), the number of tests. The descriptions of the tests follow one after another.

The first line of each test contains an integer $n$ ($1 \le n \le 10^6$), the number of cannons. The second line contains $n$ integers $p_i$ ($-10^9 \le p_i \le 10^9$), the combat strengths of the cannons. The next line contains an integer $m$ ($1 \le m \le 10^5$), the number of scenarios CAB considers. Each of the following $m$ lines contains one scenario, given as two integers $a$ and $b$ ($1 \le a \le b \le n$).

For each scenario, print the minimum and the maximum combat strength among the cannons on the segment from cannon $a$ to cannon $b$, separated by a single space on one line.