세 배열 오름차순

시간 제한2초메모리 제한1024 MB

요약
N개의 배열이 주어질 때, 지정된 세 배열의 원소를 모두 모아 정렬했을 때 j번째로 작은 값을 구하는 쿼리에 답한다.
난이도

보통10점 중 7점

유형
이분 탐색, 배열, 정렬, 분할 정복
정답자
아직 제출이 없습니다

문제

양의 정수 배열 NN개가 주어졌을 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • A B C j: AA번 배열, BB번 배열, CC번 배열의 원소들을 모두 모아 오름차순으로 정렬했을 때 jj번째 원소의 값을 출력한다.

입력

첫째 줄에 배열의 개수 NN과 쿼리의 개수 QQ가 공백으로 구분되어 주어진다. (3≤N≤105;3 \leq N \leq 10^{5}; 1≤Q≤1051 \leq Q \leq 10^{5})

둘째 줄부터 NN개의 줄에 걸쳐 ii번 배열의 크기 K_iK\_i와 각 배열의 원소 K_iK\_i개가 공백으로 구분되어 주어진다. (1≤K_i≤1051 \leq K\_i \leq 10^{5})

주어진 K_iK\_i의 합은 4×1054 \times 10^{5}을 넘지 않으며 배열의 각 원소들은 10910^{9} 이하인 양의 정수이다.

이후 QQ개의 줄에 걸쳐 쿼리가 주어진다.

각 줄에는 AA, BB, CC, jj가 공백으로 구분되어 주어진다. AA, BB, CC는 서로 다른 정수이다. (1≤A,B,C≤N;1 \leq A, B, C \leq N; 1≤j≤K_A+K_B+K_C1 \leq j \leq K\_A + K\_B + K\_C)

출력

각 쿼리의 결과를 한 줄에 하나씩, 총 QQ개의 줄에 걸쳐 출력한다.

예제3

  1. 예제 1

    입력
    3 3
3 1 3 5
2 2 4
4 2 7 1 6
1 2 3 1
1 2 3 5
3 2 1 9
    예상 출력
    1
3
7

  2. 예제 2

    입력
    4 4
5 5 1 4 2 3
4 2 6 7 2
3 9 8 5
2 1 100
1 2 3 4
2 3 4 1
4 1 2 9
1 3 4 10
    예상 출력
    2
1
6
100

  3. 예제 3

    입력
    3 2
3 1 1 2
3 1 1 2
4 1 2 2 2
1 2 3 3
1 2 3 9
    예상 출력
    1
2