ISRANK - ISRANK

There are N schools, with i th 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 j th student of i th school. The predicted rank will be unique within the school, i.e. formally:

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 j th student of i th school. IPC follows a strict rule of giving unique marks to all students taking part in IPC, i.e. formally:


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 K th 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 i th line contains Si space separated integers, j th of which is denoting Pij.
The next N lines, the i th line contains Si space separated integers, j th of which is denoting Mij.
The next line contains a single integer Q, denoting the number of queries.
Whats 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 ≤ PijSi
1 ≤ Mij ≤ 1000000000
1 ≤ Q ≤ 10000
1 ≤ P1 ≤ P2 ≤ max(S[i])
1 ≤ K ≤ sum of all S[i]

 

Sample 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

Sample 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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.