Xiaoqiang and Amoeba are good friends.
Amoeba tells Xiaoqiang that amoebas, like most living organisms, have DNA. Furthermore, amoebas can reproduce asexually through division.
We abstract the genome of an amoeba as a set of $L$ genes. Each gene is a string of length $4$ (characters include uppercase and lowercase letters, digits, and the symbols <samp>~!@#$%^&()[]:;"'<>,.?/|\=-{}`). Now, $N$ amoebas have gathered together. Since they come from all over the world, we can assume that their genomes were obtained by independently and randomly selecting $L$ genes from an "amoeba gene pool" of size $M$. Humans do not currently know what genes are in this pool, but we know its size is $M$.
Suddenly, the environment changes drastically. Stimulated by the external environment, these $N$ amoebas divide simultaneously. Each amoeba splits into two. During the division process, the original amoeba's genome (the set of genes) is copied exactly into two parts, which enter the two new amoebas. In one of the two new amoebas, half of the genes mutate and are replaced by other random genes from the "amoeba gene pool." If two amoebas are produced from the same original amoeba, we call them "homologous."
Given the genomes of $2N$ amoebas, please identify the homologous partner for each amoeba.
Input
The first line contains three integers $N$, $M$, and $L$.
The next line contains $2NL \times 4$ characters, representing the elements in each set sequentially. The order of elements within a set is irrelevant.
Output
Output $2N$ lines, each containing an integer representing the homologous partner of the $i$-th amoeba (labeled starting from $1$).
Examples
Input 1
2 100 6 H[P,86(^,<n&7X_Sg"LY67m2H$n+5'!VHp5IA.@GM:4-NJsqsiG!H[P,7X_S86(^>aNQ22'B5'!V<FD!F!6xNJsq>!]dHp5I
Output 1
3 4 1 2
Input 2
See sample data download.
Note
The input file consists of two lines. The four genomes are:
"H[P,", "86(^", ",
"H$n+", "5'!V", "Hp5I", "A.@G", "M:4-", "NJsq"
"siG!", "H[P,", "7X_S", "86(^", ">aNQ", "22'B"
"5'!V", "
Clearly, 1 and 3 are homologous, and 2 and 4 are homologous.
Constraints
There are $10$ test cases in total. All data is generated randomly according to the method described in the problem. For any two non-homologous amoebas, the size of the intersection of their genomes is less than $L/2$. For two homologous amoebas, the size of the intersection of their genomes is exactly $L/2$.
| Test Case ID | $N$ | $M$ | $L$ |
|---|---|---|---|
| 1 | $400$ | $400$ | $20$ |
| 2 | $900$ | $900$ | $30$ |
| 3 | $1600$ | $1600$ | $40$ |
| 4 | $2500$ | $2500$ | $50$ |
| 5 | $3600$ | $3600$ | $60$ |
| 6 | $6400$ | $6400$ | $80$ |
| 7 | $10000$ | $10000$ | $100$ |
| 8 | $12100$ | $12100$ | $110$ |
| 9 | $14400$ | $14400$ | $120$ |
| 10 | $16900$ | $16900$ | $130$ |
The largest test data size is approximately $17\texttt{MB}$ ($2NL \times 4=17576000$). On the judging system, due to disk caching, reading the data using scanf takes less than $0.1$ seconds. Please do not use cin. Testing shows:
- A well-implemented algorithm with $O(N^2L)$ time complexity can score 30 points.
- A well-implemented algorithm with $O(N^2 + N^2L^2 / M)$ time complexity can score 50 points.