23791번 - K번째 음식 찾기 1

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

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

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

다음 줄에 N개 한식의 맛 A_i (1 ≤ i ≤ N)가 오름차순으로 주어진다.

다음 줄에 N개 양식의 맛 B_j (1 ≤ j ≤ N)가 오름차순으로 주어진다.

다음 줄에 질의의 개수 Q가 주어진다. 다음 Q개의 줄에 각각의 질의 i j k가 주어진다. (1 ≤ k ≤ i + j)

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

• 1 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ A_i ≤ 2³¹ − 1
• 1 ≤ B_j ≤ 2³¹ − 1
• 모든 음식의 맛은 서로 다르다.