Terrifying Palindrome

Interview

Time limit1.5sMemory limit1024 MB

Summary

Order n equal-length strings so their concatenation is a palindrome, or report -1 if no such order exists.

Level: Medium5 of 10
Topics: String, Hash map, Greedy
Solved: No attempts yet

Statement

The children spent the whole evening going door to door and scaring passersby. At some point they got bored and went to scare Mr. X.

Everyone knows Mr. X is terribly afraid of palindromes. So the children decided to find the largest palindrome they could and show it to him. Unfortunately, by night their imagination was nearly gone. All they could do was copy the words from the banners around them and assemble a palindrome from those.

There are $n$ banners on the street, and every banner has text of the same length $k$ . The children think a palindrome is not scary enough unless it uses at least one banner text, so they want to build a palindrome by concatenating all banner texts, each exactly once, in some order.

Help the children build a scary palindrome, or report that no palindrome can be formed from these pieces, so that Mr. X can enjoy the rest of the evening in peace.

Input

The first line contains two integers $n$ and $k$ separated by a space ( $1 \leq n, k \leq 10^6$ ).

Each of the next $n$ lines contains the text of one banner. Every text has length exactly $k$ and consists only of lowercase Latin letters.

It is guaranteed that $n \cdot k \leq 10^7$ .

Output

If a scary palindrome can be built, print $n$ numbers separated by spaces. These are the banner numbers in the order they must be concatenated to form a palindrome. Each number from $1$ to $n$ must appear exactly once in the output.

If no palindrome can be built, print the single integer $-1$ .

Examples2

Example 1
Input
```
3 2
ab
cc
ba
```
Expected output
```
1 2 3
```
Example 2
Input
```
2 3
aba
cab
```
Expected output
```
-1
```