Stable Matching for Student-Project Assignment

You are given n students and m projects (with m \ge n). Each student has ranked all projects in order of preference, and each project has ranked all students. Your task is to assign each student to one project such that the matching is stable.

A matching is said to be stable if there is no pair \((s, p)\) (student \(s\) and project \(p\)) such that student \(s\) prefers project \(p\) over their assigned project, and project \(p\) prefers student \(s\) over its currently assigned student.

Implement the Gale–Shapley algorithm (also known as the Deferred Acceptance algorithm) to compute the student‐optimal stable matching.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers n and m (m \ge n), representing the number of students and projects respectively.
2. The next n lines each contain m space-separated integers. The i-th line represents the preferences of the i-th student, listing project indices in the order of preference from most preferred to least.
3. The following m lines each contain n space-separated integers. The j-th line of this section represents the preferences of the j-th project, listing student indices in the order of preference from most preferred to least.

outputFormat

Output a single line to stdout containing n space-separated integers. The i-th integer denotes the index of the project assigned to the i-th student in a stable matching.

3 3
0 1 2
1 0 2
2 0 1
2 0 1
1 2 0
0 2 1

0 1 2