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