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\)