4442 - 정렬된 두 부분 배열의 중앙값

• Submit
• Status
• Discuss
• Summary

Description

크기가 N이고 원소가 이미 정렬된 배열 A와 B가 있다. 두 배열의 일부를 취해서 중앙값을 찾는 과정은 다음과 같다.

1. 배열 A와 B에서 인덱스 s부터 인덱스 e까지(포함)의 원소를 추출해 부분배열 C과 D를 생성한다.
2. 배열 C와 D를 합치고 오름차순으로 정렬해서 새로운 배열 E 를 만든다.
3. 배열 E에서 중앙값을 취한다. (E의 크기는 항상 짝수이므로 중앙값은 항상 2개) 

여러분은 중앙값을 찾는 작업을 R번 할 것이기 때문에, 위 과정을 최대한 빠르게 해야한다. 

Input

* Line 1 : N(2~10,000 범위의 정수) R(1~100,000 범위의 정수)

* Line 2 : 공백으로 구분된 배열A의 N개의 원소 (각 원소는 4byte범위의 정수)

* Line 3 : 공백으로 구분된 배열B의 N개의 원소 (각 원소는 4byte범위의 정수)

* Line 4~R+3 : s e (0 ≤ s ≤ e < N; s와 e는 정수)

Output

* Line 1 ~ R : 오름차순의 두개의 중앙값

Sample Input

5 3
1 9 10 14 16
3 14 15 16 17
0 4
1 3
2 4

Sample Output

14 14
14 14
15 16