시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 0 0 0 0.000%

문제

ณ Institute of Hare Breeding ผู้ดูแลจะต้องประเมินว่ากระต่ายคู่ใดควรจะถูกเลือกให้เป็นพ่อแม่พันธุ์เพื่อให้ได้ลูกกระต่ายที่มีลักษณะตามต้องการ หลักการถ่ายทอดทางพันธุกรรมของกระต่ายมีดังนี้ กระต่ายแต่ละตัวจะมียีน A อยู่ ai ส่วนและมียีน B อยู่ bi ส่วน ซึ่งจะต้องรวมกันได้เท่ากับ 1 000 000 ส่วน (ai + bi = 1 000 000) ส าหรับยีน A ที่มากจะท าให้น่ารัก และยีน B ที่มากจะท าให้ฉลาด กระต่ายจะมีขนสีชมพูเมื่อมียีนA มากกว่าหรือเท่ากับยีน B (ai >= 500 000) เมื่อกระต่ายผสมพันธุ์จะได้ลูก 3 ตัวเสมอ โดยแต่ละตัวจะมียีนเป็นสัดส่วนของยีนของพ่อแม่ เมื่อก าหนดให้พ่อมียีน A อยู่ adad ส่วน และแม่มียีน A อยู่ amom ส่วนดังนี้

  • ลูกตัวที่ 1 มีสัดส่วนยีน A เท่ากับ 0.2*adad + 0.8*amom
  • ลูกตัวที่ 2 มีสัดส่วนยีน A เท่ากับ 0.5*adad + 0.5*amom
  • ลูกตัวที่ 3 มีสัดส่วนยีน A เท่ากับ 0.7*adad + 0.3*amom

ในศูนย์จะมีกระต่ายพ่อแม่พันธุ์อยู่ N คู่ โดยจะมีกระต่ายสุดน่ารักและกระต่ายสุดฉลาดอยู่อย่างละคู่และมีกระต่ายอีก n-2 คู่ที่มีสัดส่วนยีน A เท่ากับ ai ส่วน กล่าวคือมีตัวผู้และตัวเมียที่มียีน A เท่ากับ ai อย่างละ 1 ตัว เมื่อได้รับสัดส่วนยีน A ที่ลูกค้าต้องการผู้ดูแลจะประเมิณและเลือกพ่อแม่พันธุ์ที่เหมาะสม (ไม่จ าเป็นต้องเลือกคู่ที่มีปริมาณยีน A เท่ากัน) ลูกค้าจะรับลูกกระต่ายตัวที่ถูกใจไป โดยดูจากการที่มีสัดส่วนของยีน A ใกล้เคียงกับความต้องการมากที่สุด ส่วนอีกสองตัวที่เหลือจะถูกเก็บไว้เป็นพ่อแม่พันธุ์ต่อไป

입력

บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 10) กรณีทดสอบแต่ละชุดประกอบด้วยข้อมูลดังนี้

  1. บรรทัดแรกคือจ านวนพ่อแม่พันธุ์ N คู่ (2 ≤ N ≤ 1 000 000)
  2. บรรทัดที่สองเป็นจ านวนเต็ม R แสดงสัดส่วนยีนที่ลูกค้าต้องการ (0 ≤ R ≤ 1 000 000)
  3. บรรทัดที่สามประกอบไปด้วยจ านวนเต็ม ai ทั้งหมด N ตัว ระบุสัดส่วนยีน A ของกระต่ายพ่อแม่ พันธุ์แต่ละคู่ (0 ≤ ai ≤ 1 000 000)

출력

ส าหรับแต่กรณีทดสอบ ให้แสดงจ านวนเต็มสองจ านวนแสดงสัดส่วนยีนของพ่อแม่พันธุ์ที่ถูกเลือก ตามล าดับ ถ้ามีพ่อแม่พันธุ์ที่เป็นไปได้หลายคู่ให้เลือกตอบคู่ที่แม่พันธุ์น่ารักที่สุด

예제 입력

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

예제 출력

0 1000000
310000 315000
200000 600000

힌트