Andi and Budi were given an assignment to tidy up their bookshelf of $n$ books. Each book is represented by the book title — a string $s_i$ numbered from $1$ to $n$, each with length $m$. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string $a$ occurs before a string $b$ in asc-desc-ending order if and only if in the first position where $a$ and $b$ differ, the following holds:

if it is an odd position, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$;

if it is an even position, the string $a$ has a letter that appears later in the alphabet than the corresponding letter in $b$.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 10^6$).

The $i$-th of the next $n$ lines contains a string $s_i$ consisting of $m$ uppercase Latin letters — the book title. The strings are pairwise distinct.


-----Output-----

Output $n$ integers — the indices of the strings after they are sorted asc-desc-endingly.


-----Examples-----

Input
5 2
AA
AB
BB
BA
AZ
Output
5 2 1 3 4


-----Note-----

The following illustrates the first example.

Difficulty: EASY
Tags: String algorithms

Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
(n, m) = [int(x) for x in input().strip().split()]

def encode(x):
	accum = 1
	res = 0
	base_A = ord('A')
	base_Z = ord('Z')
	for idx in range(m, 0, -1):
		c = x[idx - 1]
		if idx % 2 != 0:
			res += (ord(c) - base_A) * accum
		else:
			res += (base_Z - ord(c)) * accum
		accum *= 26
	return res
strings = [[0, 0] for _ in range(n)]
for i in range(n):
	x = input().rstrip()
	strings[i] = (i + 1, encode(x))
strings.sort(key=lambda x: x[1])
print(' '.join([str(x[0]) for x in strings]))


(n, m) = map(int, input().split())
l = []
d = {}
for i in range(n):
	l += [input()]
	d[l[i]] = i
z = list(l)
for i in range(m - 1, -1, -1):
	if i % 2 == 0:
		l.sort(key=lambda x: x[i])
	else:
		l.sort(reverse=True, key=lambda x: x[i])
for i in l:
	print(d[i] + 1, end=' ')


(n, m) = map(int, input().split())
a = [None] * n
for i in range(n):
	s = input()
	ns = ''
	cur = 0
	flag = 1
	for j in range(m):
		if j % 2:
			ns += chr(155 - ord(s[j]))
		else:
			ns += s[j]
	a[i] = [ns, i]
print(*[v[1] + 1 for v in sorted(a)])


import math
import string

def korea(m):
	return lambda x: x[m]

def convert_to_numbers(word, hash_function):
	l = []
	for i in range(len(word)):
		if i % 2 == 0:
			l.append(hash_function[word[i]])
		else:
			l.append(-hash_function[word[i]])
	return tuple(l)

def main_function():
	(n, m) = [int(i) for i in input().split(' ')]
	alphabet = list(string.ascii_uppercase)
	hash_function = {}
	for i in range(len(alphabet)):
		hash_function[alphabet[i]] = i
	hash_function_for_position = {}
	data = []
	for i in range(n):
		data.append(input())
	data_tuple = []
	for i in data:
		data_tuple.append(convert_to_numbers(i, hash_function))
	for i in range(len(data)):
		hash_function_for_position[data[i]] = i + 1
	data_tuple_sorted = sorted(data, key=lambda x: convert_to_numbers(x, hash_function))
	for i in range(len(data_tuple_sorted)):
		if i == len(data_tuple_sorted) - 1:
			print(hash_function_for_position[data_tuple_sorted[i]])
		else:
			print(hash_function_for_position[data_tuple_sorted[i]], end=' ')
main_function()


l0 = [chr(x) for x in range(65, 91)]
l1 = reversed(l0)
dic = dict(zip(l0, l1))
(a, b) = map(int, input().split())
l2 = []
for _ in range(a):
	s = list(input())
	for i in range(1, b, 2):
		s[i] = dic[s[i]]
	l2.append(''.join(s))
