SP13809 ISRANK - ISRANK

There are **N** schools, with i th school having **S $ _{i} $** 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 **P $ _{ij} $** 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 **M $ _{ij} $** 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 **S $ _{i} $** . The next **N** lines, the **i** th line contains **S $ _{i} $** space separated integers, **j** th of which is denoting **P $ _{ij} $** . The next **N** lines, the **i** th line contains **S $ _{i} $** space separated integers, **j** th of which is denoting **M $ _{ij} $** . 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 1 S $ _{i} $ 1 P $ _{ij} $ S $ _{i} $ 1 M $ _{ij} $ 1 Q **1 1**

N/A

N/A