시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB1671038264.567%

문제

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

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

입력

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

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

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

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

각 줄에는 $A$, $B$, $C$, $j$가 공백으로 구분되어 주어진다. $A$, $B$, $C$는 서로 다른 정수이다. ($1 \leq A, B, C \leq N;$ $1 \leq j \leq K_A + K_B + K_C$)

출력

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

예제 입력 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

1
3
7

예제 입력 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

2
1
6
100

예제 입력 3

3 2
3 1 1 2
3 1 1 2
4 1 2 2 2
1 2 3 3
1 2 3 9

예제 출력 3

1
2