spair

At a dance contest N men and N women are invited. Both the women and the men are numbered from 1 to N. The organizers want all the 2*N guests to dance with a preferred person and request from each guest their list of preferences. This list contains the numbers of all opposite sex persons, in descending order, by preference.
Before the contest begins, the organizers must present the list of N pairs (male, female) designated for the dance. We say that an arbitrary pair (b, f) of the list is stable if it respects the following condition: any women f' before f  in the preference list of b and coupled with b' in the list, prefers b' to b. The whole list is stable if all the N pairs are stable.

Task

Knowing number N and the preference lists drafted by the 2*N persons determine (if possible) a stable list.

Input Data

Line one of file spair.in contains positive integer N. The following N lines contain the preference lists of men in the form of permutations of group {1, 2, ..., N }; the numbers on line i+1 represent the preference list of man i in descending order of preference. The following N lines contain the women's preferences in exactly the same format. The numbers of each line are separated by a space.

Output Data

The results will be written in file spair.out on N lines. A line will contain a pair of positive integers from group {1, 2, ..., N }, representing an element from the determined stable list. The first number of each pair is the number of the man, and the second is the number of his dance partner. If there is no solution, line one of the file will contain message impossible  

Restrictions

0 < n <= 1000
If there is more than one solution, the file will contain a single solution.

Example

spair.in

spair.out

Explanation

3
3 1 2
2 3 1
2 3 1
2 3 1
1 3 2
1 2 3

1 3
2 1
3 2

List
1 3
2 1
3 2
is stable.
If we took list with pairs:
1 2
2 1
3 3
The list is not stable, because pair (1 2) is not stable. In reality, man 1 prefers woman 3 over his partner (2), and woman 3 prefers man 1 over her partner (3).

Time limit: 0.8 seconds/test

prof. Dana Lica
"I. L. Caragiale" National College, Ploieşti
danal182001@yahoo.com