One of the biggest challenges in an online course platform is to recommend to a student one of its over 800 courses.
For instance, João took courses on Java and Java for the Web, with grades 10 and 9, respectively. What should he be recommended next? If we recommend him something much easier, much harder, or simply something that does not go with his profile, we will waste his time. Just as an undergraduate student is very careful for choosing the appropriate courses and not waste a semester due to poor choices, we wish to help students in this platform to make the best choices.
In this problem, we have (N) students and (M) courses. Students are numbered from 1 to (N), the courses from (1) to (M). For each student, we know which courses he or she already took and the respective grades. To recommend a course to a student, we first find another student who is closest to him or her. The distance between two students is defined as the euclidean distance between the grades of the courses both students took. If there are no shared courses, the distance is defined as infinity. Among the courses already taken by the closest student, we recommend the course with the highest grade which was not already taken by the original student. In case of a tie, recommend the course with the smallest index. If the original student already took all the courses that were taken by his closest student, no recommendation is make.
Your task is to code a program that recommend a course to all the students in the platform.
The first line has two integers $N$ and $M$, the number of students and courses, respectively. After this there are (N) blocks of lines, each one contains a line with an integer (Q_i), the amount of courses already taken by the (i)th student, and then (Q_i) lines, each one containing two integers (c) and (g), which indicate that the (i)th student got grade (g) for course (c).
*Constraints*
Print (N) lines, where the (i)th line has the course recommended to the (i)th student. If student (i) has already taken all courses that his closest student already took, print (-1).
In the first example, the distance between students is given by $sqrt((10 -9)^2)$
In the second, it is given by $sqrt((7 -5)^2 + (8 -9)^2)$
## Input
The first line has two integers $N$ and $M$, the number of students and courses, respectively. After this there are (N) blocks of lines, each one contains a line with an integer (Q_i), the amount of courses already taken by the (i)th student, and then (Q_i) lines, each one containing two integers (c) and (g), which indicate that the (i)th student got grade (g) for course (c).*Constraints* $2 <= N <= 100$ $1 <= M <= 100$ $1 <= Q_i, c <= M$ $0 <= g <= 10$ You may assume that each student has already taken at least one course that another student took.
## Output
Print (N) lines, where the (i)th line has the course recommended to the (i)th student. If student (i) has already taken all courses that his closest student already took, print (-1).
[samples]
## Note
In the first example, the distance between students is given by $sqrt((10 -9)^2)$In the second, it is given by $sqrt((7 -5)^2 + (8 -9)^2)$
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ denote the number of students and courses, respectively.
Let $ S_i \subseteq \{1, \dots, M\} \times \mathbb{R} $ be the set of course-grade pairs for student $ i \in \{1, \dots, N\} $, where $ (c, g) \in S_i $ means student $ i $ took course $ c $ with grade $ g $.
**Distance Definition**
For $ i \neq j $, define the distance $ d(i,j) $ as:
$$
d(i,j) =
\begin{cases}
\sqrt{ \sum_{(c,g) \in S_i \cap S_j} (g_i(c) - g_j(c))^2 } & \text{if } S_i \cap S_j \neq \emptyset \\
\infty & \text{otherwise}
\end{cases}
$$
where $ g_i(c) $ is the grade of student $ i $ in course $ c $, and $ S_i \cap S_j $ denotes the set of common courses with their respective grades.
**Objective**
For each student $ i \in \{1, \dots, N\} $:
1. Find $ j^* = \arg\min_{j \neq i} d(i,j) $ (the closest student; if multiple, choose the smallest index $ j $).
2. If $ d(i,j^*) = \infty $, output $-1$.
3. Else, let $ R_i = \{ c \mid (c, g) \in S_{j^*}, (c, \cdot) \notin S_i \} $ (courses taken by $ j^* $ but not by $ i $).
- If $ R_i = \emptyset $, output $-1$.
- Else, output $ \arg\max_{c \in R_i} g_{j^*}(c) $; in case of tie, choose the smallest $ c $.