D. Masquerade strikes back
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Quite often the jury of Saratov SU use the problem "Masquerade" in different practice sessions before the contest. This problem is quite easy — all you need is to print the product of two integers which were read from the input stream.

As usual, the jury had prepared this problem once again. The jury had $$$n$$$ testcases, the $$$i$$$-th testcase was a pair of positive integers $$$a_i$$$ and $$$b_i$$$, both integers didn't exceed $$$10^7$$$. All testcases were pairwise distinct.

Unfortunately, something went wrong. Due to hardware issues all testcases have disappeared. All that the jury were able to restore are the number of testcases $$$n$$$ and the answers to these testcases, i. e. a sequence of $$$n$$$ numbers $$$c_1, c_2, \dots, c_n$$$, such that $$$a_i \cdot b_i = c_i$$$.

The jury ask you to help them. Can you provide any possible testset? Remember that all testcases were distinct and all numbers in each testcase were positive integers and didn't exceed $$$10^7$$$.

Input

First line contains one insteger $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of lost testcases.

Second line contains $$$n$$$ space-separated integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^7$$$) — the answers to the testcases.

Output

If there is no such testset, print NO.

Otherwise, print YES in first line. Then print $$$n$$$ more lines, the $$$i$$$-th of them should contain two space separated positive integers $$$a_i$$$ and $$$b_i$$$ not exceeding $$$10^7$$$. All pairs $$$(a_i, b_i)$$$ must be distinct, and, for each $$$i \in [1, n]$$$, the condition $$$a_i \cdot b_i = c_i$$$ must be met.

Examples
Input
4
1 3 3 7
Output
YES
1 1
1 3
3 1
1 7
Input
5
3 1 3 3 7
Output
NO
Input
6
9 10 9 10 9 10
Output
YES
1 9
1 10
3 3
5 2
9 1
2 5
Note

In the first example one of the possible testsets is ($$$a_1 = 1$$$, $$$b_1 = 1$$$), ($$$a_2 = 1$$$, $$$b_2 = 3$$$), ($$$a_3 = 3$$$, $$$b_3 = 1$$$), ($$$a_4 = 1$$$, $$$b_4 = 7$$$).

In the second example a testset consisting of distinct tests doesn't exist.