아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

K번째 음식 찾기 2

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

요약
정렬된 세 배열과 질의 (x, y, z, k)가 주어질 때, 각 배열의 앞 x, y, z개 원소 중 k번째로 작은 값이 어느 배열의 몇 번째 원소인지 답한다.
난이도

어려움10점 중 8점

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

문제

서준이는 한식, 양식, 중식을 매우 좋아한다. 어느 날 아빠는 배고픈 서준이에게 한식 N개, 양식 N개, 중식 N개를 주었다. 서준이는 모든 음식을 먹고 나서 각각의 음식 맛을 매겼다. 음식의 맛은 231−12^{31} - 1보다 작거나 같은 자연수이며 값이 작을수록 더 맛있는 음식이다.

아빠는 한식[1..x], 양식[1..y], 중식[1..z]중에 k번째로 맛있는 음식을 찾는 질의를 서준이에게 주었는데 너무 배부른 서준이는 잠이 들고 말았다. 서준이를 대신하여 질의의 정답을 출력하자.

입력

첫째 줄에 음식의 수 N이 주어진다.

다음 줄에 N개 한식의 맛 AxA_x (1≤x≤N1 \le x \le N)가 오름차순으로 주어진다.

다음 줄에 N개 양식의 맛 ByB_y (1≤y≤N1 \le y \le N)가 오름차순으로 주어진다.

다음 줄에 N개 중식의 맛 CzC_z (1≤z≤N1 \le z \le N)가 오름차순으로 주어진다.

다음 줄에 질의의 개수 Q가 주어진다. 다음 Q개의 줄에 각각의 질의 x y z k가 주어진다. (1≤k≤x+y+z1 \le k \le x + y + z)

출력

Q개의 줄에 각각의 질의 정답을 출력하자. 각각의 질의 정답은 음식의 종류(한식 1, 양식 2, 중식 3)와 음식의 번호를 빈칸을 사이에 두고 출력한다.

제한

  • 1≤N≤100,0001 \le N \le 100,000
  • 1≤Ax≤231−11 \le A_x \le 2^{31} - 1
  • 1≤By≤231−11 \le B_y \le 2^{31} - 1
  • 1≤Cz≤231−11 \le C_z \le 2^{31} - 1
  • 1≤Q≤100,0001 \le Q \le 100,000
  • 3N개 음식의 맛은 모두 서로 다르다.

예제1

  1. 예제 1

    입력
    7
1 5 10 15 18 20 30
2 3 11 12 14 40 50
4 6 7 8 9 13 16
2
3 3 3 7
5 4 3 10
    예상 출력
    3 3
2 4