l3 = sorted(range(a), key=lambda x: l2[x])
print(*[i + 1 for i in l3])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from functools import cmp_to_key
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	words = ['']
	for i in range(n):
		words += [list(map(ord, input()))]
	a = list(range(1, n + 1))

	def compare(x, y):
		for i in range(m):
			if not i % 2:
				if words[x][i] != words[y][i]:
					return 1 if words[x][i] > words[y][i] else -1
			elif words[x][i] != words[y][i]:
				return -1 if words[x][i] > words[y][i] else 1
		return 0
	a = sorted(a, key=cmp_to_key(compare))
	for i in a:
		print(i)


(n, k) = map(int, input().split())
lists = []
for _ in range(n):
	lists.append(input())

def change(arr):
	w = arr[0]
	new = []
	for i in range(1, len(w), 2):
		for (index, word) in enumerate(arr):
			x = chr(ord('Z') - (ord(word[i]) - ord('A')))
			arr[index] = word[:i] + x + word[i + 1:]
order = [i for i in range(1, n + 1)]
change(lists)
(a, b) = zip(*sorted(zip(lists, order)))
for ele in b:
	print(ele, end=' ')


(n, m) = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append([list(input()), i + 1])
alps = list(map(chr, range(65, 91)))
d = {}
for a in range(len(alps)):
	d[alps[a]] = alps[len(alps) - 1 - a]
for i in range(n):
	for j in range(m):
		if j % 2:
			arr[i][0][j] = d[arr[i][0][j]]
arr.sort()
for i in range(n):
	print(arr[i][1], end=' ')


(n, m) = map(int, input().split())
letters = [0] * n
for i in range(n):
	a = input()
	cur = 0
	change = True
	for j in range(m):
		cur = cur * 26 + change * ord(a[j])
		change *= -1
	letters[i] = [cur, i]
print(*[sum([letter[1], 1]) for letter in sorted(letters)])


from sys import stdin

def main():
	input = stdin.readline
	(n, m) = [int(i) for i in input().split()]
	words = [(input(), i) for i in range(n)]
	words.sort(key=lambda x: tuple((-ord(x[0][i]) if i & 1 else ord(x[0][i]) for i in range(len(x[0])))))
	print(' '.join(map(str, [i[1] + 1 for i in words])))
main()


(n, m) = map(int, input().split())
a = []
for i in range(1, n + 1):
	s = input()
	ins = []
	for j in range(0, m):
		if j & 1:
			ins.append(chr(ord('Z') - ord(s[j]) + ord('A')))
		else:
			ins.append(s[j])
	a.append([str(ins), i])
a.sort()
for x in a:
	print(x[1], end=' ')


(n, m) = list(map(int, input().split()))
books = []
for idx in range(n):
	books.append((input(), idx + 1))
for i in range(m - 1, -1, -1):
	if i % 2:
		books.sort(key=lambda x: x[0][i], reverse=True)
	else:
		books.sort(key=lambda x: x[0][i], reverse=False)
indexes = [i[1] for i in books]
print(*indexes)


(n, m) = map(int, input().split())
l = []
for i in range(n):
	s = input()
	l.append([s, i + 1])
for i in range(m - 1, -1, -1):
	if i % 2:
		l.sort(key=lambda x: -ord(x[0][i]))
	else:
		l.sort(key=lambda x: ord(x[0][i]))
for i in l:
	print(i[1], end=' ')


(n, m) = map(int, input().split())
print(*[x[0] for x in sorted(map(lambda x: [x[0] + 1, [x[1][j] if j % 2 == 0 else chr(155 - ord(x[1][j])) for j in range(m)]], enumerate([input() for i in range(n)])), key=lambda x: x[1])])


(n, m) = [int(i) for i in input().split()]
l = []
for i in range(1, n + 1):
	temp = input().strip()
	w = []
	for j in range(m):
		z = temp[j]
		if j % 2 == 0:
			w.append(ord(z))
		else:
			w.append(ord(z) * -1)
	w += [i]
	l += [w]
l.sort()
for i in range(n):
	print(l[i][-1], end=' ')


