Sắp xếp tăng-giảm

Trên giá sách có $n$ quyển sách. Quyển thứ $i$ có tên là xâu $s_i$ gồm đúng $m$ chữ cái in hoa. Các tên sách đôi một khác nhau.

An muốn xếp sách theo thứ tự từ điển tăng dần, còn Bình muốn xếp theo thứ tự từ điển giảm dần. Để dung hoà, hai bạn thống nhất một thứ tự mới gọi là thứ tự tăng-giảm: các vị trí lẻ so sánh tăng dần, còn các vị trí chẵn so sánh giảm dần (vị trí trong xâu được đánh số từ $1$).

Cụ thể, xâu $a$ đứng trước xâu $b$ trong thứ tự tăng-giảm khi và chỉ khi tại vị trí $p$ đầu tiên mà $a$ và $b$ khác nhau:

• nếu $p$ lẻ thì $a_p$ đứng trước $b_p$ trong bảng chữ cái;
• nếu $p$ chẵn thì $a_p$ đứng sau $b_p$ trong bảng chữ cái.

Hãy sắp xếp $n$ tên sách theo thứ tự tăng-giảm.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa xâu $s_i$ gồm $m$ chữ cái in hoa.

Dữ liệu ra

In ra $n$ số nguyên trên một dòng: chỉ số của các quyển sách (theo thứ tự nhập vào, đánh số từ $1$) sau khi đã sắp xếp theo thứ tự tăng-giảm.

Ràng buộc

• $1\le n·m\le {10}^6$
• Mỗi $s_i$ gồm đúng $m$ chữ cái trong bảng chữ cái in hoa $\text{A}\dots \text{Z}$
• Các xâu $s_1,s_2,\dots ,s_n$ đôi một khác nhau

Ví dụ