Stable Matching: Doctors and Patients

You are given N doctors and M patients along with their preference lists. Each doctor has a preference list ranking the patients, and each patient has a preference list ranking the doctors. Your task is to compute a stable matching between doctors and patients using the Gale–Shapley algorithm.

A matching is stable if there is no doctor–patient pair (d, p) such that doctor d prefers patient p over their current assignment and patient p also prefers doctor d over their current assignment. In mathematical terms, if we denote by R_p(d) the ranking of doctor d in patient p's list (with lower numbers indicating higher preference), then a matching is stable if
\(\forall\; (d, p)\ not\ in\ matching,\ either\ R_{p}(current(d)) \le R_{p}(d) \; or \; R_{d}(current(p)) \le R_{d}(p)\).\)

Note: The input is formatted in a specific way as described below. You need to read the input from stdin and write the output to stdout.

inputFormat

The input is given from stdin as follows:

1. The first line contains two integers: N (number of doctors) and M (number of patients).
2. The second line is the literal string P1.
3. The next N lines each describe the preference list of a doctor in the format: i: a, b, c, ... where i is the doctor's id and a, b, c, ... are the patient ids in order of preference.
4. The next line is the literal string P2.
5. The following M lines each describe the preference list of a patient in the format: i: a, b, c, ... where i is the patient's id and a, b, c, ... are the doctor ids in order of preference.

outputFormat

The output should be written to stdout and consist of N lines (one for each doctor who is assigned a patient). Each line contains two integers separated by a space, representing the doctor's id and the corresponding patient's id, respectively.

## sample

4 4
P1
0: 2, 1, 3
1: 0, 2, 3
2: 3, 0, 1
3: 1, 2, 0
P2
0: 1, 2, 3
1: 3, 0, 2
2: 0, 1, 3
3: 2, 1, 0

0 2
1 0
2 3
3 1

</p>