This page is still under construction.

Parts of this page are still being built. What you see may change.

Finding the K-th Tasty Food 2

Time limit2sMemory limit512 MB

Summary
Given three sorted arrays and queries (x, y, z, k), find the k-th smallest value among the first x, y, and z elements and report which array and index it came from.
Level

Hard8 of 10

Topics
Binary search, Divide and conquer, Array, Sorting
Solved
No attempts yet

Problem

Seojun loves Korean, Western, and Chinese food. One day his father gave hungry Seojun N Korean dishes, N Western dishes, and N Chinese dishes. After eating every dish, Seojun rated the taste of each one. A dish's taste is a positive integer less than or equal to 231−12^{31} - 1, and a smaller value means a tastier dish.

His father gave Seojun queries asking for the k-th tastiest dish among Korean[1..x], Western[1..y], and Chinese[1..z]. Seojun was too full and fell asleep. Print the answers to the queries on his behalf.

Input

The first line gives the number of dishes N.

The next line gives the tastes AxA_x (1≤x≤N1 \le x \le N) of the N Korean dishes in ascending order.

The next line gives the tastes ByB_y (1≤y≤N1 \le y \le N) of the N Western dishes in ascending order.

The next line gives the tastes CzC_z (1≤z≤N1 \le z \le N) of the N Chinese dishes in ascending order.

The next line gives the number of queries Q. The following Q lines each give a query x y z k. (1≤k≤x+y+z1 \le k \le x + y + z)

Output

Print the answer to each query on Q lines. For each query, print the type of dish (Korean 1, Western 2, Chinese 3) and the dish's index, separated by a space.

Constraints

  • 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
  • All 3N dishes have distinct tastes.

Examples1

  1. Example 1

    Input
    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
    Expected output
    3 3
2 4