ISRANK - ISRANK

no tags 

There are N schools, with ith school having Si students. There is a inter-school programming contest IPC in which all the schools participate. As IPC is a very prestigious event, the schools conduct a test run within themselves. They assign a predicted rank for students within the school for all students, based on the rank they got in the test run. Let Pij be the predicted rank of jth student of ith school. The predicted rank will be unique within the school, i.e. formally:

{ ∀i,Pij = Pik ⇔ j = k }

It should be noted that students of different schools may have the same predicted rank.

At the end of IPC, the IPC committee has given each school the result card containing the marks of all students of that school. Let Mij represent the actual marks obtained by the jth student of ith school. IPC follows a strict rule of giving unique marks to all students taking part in IPC, i.e. formally:

{ ∀i,∀j,Mij = Mpk ⇔ i = p and j = k }

You are to design a system, which will efficiently answer queries of the following form:

  • L - the number of schools to be considered.
  • A1 A2 A3 ... AL - the list of schools.
  • P1 P2 - The range of predicted ranks.
  • K - desired rank.

You are to answer - among all the students who attended the given list of schools and with predicted ranks between P1 and P2 both inclusive, the marks of the student with Kth highest marks. (The first highest marks would the the maximum marks, and second would be the next and so on)

Input

First line contains a single integer N, the number of schools.
The next line contains N space separated integers Si.
The next N lines, the ith line contains Si space separated integers, jth of which is denoting Pij.
The next N lines, the ith line contains Si space separated integers, jth of which is denoting Mij.
The next line contains a single integer Q, denoting the number of queries.
What follows are Q sets of queries. Each query is structured as follows:
First line of the query is L, the list of schools.
Followed by L integers denoting the 1 based indices of schools.
Next are P1 and P2, the range of ranks we are interested in.
Next is the integer K.

Output

For each query on a separate line print a single integer answering the query. If answer is not possible print -1.

Constraints

1 ≤ N ≤ 10
1 ≤ Si ≤ 10000
1 ≤ Pij ≤ Si
1 ≤ Mij ≤ 1000000000
1 ≤ Q ≤ 10000
1 ≤ P1 ≤ P2 ≤ max(S[i])
1 ≤ K ≤ sum of all S[i]

Example

Input:
4
1 3 4 1
1
1 2 3
2 3 1 4
1
28
20 11 8
6 18 22 26
7
4
1
2
3 3
1
1
2
3 3
1
3
1 3 4
4 4
1
4
1 2 3 4
4 4
4

Output:
8
8
26
-1


Added by:smit hinsu
Date:2013-02-18
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 13 , Author : Kaushik Iska