혈통

시간 제한1초메모리 제한256 MB

요약

주어진 유전자 값에서 아버지와 어머니를 골라 세 새끼의 유전자 값 중 R에 가장 가까운 값이 R에 최대한 가까워지도록 합니다.

난이도: 보통10점 중 5점
유형: 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

토끼 사육 연구소에서는 손님이 원하는 새끼 토끼를 얻으려고 어떤 수컷과 어떤 암컷을 교배시킬지 정한다.

토끼 한 마리에게는 A 유전자가 $a$ 만큼, B 유전자가 $b$ 만큼 있고 두 양의 합은 항상 $1000000$ 이다 ( $a + b = 1000000$ ). A 유전자가 많을수록 귀엽고, B 유전자가 많을수록 똑똑하다. A 유전자가 B 유전자보다 많거나 같은 토끼( $a \ge 500000$ )는 털이 분홍색이다.

교배하면 새끼가 항상 세 마리 태어난다. 아버지의 A 유전자가 $d$ , 어머니의 A 유전자가 $m$ 일 때 세 마리의 A 유전자는 각각 다음과 같다.

첫째 새끼: $0.2d + 0.8m$
둘째 새끼: $0.5d + 0.5m$
셋째 새끼: $0.7d + 0.3m$

이 세 값은 정수가 아닐 수도 있다.

연구소에는 교배용 토끼가 $N$ 쌍 있다. 그중 한 쌍은 A 유전자가 $1000000$ 인 가장 귀여운 쌍이고, 다른 한 쌍은 A 유전자가 $0$ 인 가장 똑똑한 쌍이다. $i$ 번째 쌍은 A 유전자가 $a_i$ 인 수컷 한 마리와 암컷 한 마리로 이루어진다.

손님이 원하는 A 유전자 양 $R$ 을 말하면 사육사는 아버지가 될 수컷 한 마리와 어머니가 될 암컷 한 마리를 고른다. 둘은 서로 다른 쌍에서 골라도 되고 같은 쌍에서 골라도 된다. 손님은 태어난 세 마리 가운데 A 유전자가 $R$ 에 가장 가까운 한 마리를 데려가고, 나머지 두 마리는 연구소에 남아 다음 교배에 쓰인다.

손님이 데려가는 새끼의 A 유전자와 $R$ 의 차이가 가장 작아지도록 아버지와 어머니를 고르는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다 ( $1 \le T \le 10$ ).

각 테스트 케이스는 세 줄로 이루어진다.

첫 줄에 교배용 토끼 쌍의 수 $N$ 이 주어진다 ( $2 \le N \le 1000000$ ).
둘째 줄에 손님이 원하는 A 유전자 양 $R$ 이 주어진다 ( $0 \le R \le 1000000$ ).
셋째 줄에 각 쌍의 A 유전자 양 $a_1, a_2, \dots, a_N$ 이 공백으로 구분되어 주어진다 ( $0 \le a_i \le 1000000$ ).

$a_i$ 중에는 $0$ 이 적어도 하나, $1000000$ 이 적어도 하나 있다.

출력

각 테스트 케이스마다 고른 아버지의 A 유전자와 어머니의 A 유전자를 이 순서로 한 줄에 공백으로 구분해 출력한다.

차이가 가장 작은 조합이 여럿이면 어머니의 A 유전자가 가장 큰 조합을 출력한다. 그런 조합마저 여럿이면 그중 아버지의 A 유전자가 가장 큰 조합을 출력한다.

예제2

예제 1

입력

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

예상 출력

0 1000000
310000 315000
200000 600000

예제 2

입력

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

예상 출력

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