## Problem

College admissions are starting and Chef has also recently completed his high school. There areÂ NNÂ colleges, numbered fromÂ 11Â toÂ NN, and they are ranked fromÂ 11Â toÂ NN. Each college has only a single seat left. To apply for the colleges, every student has to give a common exam, the result of which decides their destiny, i.e, the student having best rank (scoring max marks) gets to choose the college of their preference first.

Each student has a list of colleges that they like. They will want to get to the best-ranked college from their list. If they canâ€™t get into it, they will want to get into the second-ranked college from among their list, and so on.

If the single vacant seat of a college gets filled, the admission for that year is closed in that college. Then, the people who have applied for that college have to look for a lower-ranked college in their preference list provided that it still has vacancies.

Given information aboutÂ MMÂ students, about their marks scored in the exam (given as ranks) and the idâ€™s of the college they are applying for, find which college Chef will land into given that he is the student withÂ id=1id=1.

Every student tries to get into the highest-ranked college on his list which has a vacancy and if not possible to get into any of the colleges on his list, he wonâ€™t join any college this year.

### Input:

• First line will containÂ TT, number of testcases. Then the testcases follow.
• Each testcase containsÂ M+3M+3Â lines of input.
• First line containsÂ 22Â space separated integersÂ NN,Â MM, the total number of colleges, and total number of students respectively.
• Second line containÂ NNÂ distinct space separated integersÂ RiRi, rank of theÂ ithithÂ college. HereÂ 11Â denotes a higher rank andÂ NNÂ denotes a lower rank.
• Third line containsÂ MMÂ distinct space separated integersÂ SiSi, the rank of theÂ ithithÂ student in the exam. HereÂ 11Â denotes a higher rank, i.e, maximum marks scored andÂ MMÂ denotes a lower rank, i.e, minimum marks scored.
• NextÂ MMÂ lines containÂ K+1K+1Â space separated integers which the first integerÂ KKÂ is the number of collegesÂ ithithÂ student will apply to and the nextÂ KKÂ integers describe the same.

### Output:

For each testcase, output in a single line the college in which Chef applies andÂ 00Â if he wonâ€™t be joining any college this year.

### Constraints

• 1â‰¤N,Mâ‰¤5âˆ—1041â‰¤N,Mâ‰¤5âˆ—104
• RRÂ is the permutation of integers fromÂ [1,N][1,N]
• SSÂ is the permutation of integers fromÂ [1,M][1,M]
• Sum ofÂ NNÂ over all tests is atmostÂ 3âˆ—1053âˆ—105
• Sum ofÂ MMÂ over all tests is atmostÂ 3.5âˆ—1053.5âˆ—105
• Sum ofÂ KKÂ over all students over all tests is atmostÂ 1.5âˆ—1061.5âˆ—106
• Every student applies to atleastÂ 11Â college and all the applied colleges are different.

### Sample Input 1

``````3
2 2
2 1
1 2
2 1 2
2 1 2
1 2
1
2 1
1 1
1 1
2 1
1 2
1
2 2 1``````

### Sample Output 1

``````2
1
``````

### Explanation

Case 1:Â Here since Chef has the highest rank, he gets to choose the highest rank college in his preference list first, that is college withÂ id=2.

Case 2:Â Here since there is onlyÂ 11Â college and Chef stood second, he wonâ€™t be able to apply to any of the colleges this year, so we printÂ id=0.

Case 3:Â Here since Chef is the only student and thus has the highest rank, he gets to choose the highest rank college in his preference list first, that is college withÂ id=1.

## College Admissions- CodeChef Solution in JAVA

```import java.io.BufferedReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Throwable {
StringBuilder out = new StringBuilder();
int T = Integer.parseInt(st.nextToken());
for (int tc = 0; tc < T; ++tc) {
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] R = new int[N];
for (int i = 0; i < R.length; ++i) {
R[i] = Integer.parseInt(st.nextToken());
}
int[] S = new int[M];
for (int i = 0; i < S.length; ++i) {
S[i] = Integer.parseInt(st.nextToken());
}
int[][] applied = new int[M][];
for (int i = 0; i < applied.length; ++i) {
int K = Integer.parseInt(st.nextToken());
applied[i] = new int[K];
for (int j = 0; j < applied[i].length; ++j) {
applied[i][j] = Integer.parseInt(st.nextToken()) - 1;
}
}
out.append(solve(R, S, applied)).append("\n");
}
System.out.print(out);
}
static int solve(int[] R, int[] S, int[][] applied) {
Integer[] sortedIndices = new Integer[S.length];
for (int i = 0; i < sortedIndices.length; ++i) {
sortedIndices[i] = i;
}
Arrays.sort(sortedIndices, Comparator.comparing(i -> S[i]));
boolean[] used = new boolean[R.length];
for (int i = 0; ; ++i) {
int collegeIndex = -1;
for (int j : applied[sortedIndices[i]]) {
if (!used[j] && (collegeIndex == -1 || R[j] < R[collegeIndex])) {
collegeIndex = j;
}
}
if (collegeIndex != -1) {
used[collegeIndex] = true;
}
if (sortedIndices[i] == 0) {
return collegeIndex + 1;
}
}
}
}```

Disclaimer:Â The above Problem (College Admissions) is generated byÂ CodeChef but the solution is provided byÂ Â Chase2learn.This tutorial is only forÂ EducationalÂ andÂ LearningÂ purpose.

Sharing Is Caring