This page is still under construction.

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

Find the K-th Tastiest Food 1

Time limit1sMemory limit512 MB

Summary
Given two sorted arrays of tastes, answer queries asking for the k-th smallest value among the first i Korean and first j Western dishes and report which array and index it came from.
Level

Medium7 of 10

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

Problem

Seojun loves Korean food and Western food alike. One day his father gave hungry Seojun N Korean dishes and N Western dishes. After eating every dish, Seojun rated the taste of each one. A dish's taste is a positive integer no greater than 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 dishes [1..i][1..i] and Western dishes [1..j][1..j], but Seojun was so full that he 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 AiA_i of the N Korean dishes (1≤i≤N1 \le i \le N) in ascending order.

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

The next line gives the number of queries, Q. The following Q lines each give a query i j k. (1≤k≤i+j1 \le k \le i + j)

Output

Print the answer to each query on its own line, for Q lines total. Each answer is the type of the dish (1 for Korean, 2 for Western) and the dish's index, separated by a space.

Constraints

  • 1≤N≤100,0001 \le N \le 100,000
  • 1≤Q≤100,0001 \le Q \le 100,000
  • 1≤Ai≤231−11 \le A_i \le 2^{31} - 1
  • 1≤Bj≤231−11 \le B_j \le 2^{31} - 1
  • All dishes have distinct tastes.

Examples1

  1. Example 1

    Input
    7
1 5 10 15 18 20 30
2 3 8 11 14 40 50
2
3 3 3
3 4 6
    Expected output
    2 2
1 3