class pairs:

	def __init__(self, num, index):
		self.num = num
		self.index = index

def get_my_key(pair):
	return pair.num
a = input().split()
arr_size = int(a[0])
str_size = int(a[1])
arr = []
for i in range(arr_size):
	arr.append(input())
p_arr = []
for (ind, num) in enumerate(arr):
	p_arr.append(pairs(num, ind + 1))
for i in range(arr_size):
	for j in range(1, str_size, 2):
		p_arr[i].num = p_arr[i].num[:j] + chr(25 - ord(p_arr[i].num[j]) + 2 * ord('A')) + p_arr[i].num[j + 1:]
p_arr.sort(key=get_my_key)
for i in range(arr_size):
	print(p_arr[i].index, end=' ')


def main():
	lista = []
	(line, lenght) = input().split()
	line = int(line)
	lenght = int(lenght)
	dicio: dict = {}
	for i in range(line):
		text = input()
		dicio[text] = i + 1
		lista.append(text)
	for i in range(lenght - 1, -1, -1):
		if (i + 1) % 2 != 0:
			lista.sort(key=lambda x: x[i])
		else:
			lista.sort(key=lambda x: x[i], reverse=True)
	for word in lista:
		print(dicio[word], end=' ')
main()


import os
import sys
import math
from io import BytesIO, IOBase
from collections import deque, defaultdict, OrderedDict, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, insort, bisect_left
from functools import lru_cache
from itertools import permutations
sys.setrecursionlimit(10 ** 6)

def STRIN():
	return input()

def INTIN():
	return int(input())

def LINT():
	return list(map(int, input().split()))

def LSTR():
	return list(map(str, input().split()))

def MINT():
	return map(int, input().split())

def MSTR():
	return map(str, input().split())

def solve():
	(n, m) = map(int, input().split())
	s = []
	d = {}
	for i in range(n):
		s.append(list(input()))
	for j in range(n):
		for k in range(len(s[i])):
			if (k + 1) % 2 == 0:
				s[j][k] = chr(90 - (ord(s[j][k]) + 26 - 91))
	for i in range(len(s)):
		d[''.join(s[i])] = i + 1
	s.sort()
	for i in s:
		print(d[''.join(i)], end=' ')

def main():
	solve()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, m) = list(map(int, input().split()))
l = []
for _ in range(n):
	book = list(input())
	book[1::2] = map(lambda x: chr(155 - ord(x)), book[1::2])
	l.append(book)
print(*sorted(range(1, n + 1), key=lambda x: l[x - 1]))


(n, m) = (int(x) for x in input().split())
arr = [0] * n
d = {}
for i in range(n):
	arr[i] = input()
	d[arr[i]] = i + 1
for i in range(m - 1, -1, -1):
	arr.sort(key=lambda x: x[i], reverse=i % 2 != 0)
for i in arr:
	print(d[i], end=' ')


(n, m) = map(int, input().split())
l = [(lambda x: [i + 1, [x[j] if j % 2 == 0 else chr(ord('Z') - ord(x[j]) + ord('A')) for j in range(m)]])(input()) for i in range(n)]
print(*[i[0] for i in sorted(l, key=lambda x: x[1])])


