Amoeba Genome Homolog Pairing

Two amoebas are said to be homologous if they originate from the same parent amoeba. Initially, an amoeba has its genome represented as a set of L genes. Each gene is a 4‐character string. In a population, there are N original amoebas (each with a gene set of size \(L\)) generated by choosing genes independently from a gene bank of size \(M\)). When the environment changes, every amoeba splits into two offspring. The parent's genome is exactly copied in both offspring. However, in one of the offspring exactly half of the genes (i.e. \(\frac{L}{2}\)) are replaced by different genes (picked uniformly at random from the gene bank, and different from the copied gene).

You are given the genomes of the resulting \(2N\) amoebas. Your task is to pair them, so that for each pair (i.e. the two offspring from the same parent), the two genomes share exactly \(\frac{L}{2}\) genes in common.

inputFormat

The first line contains three integers \(N\), \(M\) and \(L\) where \(N\) is the number of original amoebas, \(M\) is the size of the amoeba gene bank, and \(L\) is the number of genes in each genome.

Each of the following \(2N\) lines contains \(L\) strings separated by spaces, each representing a gene. All genes are 4-character strings. Note that the order of the \(2N\) genomes is random.

outputFormat

Output \(2N\) lines. The \(i\)-th line (1-indexed) should contain the index (also 1-indexed) of the genome which is homologous to the \(i\)-th input genome.

sample

2 100 4
A B C D
A B X Y
E F G H
E F W Z

2
1
4
3