Absent Remainder solution codeforces

Absent Remainder solution codeforces

You are given a sequence a1,a2,,ana1,a2,…,an consisting of nn pairwise distinct positive integers.

Find n2⌊n2⌋ different pairs of integers xx and yy such that:

  • xyx≠y;
  • xx and yy appear in aa;
  • x mod yx mod y doesn’t appear in aa.

Note that some xx or yy can belong to multiple pairs.

x⌊x⌋ denotes the floor function — the largest integer less than or equal to xxx mod yx mod y denotes the remainder from dividing xx by yy.

If there are multiple solutions, print any of them. It can be shown that at least one solution always exists.

Absent Remainder solution codeforces Input

The first line contains a single integer tt (1t1041≤t≤104) — the number of testcases.

The first line of each testcase contains a single integer nn (2n21052≤n≤2⋅105) — the length of the sequence.

The second line of each testcase contains nn integers a1,a2,,ana1,a2,…,an (1ai1061≤ai≤106).

All numbers in the sequence are pairwise distinct. The sum of nn over all testcases doesn’t exceed 21052⋅105.

Output Absent Remainder solution codeforces

The answer for each testcase should contain n2⌊n2⌋ different pairs of integers xx and yy such that xyx≠yxx and yy appear in aa and x mod yx mod y doesn’t appear in aa. Print the pairs one after another.

You can print the pairs in any order. However, the order of numbers in the pair should be exactly such that the first number is xx and the second number is yy. All pairs should be pairwise distinct.

If there are multiple solutions, print any of them.

Example

input

Copy
4
2
1 4
4
2 8 3 4
5
3 8 5 9 7
6
2 7 5 3 4 8

Absent Remainder solution codeforces output

Copy
4 1
8 2
8 4
9 5
7 5
8 7
4 3
5 2
Note

In the first testcase there are only two pairs: (1,4)(1,4) and (4,1)(4,1)22=1⌊22⌋=1, so we have to find one pair. 1 mod 4=11 mod 4=1, and 11 appears in aa, so that pair is invalid. Thus, the only possible answer is a pair (4,1)(4,1).

In the second testcase, we chose pairs 8 mod 2=08 mod 2=0 and 8 mod 4=08 mod 4=000 doesn’t appear in aa, so that answer is valid. There are multiple possible answers for that testcase.

In the third testcase, the chosen pairs are 9 mod 5=49 mod 5=4 and 7 mod 5=27 mod 5=2. Neither 44, nor 22, appears in aa, so that answer is valid.

Leave a Comment

Your email address will not be published. Required fields are marked *