(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(str(input()))
new_l = []
for i in range(len(l)):
	new_s = ''
	for j in range(len(l[i])):
		if j % 2 != 0:
			new_s += chr(90 - (ord(l[i][j]) - 65))
		else:
			new_s += l[i][j]
	new_l.append((new_s, i + 1))
new_l.sort()
x = []
for i in range(len(new_l)):
	x.append(new_l[i][1])
print(*x)


(n, m) = map(int, input().split())
a = []
for k in range(n):
	x = input()
	y = ''
	for i in range(m):
		if i % 2 != 0:
			y = y + chr(155 - ord(x[i]))
		else:
			y = y + x[i]
	a.append((y, k + 1))
a.sort()
for j in range(n):
	print(a[j][1], end=' ')


(n, m) = input().split(' ')
n = int(n)
m = int(m)
strings = []
str_idxs = {}
sol = []
for i in range(n):
	string = input()
	s = [None] * m
	for j in range(1, m, 2):
		c = ord(string[j]) - ord('A')
		s[j] = chr(ord('A') + (25 - c))
	for (j, letter) in enumerate(s):
		if letter == None:
			s[j] = string[j]
	aux = ''
	new_s = aux.join(s)
	str_idxs[new_s] = i + 1
	sol.append(new_s)
sol.sort()
for i in range(n):
	print(str_idxs[sol[i]], end=' ')


import sys
pl = 1
sys.setrecursionlimit(10 ** 5)
if pl:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('outpt.txt', 'w')

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def ff():
	sys.stdout.flush()

def google(tc, *ans):
	print('Case #' + str(tc) + ':', *ans)

def bits(i, n):
	p = bin(i)[2:]
	return (n - len(p)) * '0' + p
t = 1
f = t
mod = 10 ** 9 + 7
while t:
	t -= 1
	(n, m) = mi()
	a = []
	for i in range(n):
		s = si()
		p = ''
		for j in range(m):
			if j % 2 == 0:
				p += s[j]
			else:
				w = ord(s[j]) - ord('a')
				p += chr(ord('a') + 25 - w)
		a.append([p, i + 1])
	a.sort()
	for i in a:
		print(i[1], end=' ')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
d = {}
w = []
for i in range(n):
	s = input()[:-1]
	d[s] = i
	w.append(s)
for i in range(m - 1, -1, -1):
	if i % 2:
		w.sort(key=lambda x: x[i], reverse=True)
	else:
		w.sort(key=lambda x: x[i])
for i in w:
	print(d[i] + 1, end=' ')


(n, m) = map(int, input().split())
s = []
for i in range(1, n + 1):
	x = input()
	new = ''
	for j in range(m):
		if j % 2:
			new += chr(155 - ord(x[j]))
		else:
			new += x[j]
	s.append([new, i])
print(*[i[1] for i in sorted(s)])


def compare(a, b):
	for i in range(len(a)):
		if a[i] == b[i]:
			continue
		if i % 2 == 0:
			if a[i] > b[i]:
				return True
			else:
				return False
		if a[i] < b[i]:
			return True
		else:
			return False

def val(a):
	ans = ''
	for i in range(len(a)):
		if i % 2 == 1:
			ans += chr(ord('Z') - ord(a[i]) + ord('A'))
		else:
			ans += a[i]
	return ans
(n, m) = [int(x) for x in input().split()]
list = []
for i in range(n):
	list.append(input())
diction = {}
for i in range(n):
	diction[list[i]] = i + 1
list.sort(key=val)
for i in range(n):
	print(diction[list[i]], end=' ')


from sys import stdin
input = stdin.readline

def func():
	for i in range(m - 1, -1, -1):
		if (i + 1) % 2 == 0:
			books.sort(key=lambda x: x[1][i], reverse=True)
		else:
			books.sort(key=lambda x: x[1][i])
	ans = []
	for book in books:
		ans.append(book[0])
	print(*ans)
(n, m) = map(int, input().split())
books = []
for i in range(1, n + 1):
	books.append((i, input()))
func()


(n, m) = map(int, input().split())
c = lambda x: chr(ord('Z') - ord(x) + ord('A'))
p = lambda x, ind: x if ind % 2 == 0 else c(x)
for_sort = lambda x: x[1]
lam = lambda x, i: [i + 1, [p(x[j], j) for j in range(m)]]
print(*[i[0] for i in sorted([lam(input(), i) for i in range(n)], key=for_sort)])


from collections import defaultdict, Counter, deque
from math import sqrt, log10, log, floor, factorial, gcd
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
import sys, io, os
input = sys.stdin.readline
inf = float('inf')
mod = 10 ** 9 + 7

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
t = 1
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	l = []
	for i in range(1, n + 1):
		temp = input().strip()
		l.append([ord(temp[i]) * (-1) ** (i % 2) for i in range(m)])
		l[-1].append(i)
	l.sort()
	for i in range(n):
		print(l[i][-1], end=' ')


(n, m) = map(int, input().split())
strings = []
for i in range(n):
	strings.append([input(), i + 1])
for s in strings:
	for i in range(m):
		if i & 1:
			x = chr(25 - (ord(s[0][i]) - ord('A')) + ord('A'))
			s[0] = s[0][:i] + x + s[0][i + 1:]
strings.sort()
for x in strings:
	print(x[1], end=' ')


def to_tuple(s: str) -> tuple:
	return tuple((ord(c) if i % 2 == 0 else -ord(c) for (i, c) in enumerate(s)))

def main():
	(n, m) = map(int, input().split())
	for e in sorted([(to_tuple(input()), i) for i in range(1, n + 1)]):
		print(e[-1])
main()


nm = list(map(int, input().split(' ')))
struct = []
n = True
for idx in range(nm[0]):
	struct.append([input(), str(idx + 1)])
if nm[1] % 2 != 0:
	n = False
for idx1 in range(nm[1] - 1, -1, -1):
	struct.sort(key=lambda x: x[0][idx1], reverse=n)
	n = not n
for i in range(nm[0]):
	print(struct[i][1], end=' ')


(n, m) = map(int, input().split())
strings = []
for i in range(n):
	strings.append([input(), i + 1])
for i in range(m - 1, -1, -1):
	if i & 1:
		strings.sort(key=lambda x: -ord(x[0][i]))
	else:
		strings.sort(key=lambda x: ord(x[0][i]))
for i in strings:
	print(i[1], end=' ')


from sys import stdin
from heapq import heappush, heappop
(n, m) = map(int, stdin.readline().split())
arr = []
d = {}
for i in range(n):
	l = input()
	d[l] = i + 1
	arr.append(list(l))
for i in range(m - 1, -1, -1):
	if (i + 1) % 2 != 0:
		arr.sort(key=lambda x: ord(x[i]))
	else:
		arr.sort(reverse=True, key=lambda x: ord(x[i]))
ans = []
for a in arr:
	ans.append(d[''.join(a)])
print(*ans)


(n, m) = map(int, input().split())
a = [None] * n
for i in range(n):
	s = input()
	cur = 0
	flag = 1
	for j in range(m):
		cur = cur * 26 + flag * ord(s[j])
		flag = -flag
	a[i] = [cur, i]
a.sort()
print(*[v[1] + 1 for v in a])


import math
import string

def main_function():
	(n, m) = [int(i) for i in input().split(' ')]
	alphabet = list(string.ascii_uppercase)
	hash_function = {}
	for i in range(len(alphabet)):
		hash_function[alphabet[i]] = i
	reverse_hash_function = {}
	for i in hash_function:
		reverse_hash_function[hash_function[i]] = i
	data = []
	for i in range(n):
		data.append(list(input()))
	for i in range(len(data)):
		for j in range(len(data[i])):
			if j % 2 == 1:
				data[i][j] = reverse_hash_function[25 - hash_function[data[i][j]]]
	for i in range(len(data)):
		data[i] = tuple(data[i])
	hash_position = {}
	for i in range(len(data)):
		hash_position[data[i]] = i + 1
	data.sort(key=lambda x: [i for i in x])
	for i in range(len(data)):
		if i == len(data) - 1:
			print(hash_position[data[i]])
		else:
			print(hash_position[data[i]], end=' ')
main_function()


def solve():
	(n, m) = map(int, input().split())
	l = []
	d = {}
	for i in range(n):
		l.append(input())
		d[l[i]] = i
	for i in range(m - 1, -1, -1):
		if i % 2 == 0:
			l.sort(key=lambda x: x[i])
		else:
			l.sort(reverse=True, key=lambda x: x[i])
	for i in l:
		print(d[i] + 1, end=' ')
solve()