Lineage

Time limit1sMemory limit256 MB

Summary

Pick a father and a mother from the given gene values so the nearest of the three pups' gene values to R is as close as possible.

Level: Medium5 of 10
Topics: Sorting, Binary search
Solved: No attempts yet

Problem

At a rabbit breeding institute the keeper decides which male and which female to mate so that a customer gets the young rabbit they want.

A rabbit carries gene A in amount $a$ and gene B in amount $b$ , and the two amounts always add up to $1000000$ ( $a + b = 1000000$ ). More gene A makes a rabbit cuter, more gene B makes it smarter. A rabbit whose gene A is at least as large as its gene B ( $a \ge 500000$ ) has pink fur.

A mating always produces three young rabbits. If the father carries gene A in amount $d$ and the mother carries gene A in amount $m$ , the three young rabbits carry gene A in these amounts:

first: $0.2d + 0.8m$
second: $0.5d + 0.5m$
third: $0.7d + 0.3m$

These three amounts are not always integers.

The institute keeps $N$ breeding pairs. One pair is the cutest pair, with gene A equal to $1000000$ , and another pair is the smartest pair, with gene A equal to $0$ . Pair $i$ is one male and one female that both carry gene A in amount $a_i$ .

The customer names the amount $R$ of gene A they want, and the keeper picks one male as the father and one female as the mother. The two may come from different pairs or from the same pair. The customer takes the one young rabbit whose gene A is closest to $R$ , and the other two stay at the institute for later matings.

Pick the father and the mother so that the difference between $R$ and the gene A of the young rabbit the customer takes is as small as possible.

Input

The first line has the number of test cases $T$ ( $1 \le T \le 10$ ).

Each test case is three lines.

The first line has the number of breeding pairs $N$ ( $2 \le N \le 1000000$ ).
The second line has the amount $R$ of gene A the customer wants ( $0 \le R \le 1000000$ ).
The third line has the amounts $a_1, a_2, \dots, a_N$ separated by spaces ( $0 \le a_i \le 1000000$ ).

At least one $a_i$ is $0$ and at least one $a_i$ is $1000000$ .

Output

For each test case print the gene A of the chosen father and the gene A of the chosen mother in that order, on one line, separated by a space.

If several combinations give the same smallest difference, print the one whose mother has the largest gene A. If several of those remain, print the one whose father has the largest gene A.

Examples2

Example 1

Input

3
2
314159
0 1000000
4
314159
0 310000 315000 1000000
5
314159
0 200000 400000 600000 1000000

Expected output

0 1000000
310000 315000
200000 600000

Example 2

Input

10
16
999999
838685 999971 6 0 999955 18 954993 999973 1000000 999972 460740 884916 559407 168234 35483 1
7
999999
1000000 0 606705 999969 10 5 576180
35
1000000
0 960461 10 999994 736477 27 731762 999983 40 999973 497026 38 999977 999987 975996 1000000 999974 999972 766319 27 999965 688810 999961 6 1651 608079 8 8 820564 31 48 999977 39 999971 35
13
500000
139080 999980 999981 0 999970 623487 999954 1000000 999992 34 18 999984 999969
21
882240
48 344753 1000000 999981 46 13 75717 999983 999977 39 553080 750781 42 0 5 760254 999983 999980 35 666757 45
4
219963
0 999975 999967 1000000
28
1000000
188750 999997 0 999993 36 1000000 999995 999966 999964 1 1 999996 13 999960 583236 826858 588464 21 727760 999964 725920 1000000 989483 31 999977 999978 999967 884395
4
0
1000000 67912 0 36
14
499999
43539 183739 50 45 0 609430 943343 999987 23 16 832639 326829 1000000 227535
37
1000000
147949 999978 361895 999956 33 999999 999953 999984 999973 869870 33 1000000 3 0 999961 30 502827 999984 23 999979 999988 42 708849 999955 47 20 1000000 43 849170 471823 999968 999959 1 6 32 999985 999998

Expected output

1000000 1000000
1000000 1000000
1000000 1000000
0 1000000
760254 1000000
1000000 0
1000000 1000000
0 0
0 1000000
1000000 1000000