Overview

For each scholarship, select the person with the highest evaluation score among the applicants (breaking ties by smallest applicant number), and output that number. If there are no applicants, output \(0\).

Analysis

This problem simply requires determining the top-priority person from the “list of applicants associated with scholarship \(i\)” based on the given conditions.
In other words, for each scholarship, we iterate through the applicants and keep updating the “current best” to obtain the answer.

The two key observations are:

• The recipient selection rule is “maximize (evaluation score) + tiebreak (smallest number)”, so the comparison rule is clear, and the winner is always determined by examining the entire list.
• Since the constraint gives \(\sum K_i \le 2 \times 10^5\), it is fast enough to look at each applicant across all scholarships exactly once in total.

A naive approach like “sort the applicants for each scholarship and take the best” would cost \(O(K_i \log K_i)\) per scholarship, totaling \(O\!\left(\sum K_i \log K_i\right)\), which is wasteful (and tends to be unnecessarily slow for the largest cases).
However, since we only need to find “the single best”, the optimal approach is to update the best via a linear scan without sorting.

Example: If a scholarship’s applicants are [3, 5, 2] with evaluation scores \(P_3=80, P_5=90, P_2=90\):
- The maximum evaluation score is \(90\) (applicants 5 and 2 are tied) - Among tied applicants, number 2 wins since it is smaller
→ The answer is 2
This is obtained during the scan by simply updating whenever “the evaluation score is higher, or the score is tied and the number is smaller”.

Algorithm

1. Store applicant \(j\)’s evaluation score \(P_j\) in an array (using \(1\)-indexed makes it easy to correspond with applicant numbers).
2. For each scholarship:
   • If \(K_i=0\), output 0.
   • Otherwise, maintain best (current best applicant number) and bestP (their evaluation score), and iterate through the applicant list from the beginning.
   • When examining applicant \(c\), update if:
     • \(P_c > bestP\) (higher evaluation score)
     • or \(P_c = bestP\) and \(c < best\) (tied score but smaller number)
3. Output best for each scholarship.

This comparison rule directly achieves “maximum evaluation score, with smallest number as tiebreaker”.

Complexity

• Time complexity: \(O\!\left(M + \sum_{i=1}^{N} K_i\right)\)
  (Reading evaluation scores takes \(O(M)\), and processing each applicant ID once in total takes \(O(\sum K_i)\))
• Space complexity: \(O(M)\)
  (For storing the evaluation score array \(P\))

Implementation Notes

• Since the input size is large, we read all input at once using sys.stdin.buffer.read() and speed things up with split() → map(int, ...).

• Since applicant numbers range from \(1\) to \(M\), we prepare an evaluation score array of size P[M+1] so that P[c] can be accessed directly.

• Forgetting the tiebreak (number comparison when scores are tied) will result in WA, so it is important to write the update condition precisely as:
  pc > bestP or (pc == bestP and c < best)

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    P = [0] * (M + 1)
    for j in range(1, M + 1):
        P[j] = next(it)

    out_lines = []
    for _ in range(N):
        k = next(it)
        if k == 0:
            out_lines.append("0")
            continue
        best = 0
        bestP = -1
        for _ in range(k):
            c = next(it)
            pc = P[c]
            if pc > bestP or (pc == bestP and c < best):
                bestP = pc
                best = c
        out_lines.append(str(best))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.