You are given $N$ integers. You are required to perform $Q$ queries. In each query, you are given two integers $x$ and $y$. Your task is to merge the groups that contain the $x^{th}$ and $y^{th}$ integer to a single group. After performing each query, you are required to print the range of numbers that lie in the newly-formed group. Initially, the numbers do not belong to any group. 

Input format

• First line: $N$ denoting the number of integers
• Next line: $N$ space-separated integers denoting $N$ integers
• Next line: $Q$ denoting the number of queries
• Next $Q$ lines: Integers $x$ and $y$

Output format

For every query, print two space-separated integers $min$ and $max$ in a new line, where $min$ is the minimum element and $max$ is the maximum element of the new group formed.

Constraints

$1 \leq N, Q \leq 2 * 10^5$

$-10^{18} \leq integer_{i} \leq 10^{18}$

$1 \leq x, y \leq N$