You cannot submit for this problem because the homework's deadline is due.

Description

Use python3 to implement Gale-Shapley algorithm.

Submission Format

Submit a tar or zip file including a script named gale.py.

IO

Input

The first line contains the number of mans n.
The following n lines contain the preference of n men about n women.
Then followed by a blank line.
Finally, there are n lines containing the preference of n women about n men.

Output

One line.
All engaged (man, woman)-pairs sorted by the index of man.

Sample IO

This sample is the case shown on the slides.
The only difference is that man and woman are numbered with index starting from 0.

input

There are 4 men and 4 women.
The first man man0 prefers woman0>woman1>woman2>woman3.
The second man man1 prefers woman0>woman3>woman2>woman1, etc...

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

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

output

This means man0 pairs with woman1. man1 with woman3, etc...

[[0, 1], [1, 3], [2, 0], [3, 2]]