Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $s$.

In other words, you are given a string $s$ consisting of lowercase Latin letters.

Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $i$-th tile to $j$-th tile has a cost equal to $|index(s_i) - index(s_j)|$, where $index(c)$ is the index of the letter $c$ in the alphabet (for example, $index($'a'$)=1$, $index($'b'$)=2$, ..., $index($'z'$)=26$) .

Polycarp wants to get to the $n$-th tile for the minimum total cost, but at the same time make maximum number of jumps.

In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps.

Polycarp can visit each tile at most once.

Polycarp asks you to help — print the sequence of indices of string $s$ on which he should jump.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

Each test case is given by the string $s$ ($2 \le |s| \le 2 \cdot 10^5$), where $|s|$ — is the length of string $s$. The string $s$ consists of lowercase Latin letters.

It is guaranteed that the sum of string lengths $s$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

The answer to each test case consists of two lines.

In the first line print two integers $cost$, $m$, where $cost$ is the minimum total cost of the path, and $m$ is the maximum number of visited tiles Polycarp can make to get to $n$-th tiles for the minimum total cost $cost$ (i.e. the number of jumps is $m-1$).

In the next line print $m$ different numbers $j_1, j_2, \dots, j_m$ ($1 \le j_i \le |s|$) — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $1$ (that is, $j_1=1$) and the last number must be the value of $|s|$ (that is, $j_m=|s|$).

If there are multiple answers, print any of them.


-----Examples-----

Input
6
logic
codeforces
bca
aaaaaaaaaaa
adbaadabad
to
Output
9 4
1 4 3 5
16 10
1 8 3 4 9 5 2 6 7 10
1 2
1 3
0 11
1 8 10 4 3 5 7 2 9 6 11
3 10
1 9 5 4 7 3 8 6 2 10
5 2
1 2


-----Note-----

In the first test case, the required path corresponds to the picture:

In this case, the minimum possible total cost of the path is achieved. Since $index($'l'$)=12$, $index($'o'$)=15$, $index($'g'$)=7$, $index($'i'$)=9$, $index($'c'$)=3$, then the total cost of the path is $|12-9|+|9-7|+|7-3|=3+2+4=9$.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Constructive algorithms


Solutions:
for _ in range(int(input())):
	s = list(input())
	(first, last) = (s[0], s[-1])
	min_way = abs(ord(s[0]) - ord(s[-1]))
	if first > last:
		en = sorted(enumerate(s, 1), key=lambda x: x[1], reverse=True)
		s = ''.join(sorted(s, reverse=True))
	else:
		en = sorted(enumerate(s, 1), key=lambda x: x[1])
		s = ''.join(sorted(s))
	(l_idx, r_idx) = (s.find(first), s.rfind(last))
	print(min_way, r_idx - l_idx + 1)
	path = [i[0] for i in en[l_idx:r_idx + 1]]
	print(' '.join(map(str, path)))


t = int(input())
results = []
for i in range(t):
	s = input()
	result = []
	indices = {}
	for (idx, c) in enumerate(s):
		if s[0] <= c and c <= s[-1] or (s[-1] <= c and c <= s[0]):
			c = ord(c)
			if c not in indices.keys():
				indices[c] = []
			indices[c].append(idx + 1)
	dir = -1 if s[0] > s[-1] else 1
	for i in range(ord(s[0]), ord(s[-1]) + dir, dir):
		if i in indices.keys():
			result.extend(indices[i])
	results.append(((abs(ord(s[-1]) - ord(s[0])), len(result)), [str(item) for item in result]))
for item in results:
	print(item[0][0], item[0][1])
	print(' '.join(item[1]))


from collections import defaultdict

def solution(string):
	min_step = ord(string[0]) - ord(string[-1])
	ans = ['1']
	char_to_idx = defaultdict(list)
	for i in range(1, len(string) - 1):
		char_to_idx[ord(string[i])].append(str(i + 1))
	inc = 1 if min_step < 0 else -1
	for key in range(ord(string[0]), ord(string[-1]) + inc, inc):
		for idx in char_to_idx[key]:
			ans.append(idx)
	ans.append(str(len(string)))
	print('%d %d' % (abs(min_step), len(ans)))
	print(' '.join(ans))
t = int(input())
for _ in range(t):
	solution(input())


def readNums():
	return [int(i) for i in input().split()]
n = int(input())
for i in range(n):
	s = input()
	r = False
	if s[0] > s[-1]:
		r = True
	a = min(s[0], s[-1])
	b = max(s[0], s[-1])
	s = s[1:-1]
	l = sorted(zip(s, range(len(s))))
	ans = []
	for (j, k) in l:
		if a <= j <= b:
			ans.append(str(k + 2))
	if r:
		ans = ans[::-1]
	print(abs(ord(a) - ord(b)), len(ans) + 2)
	ans = ['1'] + ans + [str(len(s) + 2)]
	print(' '.join(ans))


def ordonner(a):
	return ord(a) - 96
t = int(input())
result = []
for i in range(t):
	s = input()
	n = len(s)
	indices = [[] for j in range(26)]
	Lindexes = list(map(ordonner, s))
	interm = Lindexes[1:-1]
	for j in range(n - 2):
		indices[interm[j] - 1].append(str(j + 2))
	interm.sort()
	if Lindexes[0] > Lindexes[-1]:
		interm.reverse()
	visitedTiles = ['1']
	(start, end) = (min(Lindexes[0], Lindexes[-1]), max(Lindexes[0], Lindexes[-1]))
	for j in interm:
		if start <= j <= end:
			visitedTiles += indices[j - 1]
			indices[j - 1] = []
	cost = abs(Lindexes[0] - Lindexes[-1])
	visitedTiles.append(str(n))
	result.append(str(cost) + ' ' + str(len(visitedTiles)))
	result.append(' '.join(visitedTiles))
for i in result:
	print(i)


t = int(input())
alps = 'abcdefghijklmnopqrstuvwxyz'
alps_dict = dict()
for (i, char) in enumerate(alps):
	alps_dict[char] = i
for _ in range(t):
	s = input().strip()
	arr = [[] for i in range(26)]
	for i in range(1, len(s) - 1):
		char = s[i]
		arr[alps_dict[char]].append(i + 1)
	(st, ed) = (alps_dict[s[0]], alps_dict[s[-1]])
	(_cost, _cnt) = (abs(st - ed), 2)
	path = [1]
	if st <= ed:
		for i in range(st, ed + 1):
			for idx in arr[i]:
				path.append(idx)
			_cnt += len(arr[i])
	else:
		for i in range(st, ed - 1, -1):
			for idx in arr[i]:
				path.append(idx)
			_cnt += len(arr[i])
	path.append(len(s))
	print(_cost, _cnt)
	print(' '.join([str(i) for i in path]))


from collections import defaultdict
N = int(input())
for _ in range(N):
	K = input().strip('\r\n')
	dp = defaultdict(lambda : [])
	A = ord(K[0])
	B = ord(K[-1])
	state = A <= B
	dist = abs(B - A)
	for i in range(len(K)):
		v = ord(K[i])
		if state and v >= A and (v <= B):
			dp[v].append(i + 1)
		if not state and v >= B and (v <= A):
			dp[v].append(i + 1)
	jump = 0
	ans = []
	if state:
		P = A
		while P <= B:
			ans.extend(dp[P])
			jump += len(dp[P])
			P += 1
	else:
		P = A
		while P >= B:
			ans.extend(dp[P])
			jump += len(dp[P])
			P -= 1
	print(f'{dist} {jump}')
	print(' '.join([str(x) for x in ans]))


t = int(input())
alphabet = 'abcdefghijklmnopqrstuvwxyz'
d = {alphabet[i]: i + 1 for i in range(26)}
d00 = {alphabet[i]: i for i in range(26)}
for ncase in range(1, t + 1):
	s = [i for i in input()]
	d0 = {c: [] for c in alphabet}
	for i in range(len(s)):
		d0[s[i]].append(i + 1)
	if s[0] == s[-1]:
		ans = d0[s[0]]
		cost = 0
	elif s[0] < s[-1]:
		ans = []
		for i in range(d00[s[0]], d00[s[-1]] + 1):
			ans += d0[alphabet[i]]
	else:
		ans = []
		for i in range(d00[s[-1]], d00[s[0]] + 1):
			d0[alphabet[i]].reverse()
			ans += d0[alphabet[i]]
		ans.reverse()
	cost = abs(d[s[-1]] - d[s[0]])
	m = len(ans)
	print(cost, m)
	print(' '.join((str(i) for i in ans)))


def decode(s, n):
	dictx = {}
	for i in range(n):
		index = ord(s[i]) - 96
		try:
			dictx[index].append(i)
		except KeyError:
			dictx[index] = []
			dictx[index].append(i)
	return dictx
for z in range(int(input())):
	m = 0
	s = input()
	length = len(s)
	dict_0 = decode(s, length)
	(beg, fin) = (ord(s[0]) - 96, ord(s[length - 1]) - 96)
	cost = abs(beg - fin)
	ans = []
	symbol = ' '
	if beg <= fin:
		for i in range(beg, fin + 1):
			try:
				m += len(dict_0[i])
				for j in dict_0[i]:
					ans.append(str(j + 1))
			except KeyError:
				continue
	else:
		for i in range(fin, beg + 1):
			try:
				m += len(dict_0[i])
				dict_0[i].reverse()
				for j in dict_0[i]:
					ans.append(str(j + 1))
			except KeyError:
				continue
		ans.reverse()
	print('{} {}'.format(cost, m))
	print(symbol.join(tuple(ans)))


def sign(n):
	if n > 0:
		return 1
	elif n == 0:
		return 404
	else:
		return -1
n = int(input())
full_ans = []
for m in range(n):
	inp_str = input()
	max_s = max(inp_str[0], inp_str[-1])
	min_s = min(inp_str[0], inp_str[-1])
	sybls_indxs = dict()
	ans = [str(ord(max_s) - ord(min_s)), str(1)]
	for i in range(1, len(inp_str) - 1):
		if min_s <= inp_str[i] <= max_s:
			if inp_str[i] not in sybls_indxs.keys():
				sybls_indxs[inp_str[i]] = [str(i + 1)]
			else:
				sybls_indxs[inp_str[i]].append(str(i + 1))
	one = sign(ord(inp_str[-1]) - ord(inp_str[0]))
	for i in range(ord(inp_str[0]), ord(inp_str[-1]) + one, one):
		if chr(i) in sybls_indxs:
			ans += sybls_indxs[chr(i)]
	ans.append(str(len(inp_str)))
	full_ans.append(ans)
for ans in full_ans:
	print(ans[0], len(ans[1:]), sep=' ')
	print(' '.join(ans[1:]))


t = int(input())
for i in range(t):
	s = input()
	d = {}
	for i in range(len(s)):
		d.setdefault(s[i], [])
		d[s[i]].append(i)
	r = []
	if s[0] < s[-1]:
		for c in sorted(d.keys()):
			if s[0] <= c <= s[-1]:
				r.extend(d[c])
	else:
		for c in sorted(d.keys(), reverse=True):
			if s[0] >= c >= s[-1]:
				r.extend(d[c])
	print(abs(ord(s[0]) - ord(s[-1])), len(r))
	print(' '.join((str(i + 1) for i in r)))


t = int(input())
for _ in range(t):
	alphs = {chr(x): [] for x in range(ord('a'), ord('z') + 1)}
	s = input()
	for (i, c) in enumerate(s):
		alphs[c].append(i + 1)
	(src, dst) = (s[0], s[-1])
	rng = 1
	if src > dst:
		rng = -1
	res = []
	for x in range(ord(src), ord(dst) + rng, rng):
		res += alphs[chr(x)]
	print(abs(ord(src) - ord(dst)), len(res))
	print(' '.join([str(r) for r in res]))


import math, re

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

def fastint():
	return int(input())

def solve():
	s = input()
	b = []
	plitki = []
	for i in range(26):
		b.append(0)
		plitki.append([])
	chp = 0
	p = []
	for i in range(len(s)):
		b[ord(s[i]) - 97] += 1
		plitki[ord(s[i]) - 97].append(i + 1)
	if ord(s[0]) - 97 > ord(s[-1]) - 97:
		for i in range(ord(s[0]) - 97, ord(s[-1]) - 98, -1):
			chp += b[i]
			p += plitki[i]
	elif ord(s[0]) - 97 < ord(s[-1]) - 97:
		for i in range(ord(s[0]) - 97, ord(s[-1]) - 96):
			chp += b[i]
			p += plitki[i]
	else:
		chp = b[ord(s[i]) - 97]
		p = plitki[ord(s[0]) - 97]
	print(abs(ord(s[0]) - 97 - (ord(s[-1]) - 97)), chp)
	print(' '.join(list(map(str, p))))
t = int(input())
for _ in range(t):
	solve()


def solve(s):
	lst = []
	for (i, c) in enumerate(s):
		lst.append((ord(c) - ord('a') + 1, i + 1))
	lb = min(lst[0][0], lst[-1][0])
	ub = max(lst[0][0], lst[-1][0])
	lst2 = lst[1:-1]
	lst2.sort(key=lambda x: x[0], reverse=lst[0][0] > lst[-1][0])
	lst3 = [1] + [i for (c, i) in lst2 if lb <= c <= ub] + [len(s)]
	print(ub - lb, len(lst3))
	print(' '.join([str(i) for i in lst3]))
n_case = int(input())
while n_case:
	n_case -= 1
	solve(input())


d = {}
h = 0
m = 'abcdefghijklmnopqrstuvwxyz'
for j in m:
	h += 1
	d[j] = h
t = int(input())
for j in range(0, t):
	p = input()
	mi = min(d[p[0]], d[p[-1]])
	ma = max(d[p[0]], d[p[-1]])
	op = m[mi - 1:ma]
	o = 0
	s = {}
	for i in op:
		o += 1
		s[i] = []
	for i in range(0, len(p)):
		if d[p[i]] >= mi and d[p[i]] <= ma:
			s[p[i]].append(str(i + 1))
	eu = ''
	if d[p[0]] >= d[p[-1]]:
		eu = op[::-1]
	else:
		eu = op[:]
	z = []
	for i in eu:
		if i in s and len(s[i]) > 0:
			z += s[i]
	print(ma - mi, len(z))
	print(' '.join(z))


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	indices = [[] for _ in range(26)]
	ans = list()
	m = 0
	for i in range(n):
		indices[ord(s[i]) - 97].append(i + 1)
	cost = abs(ord(s[0]) - ord(s[n - 1]))
	if s[n - 1] > s[0]:
		start = ord(s[0]) - 97
		for i in range(start, ord(s[n - 1]) - 97 + 1):
			length = len(indices[i])
			m = m + length
			for j in range(0, length):
				ans.append(indices[i][j])
	else:
		start = ord(s[0]) - 97
		for i in range(start, ord(s[n - 1]) - 97 - 1, -1):
			length = len(indices[i])
			m = m + length
			for j in range(0, length):
				ans.append(indices[i][j])
	print(f'{cost} {m}')
	print(' '.join(list(map(str, ans))))
	t -= 1


for _ in range(int(input())):
	string = input().strip()
	s = string[0]
	s_l = ord(s)
	e = string[-1]
	e_l = ord(e)
	min_cost = ord(e) - ord(s)
	path = []
	if min_cost == 0:
		for (i, char) in enumerate(string, 1):
			if char == s:
				path.append(i)
	elif min_cost > 0:
		temp_path = []
		for (i, char) in enumerate(string, 1):
			if i == 1 or i == len(string):
				continue
			if s_l <= ord(char) <= e_l:
				temp_path.append((char, i))
		temp_path.sort(key=lambda t: ord(t[0]) - s_l)
		path = [1] + [i[1] for i in temp_path] + [len(string)]
	else:
		temp_path = []
		for (i, char) in enumerate(string, 1):
			if i == 1 or i == len(string):
				continue
			if e_l <= ord(char) <= s_l:
				temp_path.append((char, i))
		temp_path.sort(key=lambda t: ord(t[0]) - s_l, reverse=True)
		path = [1] + [i[1] for i in temp_path] + [len(string)]
	print(f'{abs(min_cost)} {len(path)}')
	print(' '.join([str(i) for i in path]))


t = int(input())
for _ in range(t):
	s = input()
	d = {}
	for i in range(len(s)):
		if s[i] in d:
			d[s[i]].append(i)
		else:
			d[s[i]] = [i]
	out = []
	(st, ed) = (ord(min(s[0], s[-1])), ord(max(s[0], s[-1])))
	print(ed - st, end=' ')
	l = [chr(i) for i in range(st, ed + 1)]
	if s[0] > s[-1]:
		l = l[::-1]
	for ch in l:
		if ch not in d:
			continue
		for ind in d[ch]:
			out.append(str(ind + 1))
	print(len(out))
	print(' '.join(out))


t = int(input())
for t1 in range(t):
	s = input()
	pos = dict()
	for i in range(len(s)):
		x = s[i]
		if x in pos:
			pos[x].append(str(i + 1))
		else:
			pos[x] = [str(i + 1)]
	start = ord(s[0])
	end = ord(s[-1])
	if start == end:
		step = 1
	else:
		step = (end - start) // abs(end - start)
	ans = []
	cost = 0
	prev = start
	for i in range(start, end + step, step):
		if chr(i) in pos:
			cost += abs(i - prev)
			prev = i
			ans += pos[chr(i)]
	print(cost, len(ans))
	print(' '.join(ans))


from collections import defaultdict
for _ in range(int(input())):
	s = input()
	n = len(s)
	pos = defaultdict(list)
	for i in range(n):
		pos[s[i]].append(i)
	(of, ol) = (ord(s[0]), ord(s[-1]))
	res = []
	if of <= ol:
		for c in range(of, ol + 1):
			cc = chr(c)
			for x in pos[cc]:
				res.append(x + 1)
	else:
		for c in reversed(range(ol, of + 1)):
			cc = chr(c)
			for x in pos[cc]:
				res.append(x + 1)
	print(abs(of - ol), len(res))
	print(' '.join(map(str, res)))


import sys
input = sys.stdin.readline
for i in range(int(input())):
	s = input()[:-1]
	l = [[] for i in range(26)]
	for i in range(len(s)):
		l[ord(s[i]) - 97].append(i + 1)
	st = [1, -1][s[0] > s[-1]]
	ans = []
	for i in range(ord(s[0]) - 97, ord(s[-1]) - 97 + st, st):
		ans.extend(l[i])
	print(abs(ord(s[-1]) - ord(s[0])), len(ans))
	print(*ans)


t = int(input())

def solve(first, last, d, s):
	sol = [first]
	col = s[first]
	while col <= s[last]:
		for x in d[col]:
			if x not in [first, last]:
				sol.append(x)
		col += 1
	sol.append(last)
	return sol
for _ in range(t):
	s = [ord(x) - 97 for x in input()]
	first = 0
	last = len(s) - 1
	d = {i: [] for i in range(26)}
	for (i, si) in enumerate(s):
		d[si].append(i)
	if s[first] < s[last]:
		sol = solve(first, last, d, s)
	elif s[last] < s[first]:
		sol = solve(last, first, d, s)[::-1]
	else:
		sol = sorted(d[s[first]])
	if len(s) == 1:
		print(0, 1)
		print(s[0])
	else:
		print(abs(s[0] - s[-1]), len(sol))
		print(' '.join([str(x + 1) for x in sol]))


import sys
input = sys.stdin.readline

def fun(s):
	return ord(s) - ord('a') + 1
for _ in range(int(input())):
	s = input().strip()
	n = len(s)
	d = {}
	for i in range(n):
		if s[i] in d:
			d[s[i]].append(i + 1)
		else:
			d[s[i]] = [i + 1]
	if s[0] == s[n - 1]:
		print(0, len(d[s[0]]))
		print(*d[s[0]])
	elif s[0] < s[n - 1]:
		a = sorted(d.keys())
		f = []
		c = 0
		m = 0
		for i in range(a.index(s[0]), a.index(s[n - 1])):
			c += fun(a[i + 1]) - fun(a[i])
			m += len(d[a[i]])
			f += d[a[i]]
		m += len(d[a[a.index(s[n - 1])]])
		f += d[a[a.index(s[n - 1])]]
		print(c, m)
		print(*f)
	else:
		a = sorted(d.keys(), reverse=True)
		f = []
		c = 0
		m = 0
		for i in range(a.index(s[0]), a.index(s[n - 1])):
			c += abs(fun(a[i + 1]) - fun(a[i]))
			m += len(d[a[i]])
			f += d[a[i]]
		m += len(d[a[a.index(s[n - 1])]])
		f += d[a[a.index(s[n - 1])]]
		print(c, m)
		print(*f)


n = int(input())
alpha = '_abcdefghijklmnopqrstuvwxyz'
for i in range(n):
	line = str(input())
	hm = {}
	for a in alpha[1:]:
		hm[a] = []
	for j in range(len(line)):
		a = line[j]
		hm[a].append(j)
	start = line[0]
	end = line[-1]
	si = alpha.index(start)
	ei = alpha.index(end)
	cost = max(si, ei) - min(si, ei)
	jumps = 0
	indices = ''
	if si < ei:
		for j in range(si, ei + 1):
			a = alpha[j]
			jumps += len(hm[a])
			for ind in hm[a]:
				indices += str(ind + 1) + ' '
	else:
		for j in range(si, ei - 1, -1):
			a = alpha[j]
			jumps += len(hm[a])
			for ind in hm[a]:
				indices += str(ind + 1) + ' '
	print(cost, jumps)
	print(indices[:-1])


for tc in range(int(input())):
	string = input()
	n = len(string)
	latin_lc = 'abcdefghijklmnopqrstuvwxyz'
	string_info = []
	first = (string[0], 1, ord(string[0]) - 96)
	last = (string[n - 1], n, ord(string[n - 1]) - 96)
	if first[2] < last[2]:
		seq = 'a'
		(lower, higher) = (first[2], last[2])
	else:
		seq = 'd'
		(lower, higher) = (last[2], first[2])
	for i in range(1, n - 1):
		ordinal = ord(string[i]) - 96
		if ordinal >= lower and ordinal <= higher:
			string_info.append((string[i], i + 1, ordinal))
	if seq == 'a':
		string_info.sort(key=lambda x: x[2])
	elif seq == 'd':
		string_info.sort(key=lambda x: x[2], reverse=True)
	print(abs(first[2] - last[2]), 1 + len(string_info) + 1)
	index = [str(first[1])]
	for e in string_info:
		index.append(str(e[1]))
	index.append(str(last[1]))
	print(' '.join(index))


t = int(input())
import string
lst = list(string.ascii_lowercase)
h = {lst[i]: i for i in range(len(lst))}
l = list(h.keys())

def helper(s):
	ans = []
	small = min(h[s[0]], h[s[-1]])
	big = max(h[s[0]], h[s[-1]])
	for i in range(1, len(s) - 1):
		c = h[s[i]]
		if small <= h[s[i]] <= big:
			ans.append((str(i + 1), h[s[i]]))
	final = '1'
	if h[s[0]] > h[s[-1]]:
		ans = sorted(ans, key=lambda x: x[1], reverse=True)
	else:
		ans = sorted(ans, key=lambda x: x[1])
	ans = [ans[i][0] for i in range(len(ans))]
	arr = [0] * 3
	arr[0] = str(big - small)
	arr[1] = str(2 + len(ans))
	ans = ['1'] + ans + [str(len(s))]
	arr[2] = ans
	return arr
for i in range(t):
	s = input()
	res = helper(s)
	print(int(res[0]), int(res[1]))
	print(' '.join(res[2]))


readMl = lambda _f, _n: (_f(input()) for _ in range(_n))

def readLn() -> map:
	return map(int, input().split())

def alp(s: str) -> int:
	return ord(s) - ord('a')

def Solve() -> None:
	s = input()
	n = len(s)
	m = [[] for _ in range(26)]
	for i in range(n):
		m[alp(s[i])].append(i + 1)
	(ansmn, ansmx) = (abs(alp(s[-1]) - alp(s[0])), 0)
	ansord = []
	if s[-1] > s[0]:
		for i in range(alp(s[0]), alp(s[-1]) + 1):
			ansmx += len(m[i])
			ansord.extend(m[i])
	elif s[-1] < s[0]:
		for i in range(alp(s[0]), alp(s[-1]) - 1, -1):
			ansmx += len(m[i])
			ansord.extend(m[i])
	else:
		ansmx = len(m[alp(s[0])])
		ansord = m[alp(s[0])]
	print(ansmn, ansmx)
	print(*ansord)

def Main() -> None:
	for _ in range(int(input())):
		Solve()
Main()


from collections import defaultdict
for _ in range(int(input())):
	s = input()
	dt = defaultdict(list)
	for (idx, ch) in enumerate(s):
		dt[ch].append(idx + 1)
	begin = ord(s[0])
	end = ord(s[-1])
	ans = []
	if begin < end:
		for i in range(begin, end + 1):
			ans.extend(dt[chr(i)])
	else:
		for i in range(begin, end - 1, -1):
			ans.extend(dt[chr(i)])
	print(abs(begin - end), len(ans))
	print(*ans)


t = int(input())
for i in range(t):
	ans = ''
	occur = [[] for j in range(26)]
	s = input()
	cost = ord(s[-1]) - ord(s[0])
	if cost >= 0:
		low = ord(s[0]) - ord('a')
		high = ord(s[-1]) - ord('a')
		rev = False
	else:
		low = ord(s[-1]) - ord('a')
		high = ord(s[0]) - ord('a')
		cost = -cost
		rev = True
	for (pos, char) in enumerate(s):
		occur[ord(char) - ord('a')].append(pos)
	occured = list(filter(None, occur[low:high + 1]))
	if rev:
		occured = reversed(occured)
	m = 0
	for locs in occured:
		for loc in locs:
			ans += str(loc + 1) + ' '
			m += 1
	print(cost, m)
	print(ans.strip())


for i in range(int(input())):
	s = input()
	als = [(s[i], i + 1) for i in range(1, len(s) - 1) if s[-(s[0] > s[-1])] <= s[i] <= s[-(s[0] <= s[-1])]]
	als.sort(reverse=s[0] > s[-1])
	print(f'{abs(ord(s[0]) - ord(s[-1]))} {len(als) + 2}\n' + '1 ' + ' '.join((str(als[i][1]) for i in range(len(als)))) + f' {len(s)}')


def cal(s):
	dic = {}
	for (i, p) in enumerate(s):
		v = ord(p)
		if v in dic:
			dic[v].append(i + 1)
		else:
			dic[v] = [i + 1]
	(a, b) = (ord(s[0]), ord(s[-1]))
	m = abs(a - b)
	if a <= b:
		st = a
		ed = b + 1
		tg = 1
	else:
		st = a
		ed = b - 1
		tg = -1
	ans = []
	for i in range(st, ed, tg):
		if i in dic:
			ans += dic[i]
	return [m] + [len(ans)] + ans
for jj in range(int(input())):
	s = input()
	res = cal(s)
	print(*res[:2])
	print(*res[2:])


import sys
import heapq
import math
input = sys.stdin.readline
from collections import Counter, defaultdict

def inp():
	return int(input())

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

def main():
	string = input().strip()
	charMap = defaultdict(list)
	for i in range(len(string)):
		char = string[i]
		charMap[char].append(i + 1)
	sum_ = 0
	stack = [1]
	direction = -1 if string[0] > string[-1] else 1
	prevChar = string[0]
	for i in range(ord(string[0]), ord(string[-1]) + direction, direction):
		character = chr(i)
		if character in charMap:
			while charMap[character]:
				popped = charMap[character].pop()
				if popped != 1 and popped != len(string):
					stack.append(popped)
		sum_ += abs(ord(prevChar) - ord(character))
		prevChar = character
	if len(string) != 1:
		stack.append(len(string))
	print(sum_, len(stack))
	print(*stack)
t = inp()
for _ in range(t):
	main()


a = ord('a')

def solve(string: str):
	numbers = createArr(string)
	size = len(numbers)
	first = numbers[0]
	last = numbers[size - 1]
	if first <= last:
		numbers.sort(key=lambda x: (x[0], x[1]))
	elif first > last:
		numbers.sort(key=lambda x: x[1])
		numbers.sort(reverse=True, key=lambda x: x[0])
	start = findFirst(numbers, first[0])
	i = start + 1
	res = 0
	indexes = [1]
	while i < size and (not (numbers[i - 1] == last and numbers[i] != last)):
		res += abs(numbers[i][0] - numbers[i - 1][0])
		indexes.append(numbers[i][1])
		i += 1
	print(res, i - start)
	print(' '.join([str(i) for i in indexes]))

def findFirst(numbers, first):
	for i in range(len(numbers)):
		if numbers[i][0] == first:
			return i

def createArr(string: str):
	arr = []
	for (i, v) in enumerate(string):
		arr.append((ord(v) - a + 1, i + 1))
	return arr

def toChar(digit):
	return chr(int(digit) + a - 1)
amountTests = int(input())
for _ in range(amountTests):
	string = input()
	solve(string)


import sys
input = sys.stdin.readline

def solve():
	s = input().strip()
	n = len(s)
	pos = [[] for _ in range(26)]
	(v1, v2) = (min(ord(s[0]), ord(s[-1])), max(ord(s[0]), ord(s[-1])))
	cost = v2 - v1
	for i in range(n):
		if v1 <= ord(s[i]) <= v2:
			pos[ord(s[i]) - ord('a')].append(i + 1)
	ans = []
	if ord(s[0]) <= ord(s[-1]):
		for each in pos:
			for idx in each:
				ans.append(idx)
	else:
		pos = pos[::-1]
		for each in pos:
			for idx in each:
				ans.append(idx)
	print(*[cost, len(ans)])
	print(*ans)
for _ in range(int(input())):
	solve()


testcases = int(input())
for i in range(testcases):
	input_1 = input()
	string_list = [*input_1]
	start = string_list[0]
	end = string_list[len(string_list) - 1]
	if start < end:
		letters = list(map(chr, range(ord(start), ord(end) + 1)))
		reverse = False
		dictionary = {key: [] for key in list(map(chr, range(ord(start), ord(end) + 1)))}
	else:
		letters = list(map(chr, range(ord(end), ord(start) + 1)))[::-1]
		reverse = True
		dictionary = {key: [] for key in list(map(chr, range(ord(end), ord(start) + 1)))}
	for i in range(len(string_list)):
		if string_list[i] in dictionary.keys():
			dictionary[string_list[i]].append(i + 1)
	cost = 0
	sequence = list()
	n_visited = 0
	last_letter = start
	for i in letters:
		dict_i = dictionary[i]
		for j in range(len(dict_i)):
			sequence.append(dict_i[j])
			n_visited += 1
			cost += abs(ord(last_letter) - ord(i))
			last_letter = i
	print(' '.join(map(str, [cost, n_visited])))
	print(' '.join(map(str, sequence)))


index = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}
n = int(input())
for num in range(n):
	words = ans = []
	count = [[] for i in range(27)]
	a = input()
	for i in range(len(a)):
		count[index[a[i]]].append(i + 1)
	jieshu = index[a[-1]]
	kaishi = index[a[0]]
	waste = abs(jieshu - kaishi)
	shun = []
	step = 0
	for i in range(kaishi, jieshu + 1) if kaishi < jieshu else range(kaishi, jieshu - 1, -1):
		ans.extend(count[i])
	print(waste, len(ans))
	print(*ans)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	pos = [[] for _ in range(26)]
	for i in range(n):
		pos[ord(s[i]) - ord('a')].append(i + 1)
	res = []
	k = ord(s[0]) - ord('a')
	l = ord(s[-1]) - ord('a')
	rng = None
	if k <= l:
		rng = range(k, l + 1)
	else:
		rng = range(k, l - 1, -1)
	cost = 0
	prev = k
	for i in rng:
		res.extend(pos[i])
		if len(pos[i]) > 0:
			cost += abs(i - prev)
			prev = i
	print(cost, len(res))
	print(*res)


t = int(input())
for _ in range(t):
	s = [ord(x) - 96 for x in input()]
	cost = abs(s[0] - s[-1])
	(l, r) = sorted([s[0], s[-1]])
	path = [i for (i, x) in enumerate(s) if l <= x <= r]
	del path[0]
	del path[-1]
	if s[0] < s[-1]:
		path.sort(key=lambda i: s[i])
	else:
		path.sort(key=lambda i: s[i], reverse=True)
	print(cost, len(path) + 2)
	print(1, *[i + 1 for i in path], len(s))


import sys
sys.setrecursionlimit(200000)
import math
from collections import Counter
from collections import defaultdict
from collections import deque
input = sys.stdin.readline
from functools import lru_cache
import heapq

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
testcases = inp()
for i in range(testcases):
	arr = insr()
	f = defaultdict(list)
	answer1 = [0, 0]
	answer = []
	prevKey = arr[0]
	y = 1 if arr[0] < arr[-1] else -1
	for i in range(len(arr)):
		if arr[0] <= arr[i] <= arr[-1] or arr[0] >= arr[i] >= arr[-1]:
			f[arr[i]].append(i + 1)
	for key in sorted(f.keys())[::y]:
		if arr[0] <= key <= arr[-1] or arr[0] >= key >= arr[-1]:
			answer.extend(f[key])
			answer1[0] += abs(ord(prevKey) - ord(key))
			answer1[1] += len(f[key])
			prevKey = key
	print(*answer1)
	print(*answer)


import sys

def JumpingonTiles(s):
	int_s = [ord(i) for i in s]
	start = min(int_s[0], int_s[-1])
	end = max(int_s[0], int_s[-1])
	desc = False
	if int_s[0] > int_s[-1]:
		desc = True
	steps = []
	for i in range(1, len(int_s) - 1):
		if int_s[i] <= end and int_s[i] >= start:
			steps.append([int_s[i], i])
	steps = sorted(steps, reverse=desc)
	ret = []
	ret.append('1')
	for (_, i) in steps:
		ret.append(str(i + 1))
	ret.append(str(len(int_s)))
	sys.stdout.write(str(end - start) + ' ' + str(len(steps) + 2) + '\n')
	sys.stdout.write(' '.join(ret) + '\n')

def inp():
	return int(input())
num_testcases = inp()
for i in range(num_testcases):
	s = input()
	JumpingonTiles(s)


import sys
from collections import defaultdict

def solve():
	s = input()
	g = defaultdict(list)
	for (i, c) in enumerate(s):
		g[c].append(i)
	cost = abs(ord(s[0]) - ord(s[-1]))
	ans = []
	(start, end) = (ord(s[0]), ord(s[-1]))
	if start > end:
		for i in range(start, end - 1, -1):
			for x in g[chr(i)]:
				ans.append(x + 1)
	else:
		for i in range(start, end + 1):
			for x in g[chr(i)]:
				ans.append(x + 1)
	print(cost, len(ans))
	print(*ans)
for _ in range(int(input())):
	solve()


tc = int(input())
for _ in range(tc):
	test = input()
	fch = test[0]
	lch = test[-1]
	upper = max(ord(fch), ord(lch))
	lower = min(ord(fch), ord(lch))
	res = {}
	for i in range(1, len(test)):
		if lower <= ord(test[i]) <= upper:
			res[i + 1] = ord(test[i])
	if ord(fch) <= ord(lch):
		sorted_dict = dict(sorted(res.items(), key=lambda item: item[1]))
	else:
		sorted_dict = dict(sorted(res.items(), key=lambda item: item[1], reverse=True))
	print(f'{abs(ord(fch) - ord(lch))} {len(sorted_dict) + 1}')
	res = ''
	res += '1'
	for (key, value) in sorted_dict.items():
		res += f' {key}'
	print(res)


from string import ascii_lowercase
t = int(input())
score = {x: i + 1 for (i, x) in enumerate(ascii_lowercase)}
for _ in range(t):
	s = input()
	if s[0] > s[-1]:
		ss = sorted([(x, i) for (i, x) in enumerate(s)], key=lambda k: (k[0], -k[1]), reverse=True)
	else:
		ss = sorted([(x, i) for (i, x) in enumerate(s)])
	start = None
	end = None
	for (i, x) in enumerate(ss):
		if x[1] == 0 and start is None:
			start = i
		if x[0] == s[-1]:
			end = i
	max_score = abs(score[ss[end][0]] - score[ss[start][0]])
	max_jumps = end - start + 1
	path = [ss[x][1] + 1 for x in range(start, end + 1)]
	print(max_score, max_jumps)
	print(' '.join(map(str, path)))


from collections import defaultdict
for _ in range(int(input())):
	s = input()
	n = len(s)
	chars = defaultdict(list)
	for (i, c) in enumerate(s, 1):
		chars[c].append(i)
	answer = []
	start = ord(s[0])
	end = ord(s[-1])
	rng = range(start, end + 1) if start <= end else range(start, end - 1, -1)
	for i in rng:
		answer.extend(chars[chr(i)])
	answer.remove(1)
	answer.remove(n)
	answer = [1] + answer + [n]
	print(abs(end - start), len(answer))
	print(*answer)


from collections import Counter, defaultdict
for _ in ' ' * int(input()):
	p = input()
	n = list(enumerate(p))
	if p[0] > p[-1]:
		n.sort(key=lambda j: j[1], reverse=True)
	else:
		n.sort(key=lambda j: j[1])
	x = []
	f = 0
	for (i, a) in n:
		if i == 0:
			f = 1 ^ f
		if f:
			x.append(i + 1)
		if i == len(p) - 1:
			break
	print(abs(ord(p[0]) - ord(p[-1])), len(x), '\n', *x)


t = int(input())
for _ in range(t):
	s = input()
	f = ord(s[0])
	l = ord(s[-1])
	cost = abs(f - l)
	d = {}
	for i in range(len(s)):
		if d.get(ord(s[i]), -1) == -1:
			d[ord(s[i])] = [i + 1]
		else:
			d[ord(s[i])].append(i + 1)
	m = 0
	lst = []
	if f < l:
		for key in sorted(d.keys()):
			if f <= key <= l:
				lst += d[key]
				m += len(d[key])
	else:
		for key in sorted(d.keys(), reverse=True):
			if l <= key <= f:
				lst += d[key]
				m += len(d[key])
	print(cost, m)
	print(*lst)


for _ in range(int(input())):
	s = input()
	n = len(s)
	ns = sorted(list(range(n)), key=lambda x: s[x], reverse=True if s[0] > s[n - 1] else False)
	active = False
	ans = []
	for i in range(n):
		if ns[i] == 0:
			active = True
		if active:
			ans.append(ns[i] + 1)
		if ns[i] == n - 1:
			break
	print(abs(ord(s[n - 1]) - ord(s[0])), len(ans))
	print(*ans)


n = int(input())
result = []
for i in range(0, n):
	line_index = [ord(c) for c in input()]
	cost_final = abs(line_index[-1] - line_index[0])
	min_el = min(line_index[-1], line_index[0])
	max_el = max(line_index[-1], line_index[0])
	list_with_ind = list(zip(range(1, len(line_index) + 1), line_index))
	line_index_fav = [(ind, el) for (ind, el) in list_with_ind if el >= min_el and el <= max_el]
	line_index_fav.sort(key=lambda x: x[1]) if min_el == line_index[0] else line_index_fav.sort(key=lambda x: x[1], reverse=True)
	m_final = len(line_index_fav)
	result.append([cost_final, m_final])
	result.append([el for (el, _) in line_index_fav])
for r in result:
	print(*r)


import sys
T = int(input())
for _ in range(T):
	arr = []
	s = input()
	for (i, l) in enumerate(s):
		arr.append((ord(l) - ord('a') + 1, i + 1))
	start = arr[0][0]
	end = arr[-1][0]
	res = []
	ans = 0
	reverse = False
	if start > end:
		reverse = True
		(start, end) = (end, start)
	for (n, i) in sorted(arr, key=lambda x: (x[0], -x[1] if reverse else x[1])):
		if n >= start and n <= end:
			res.append(str(i))
	print(end - start, len(res))
	print(' '.join(res[::-1]) if reverse else ' '.join(res))


import string

def main():
	s = input()
	retard_dict = {i: [] for i in range(1, 27)}
	items = []
	for (index, elem) in enumerate(s):
		retard = string.ascii_lowercase.index(elem) + 1
		items.append(retard)
		retard_dict[retard].append(index + 1)
	result = []
	cost = 0
	m = 0
	if items[0] < items[-1]:
		last = items[0]
		for i in range(items[0], items[-1] + 1):
			if i in items:
				item = i
				cost += item - last
				last = item
				retard_now = retard_dict[item]
				m += len(retard_now)
				result += retard_now
	else:
		last = items[0]
		for i in range(items[0], items[-1] - 1, -1):
			if i in items:
				item = i
				cost += last - item
				last = item
				retard_now = retard_dict[item]
				m += len(retard_now)
				result += retard_now
	print(cost, m)
	return result
for asd in range(int(input())):
	print(*main())


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = list(input().strip())
	n = len(s)
	begin = s.pop(0)
	end = s.pop(-1)
	if begin < end:
		newS = [(j, i) for (i, j) in enumerate(s) if j >= begin and j <= end]
		newS.sort(reverse=False)
	elif end < begin:
		newS = [(j, i) for (i, j) in enumerate(s) if j >= end and j <= begin]
		newS.sort(reverse=True)
	else:
		newS = [(j, i) for (i, j) in enumerate(s) if j == begin]
	print(abs(ord(end) - ord(begin)), len(newS) + 2, sep=' ')
	sol = []
	sol.append(1)
	for (j, i) in newS:
		sol.append(i + 2)
	sol.append(n)
	print(*sol)


def solve():
	a = input()
	s = []
	(mi, ma) = (min(a[0], a[-1]), max(a[0], a[-1]))
	for i in range(1, len(a) - 1):
		if mi <= a[i] <= ma:
			s.append((a[i], i + 1))
	s.sort()
	if a[0] > a[-1]:
		s.reverse()
	print(abs(ord(a[0]) - ord(a[-1])), len(s) + 2)
	print(1, end=' ')
	for j in s:
		print(j[1], end=' ')
	print(len(a))
for _ in range(int(input())):
	solve()


from collections import defaultdict
for _ in range(int(input())):
	s = input()
	n = len(s)
	start = ord(s[0])
	end = ord(s[n - 1])
	cost = abs(start - end)
	m = 0
	indexes = defaultdict(list)
	for (i, char) in enumerate(s):
		if i == 0:
			continue
		val = ord(char)
		if val in indexes:
			indexes[val].append(i + 1)
		else:
			indexes[val] = [i + 1]
	ans = [1]
	inc = 1 if end >= start else -1
	for val in range(start, end + inc, inc):
		if val in indexes:
			ans.extend(indexes[val])
	print(cost, len(ans))
	print(*ans)


def get_index(a):
	return ord(a) - 96

def min_max(s):
	first = s[0]
	last = s[-1]
	index_of_first = get_index(first)
	index_of_last = get_index(last)
	cost = abs(index_of_first - index_of_last)
	print(cost, end=' ')
	path = []
	if index_of_first < index_of_last:
		for i in range(len(s)):
			index_of_i = get_index(s[i])
			if index_of_first <= index_of_i <= index_of_last:
				path.append((i + 1, index_of_i))
		path.sort(key=lambda x: x[1])
	else:
		for i in range(len(s)):
			index_of_i = get_index(s[i])
			if index_of_first >= index_of_i >= index_of_last:
				path.append((i + 1, index_of_i))
		path.sort(key=lambda x: x[1], reverse=True)
	print(len(path))
	print(*list((i[0] for i in path)))
t = int(input())
while t:
	t -= 1
	s = input()
	min_max(s)


try:
	for _ in range(int(input())):
		n = input()
		z = abs(ord(n[0]) - ord(n[len(n) - 1]))
		x = ord(n[0])
		y = ord(n[len(n) - 1])
		a = min(x, y)
		b = max(x, y)
		l = [[] for i in range(26)]
		for i in range(len(n)):
			l[ord(n[i]) - 97].append(i + 1)
		ans = []
		st = [1, -1][n[0] > n[-1]]
		for i in range(ord(n[0]) - 97, ord(n[-1]) - 97 + st, st):
			ans.extend(l[i])
		print(z, end=' ')
		l.sort()
		print(len(ans))
		print(*ans)
except:
	pass


abc = 'abcdefghijklmnopqrstuvwxyz'
for t in range(int(input())):
	s = input()
	s0 = min(s[0], s[-1])
	sn = max(s[0], s[-1])
	n = len(s)
	d = {}
	for i in range(n):
		if s0 <= s[i] <= sn:
			if s[i] not in d:
				d[s[i]] = [i + 1]
			else:
				d[s[i]].append(i + 1)
	s = sorted(set(s)) if s[0] <= s[-1] else sorted(set(s), reverse=True)
	t = []
	for x in s:
		if x in d:
			t.extend(d[x])
	print(ord(sn) - ord(s0), len(t))
	print(*t)


from collections import defaultdict
for _ in range(int(input())):
	tile = input()
	index = defaultdict(list)
	for i in range(len(tile)):
		index[tile[i]].append(i + 1)
	direction = 1 if tile[0] < tile[-1] else -1
	c = ord(tile[0])
	ans = []
	while c != ord(tile[-1]) + direction:
		for v in index[chr(c)]:
			ans.append(v)
		c += direction
	print(abs(ord(tile[-1]) - 96 - (ord(tile[0]) - 96)), len(ans))
	print(*ans)


from collections import defaultdict
for i in range(int(input())):
	s = input()
	d = defaultdict(list)
	for j in range(len(s)):
		d[s[j]].append(j + 1)
	dif = ord(s[0]) - ord(s[-1])
	l = list(d.keys())
	ans = []
	if dif < 0:
		l.sort()
		for j in l:
			if j > s[-1]:
				break
			if j < s[0]:
				continue
			ans.extend(d[j])
	else:
		l.sort(reverse=True)
		for j in l:
			if j < s[-1]:
				break
			if j > s[0]:
				continue
			ans.extend(d[j])
	print(abs(dif), len(ans))
	for j in ans:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	s = input()
	pos = [[] for i in range(26)]
	for i in range(len(s)):
		pos[ord(s[i]) - ord('a')].append(i + 1)
	l = ord(s[0]) - ord('a')
	r = ord(s[-1]) - ord('a')
	ok = l <= r
	ans = []
	while True:
		for x in pos[l]:
			ans.append(x)
		if l == r:
			break
		l += 1 if ok else -1
	print(abs(ord(s[0]) - ord(s[-1])), len(ans))
	print(*ans)


def solve():
	s = input()
	start = min(s[0], s[-1])
	end = max(s[0], s[-1])
	cost = ord(end) - ord(start)
	d_pos = {}
	tot_arr = []
	m = 0
	for idx in range(len(s)):
		if s[idx] < start or s[idx] > end:
			continue
		m += 1
		tot_arr.append(s[idx])
		if s[idx] in d_pos:
			d_pos[s[idx]].append(idx + 1)
		else:
			d_pos[s[idx]] = [idx + 1]
	ff = list(set(tot_arr))
	if s[0] > s[-1]:
		ff.sort(reverse=True)
	else:
		ff.sort()
	print(cost, m)
	path = []
	for f in ff:
		path += d_pos[f]
	print(*path)
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	M = list(input())
	L = [(M[i], i + 1) for i in range(len(M))]
	n = len(L)
	a = L[0][0]
	b = L[n - 1][0]
	ans = abs(ord(a) - ord(b))
	if a > b:
		L.sort(reverse=True)
	else:
		L.sort()
	startin = 0
	for i in range(n):
		if L[i][0] == a:
			startin = i
			break
	lastin = 0
	for i in range(n - 1, -1, -1):
		if L[i][0] == b:
			lastin = i
			break
	A = []
	for i in range(startin, lastin + 1):
		A.append(L[i][1])
	m = len(A)
	if A[m - 1] != n:
		c = A.index(n)
		d = A[m - 1]
		A[m - 1] = n
		A[c] = d
	if A[0] != 1:
		c = A.index(1)
		(A[c], A[0]) = (A[0], A[c])
	print(ans, m)
	print(*A)


for _ in range(int(input())):
	a = list(input())
	if a[0] > a[-1]:
		z = [(ord(a[0]) - ord(a[i]), i + 1) for i in range(len(a)) if a[i] <= a[0] and a[i] >= a[-1]]
	else:
		z = [(ord(a[i]) - ord(a[0]), i + 1) for i in range(len(a)) if a[i] >= a[0] and a[i] <= a[-1]]
	z.sort()
	m = z[-1][0]
	t = len(z)
	r = [j for (i, j) in z]
	print(m, t)
	print(*r)


for _ in range(int(input())):
	w = input()
	first_let = ord(w[0])
	last_let = ord(w[-1])
	rev = False
	if first_let > last_let:
		rev = True
		(first_let, last_let) = (last_let, first_let)
	out = ['1']
	out_let = []
	for x in range(1, len(w) - 1):
		if first_let <= ord(w[x]) <= last_let:
			out_let.append([w[x], x])
	if rev:
		out_let = sorted(out_let, key=lambda x: (x[0], x[1]), reverse=True)
	else:
		out_let = sorted(out_let, key=lambda x: (x[0], x[1]))
	for x in out_let:
		out.append(str(x[1] + 1))
	out.append(str(len(w)))
	print(abs(first_let - last_let), len(out))
	print(' '.join(out))


t = int(input())
for i in range(t):
	s = input()
	a = ord(s[0])
	b = ord(s[-1])
	if a > b:
		(a, b) = (b, a)
	ans = []
	for i in range(1, len(s) - 1):
		if a <= ord(s[i]) <= b:
			ans.append((s[i], i + 1))
	print(b - a, len(ans) + 2)
	print(1, end=' ')
	for (_, i) in sorted(ans, key=lambda x: x[0], reverse=s[0] > s[-1]):
		print(i, end=' ')
	print(len(s))


import math
from sys import stdin
input = stdin.readline
t = int(input())
alpha = 'abcdefghijklmnopqrstuvwxyz'
out = []
for _ in range(t):
	s = input().strip()
	p1 = s[0]
	p2 = s[-1]
	new = []
	cost = 0
	cost = alpha.index(s[0]) - alpha.index(s[-1])
	for i in range(len(s)):
		new.append(i + 1)
	if cost <= 0:
		new.sort(key=lambda x: s[x - 1])
	else:
		new.reverse()
		new.sort(key=lambda x: s[x - 1])
	end = len(s)
	seq = []
	start = False
	for i in range(len(new)):
		if (new[i] == 1 or new[i] == end) and start == False:
			start = True
		elif (new[i] == 1 or new[i] == end) and start == True:
			break
		elif start == True:
			seq.append(new[i])
	if cost > 0:
		seq.reverse()
	cost = abs(cost)
	seq.insert(0, 1)
	seq.append(end)
	print(cost, len(seq))
	print(*seq)


for _ in range(int(input())):
	s = input()
	n = len(s)
	d = {chr(o): [] for o in range(ord('a'), ord('z') + 1)}
	for i in range(1, n - 1):
		d[s[i]].append(i + 1)
	if ord(s[0]) < ord(s[-1]):
		sol = [1]
		for o in range(ord(s[0]), ord(s[-1]) + 1):
			sol += d[chr(o)]
		sol.append(n)
	elif ord(s[0]) > ord(s[-1]):
		sol = [1]
		for o in range(ord(s[0]), ord(s[-1]) - 1, -1):
			sol += d[chr(o)]
		sol.append(n)
	else:
		sol = [1] + d[s[0]] + [n]
	print(abs(ord(s[0]) - ord(s[-1])), len(sol))
	print(*sol)


import bisect

def resolve(lines_1):
	start_digit = ord(lines_1[0])
	end_digit = ord(lines_1[-1])
	hash_dict = {}
	for index in range(len(lines_1)):
		digit = ord(lines_1[index])
		if digit in hash_dict.keys():
			hash_dict[digit].append(index + 1)
		else:
			hash_dict[digit] = [index + 1]
	if start_digit == end_digit:
		cost = 0
		digit_length = len(hash_dict[start_digit])
		return (cost, digit_length, hash_dict[start_digit])
	elif start_digit < end_digit:
		cost = end_digit - start_digit
		res = []
		for index in range(start_digit, end_digit + 1):
			if index in hash_dict.keys():
				res.extend(hash_dict[index])
		return (cost, len(res), res)
	else:
		cost = start_digit - end_digit
		res = []
		for index in range(start_digit, end_digit - 1, -1):
			if index in hash_dict.keys():
				res.extend(hash_dict[index])
		return (cost, len(res), res)

def read_input():
	lines_1 = input()
	return lines_1
case_num = int(input())
if not case_num == 0:
	for index in range(case_num):
		lines_1 = read_input()
		(cost, m, res_list) = resolve(lines_1)
		print(cost, m)
		for item in res_list:
			print(str(item) + ' ', end='')
		print()


from collections import defaultdict
test = int(input())
while test:
	s = input()
	ct = defaultdict(list)
	for i in range(len(s)):
		ct[s[i]].append(i + 1)
	start = ord(s[0])
	stop = ord(s[-1])
	ans = [1]
	jumps = 1
	for i in ct[s[0]]:
		if i != 1 and i != len(s):
			jumps += 1
			ans.append(i)
	dir = 1
	if start > stop:
		dir = -1
		start -= 1
	else:
		start += 1
	for i in range(start, stop, dir):
		for j in ct[chr(i)]:
			ans.append(j)
			jumps += 1
	if s[0] != s[-1]:
		for i in ct[chr(stop)]:
			if i == len(s):
				continue
			ans.append(i)
			jumps += 1
	ans.append(len(s))
	print(abs(ord(s[0]) - ord(s[-1])), jumps + 1)
	print(*ans)
	test -= 1


for abc in range(int(input())):
	string = input()
	mas = [ord(string[x]) - ord('a') for x in range(len(string))]
	index_find = []
	for x in range(26):
		index_find.append([])
	for x in range(len(mas)):
		index_find[mas[x]].append(x)
	answer = [0, []]
	flag = mas[-1] > mas[0]
	number_index = mas[0]
	flag1 = True
	while flag1:
		if flag:
			for x in range(mas[-1] - number_index + 1):
				if index_find[number_index + x]:
					answer[1] += index_find[number_index + x]
					index_find[number_index + x] = []
					number_index = number_index + x
					answer[0] += x
					if number_index >= mas[-1]:
						flag1 = False
					break
		else:
			for x in range(number_index - mas[-1] + 1):
				if index_find[number_index - x]:
					answer[1] += index_find[number_index - x]
					index_find[number_index - x] = []
					number_index = number_index - x
					answer[0] += x
					if number_index <= mas[-1]:
						flag1 = False
					break
	print(answer[0], len(answer[1]))
	answer[1] = [x + 1 for x in answer[1]]
	print(*answer[1])


def man():
	s = input()
	x = ord(s[0])
	y = ord(s[-1])
	cost = abs(x - y)
	l = [[] for i in range(cost + 1)]
	num = 0
	st = -1
	if x < y:
		st = 1
	for i in range(0, len(s)):
		if x * st <= ord(s[i]) * st <= y * st:
			num += 1
			l[st * (ord(s[i]) - x)].append(i + 1)
	print(cost, num)
	print(*l[0], end='')
	for i in l[1:]:
		if len(i) > 0:
			print('', *i, end='')
	print()
n = int(input())
for i in range(n):
	man()


from sys import stdin
rd = stdin.readline
for _ in range(int(rd())):
	s = rd().strip()
	cost = abs(ord(s[0]) - ord(s[-1]))
	if s[0] > s[-1]:
		l = sorted(zip(s, range(len(s))), reverse=True, key=lambda x: (x[0], -x[1]))
	else:
		l = sorted(zip(s, range(len(s))))
	(x, y) = (l.index((s[-1], len(s) - 1)), l.index((s[0], 0)))
	visits = x - y + 1
	print(cost, visits)
	for i in range(y, x + 1):
		print(l[i][1] + 1, end=' ')
	print()


n_tests = int(input())
inputs = []
for test in range(n_tests):
	inputs.append(list(input()))

def indices(word, char):
	indxs = []
	for (d, char_i) in enumerate(word):
		if char_i == char:
			indxs.append(d)
	return indxs
for line in inputs:
	(start, end) = (line[0], line[-1])
	sorted_line = sorted(line)
	if start <= end:
		new_end = len(line) - sorted_line[::-1].index(end) - 1
		new_start = sorted_line.index(start)
		tiles = new_end - new_start + 1
		cost = ord(end) - ord(start)
		jump_pattern = []
		for char in sorted(set(sorted_line[new_start:new_end + 1])):
			jump_pattern += indices(line, char)
	else:
		new_start = len(line) - sorted_line[::-1].index(start) - 1
		new_end = sorted_line.index(end)
		tiles = new_start - new_end + 1
		cost = ord(start) - ord(end)
		jump_pattern = []
		for char in sorted(set(sorted_line[new_end:new_start + 1]))[::-1]:
			jump_pattern += indices(line, char)
	print(cost, tiles)
	print(' '.join([str(n + 1) for n in jump_pattern]))


testcases = int(input().strip())
for _ in range(testcases):
	string = input().strip()
	n = len(string)
	(s, e) = (string[0], string[-1])
	l = []
	for i in range(n):
		if s <= e and string[i] >= s and (string[i] <= e) or (s > e and string[i] <= s and (string[i] >= e)):
			l.append(i + 1)
	if s <= e:
		l.sort(key=lambda x: string[x - 1])
	else:
		l.sort(reverse=True, key=lambda x: string[x - 1])
	print(abs(ord(e) - ord(s)), len(l))
	[print(i, end=' ') for i in l]
	print()


from collections import defaultdict
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	(l, r) = (ord(s[0]), ord(s[-1]))
	(x, y) = (min(l, r), max(l, r))
	d = defaultdict(list)
	a = []
	for i in range(1, n - 1):
		if ord(s[i]) >= x and ord(s[i]) <= y:
			d[s[i]].append(i + 1)
	for i in sorted(d.items()):
		a.extend(i[1])
	print(abs(ord(s[-1]) - ord(s[0])), len(a) + 2)
	if l < r:
		print(*[1] + a + [n])
	else:
		print(*[1] + a[::-1] + [n])


import sys
t = int(input())
for _ in range(t):
	s = [ord(i) - 96 for i in input()]
	n = len(s)
	d = {}
	for j in range(n):
		if s[j] in d.keys():
			d[s[j]].append(j + 1)
		else:
			d[s[j]] = [j + 1]
	ans = []
	(cost, m) = (abs(s[0] - s[-1]), 0)
	if s[0] <= s[-1]:
		for i in range(s[0], s[-1] + 1):
			if i in d.keys():
				ans += d[i]
				m += len(d[i])
	else:
		for ii in range(s[-1], s[0] + 1):
			if ii in d.keys():
				ans += reversed(d[ii])
				m += len(d[ii])
		ans.reverse()
	print(cost, m)
	print(*ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	arr = [(ord(s[i]), i + 1) for i in range(1, n - 1)]
	first = ord(s[0])
	last = ord(s[-1])
	mn = abs(first - last)
	if first <= last:
		arr.sort()
	else:
		arr.sort(reverse=True)
	ans = [1]
	for (i, j) in arr:
		if i >= first and i <= last:
			ans.append(j)
		elif i <= first and i >= last:
			ans.append(j)
	ans.append(n)
	print(mn, len(ans))
	for i in ans:
		print(i, end=' ')
	print()


from collections import defaultdict as dd
for _ in range(int(input())):
	string = list(input().strip())
	n = len(string)
	left = string[0]
	right = string[-1]
	start = min(left, right)
	end = max(left, right)
	dk = dd(list)
	for x in range(n):
		dk[string[x]].append(x + 1)
	string.sort()
	rslt = []
	dk_ = dd(int)
	count = 0
	for x in string:
		if x >= start and x <= end and (not dk_[x]):
			rslt.extend(dk[x])
			count += abs(ord(start) - ord(x))
			start = x
			dk_[x] = 1
	if left < right:
		print(count, len(rslt))
		rslt.remove(n)
		rslt.remove(1)
		print(1, end=' ')
		print(*rslt, end=' ')
		print(n)
	else:
		print(count, len(rslt))
		rslt.remove(n)
		rslt.remove(1)
		print(1, end=' ')
		print(*rslt[::-1], end=' ')
		print(n)


tc = int(input())
for _ in range(tc):
	s = input()
	a = []
	n = len(s)
	for i in range(1, n - 1):
		c = s[i]
		if c >= s[0] and c <= s[-1] or (c <= s[0] and c >= s[-1]):
			a.append((c, i + 1))
	if s[-1] >= s[0]:
		a.sort()
	else:
		a.sort(reverse=True)
	print(abs(ord(s[-1]) - ord(s[0])), 2 + len(a))
	print(1, end=' ')
	if len(a) > 0:
		print(*[x[1] for x in a], end=' ')
	print(n)


def solve():
	s = input()
	(minx, maxx, td) = (0, 0, 0)
	if s[0] < s[-1]:
		(minx, maxx) = (s[0], s[-1])
		td = 1
	else:
		(minx, maxx) = (s[-1], s[0])
		td = -1
	cost = ord(maxx) - ord(minx)
	pt = []
	for i in range(1, len(s) - 1):
		if minx <= s[i] <= maxx:
			pt.append((i + 1, ord(s[i])))
	pt.sort(key=lambda w: w[1] * td)
	print(cost, len(pt) + 2)
	print(1, end=' ')
	for it in pt:
		print(it[0], end=' ')
	print(len(s))
t = int(input())
for _ in range(t):
	solve()


def p(c):
	return ord(c) - ord('a')
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	pos = [[] for i in range(26)]
	for i in range(n):
		pos[p(s[i])].append(i)
	cost = abs(p(s[n - 1]) - p(s[0]))
	m = len(pos[p(s[n - 1])])
	step = 1 if p(s[n - 1]) > p(s[0]) else -1
	for i in range(p(s[0]), p(s[n - 1]), step):
		if pos[i]:
			m += len(pos[i])
	print(cost, m)
	for i in range(p(s[0]), p(s[n - 1]), step):
		if pos[i]:
			for j in pos[i]:
				print(j + 1, end=' ')
	for j in pos[p(s[n - 1])]:
		print(j + 1, end=' ')
	print()


t = int(input())
while t > 0:
	a = []
	for i in range(26):
		a += [[]]
	t -= 1
	s = input()
	n = len(s)
	for i in range(n):
		a[ord(s[i]) - 97] += [i + 1]
	start = ord(s[0]) - 97
	end = ord(s[-1]) - 97
	ans = []
	if start <= end:
		for i in range(start, end + 1):
			ans += a[i]
	else:
		for i in range(start, end - 1, -1):
			ans += a[i]
	ans.pop(ans.index(1))
	ans.pop(ans.index(n))
	print(abs(start - end), len(ans) + 2)
	print(1, *ans, n)


t = int(input())
for g in range(t):
	s = input()
	cost = abs(ord(s[-1]) - ord(s[0]))
	a = []
	for i in range(len(s)):
		if s[i] not in a:
			a.append(s[i])
	a.sort()
	if a.index(s[0]) > a.index(s[-1]):
		a = a[::-1]
	b = []
	for i in range(len(a)):
		b.append([])
	for i in range(len(s)):
		b[a.index(s[i])].append(i + 1)
	l = min(a.index(s[0]), a.index(s[-1]))
	r = max(a.index(s[0]), a.index(s[-1]))
	ans = []
	for i in range(l, r + 1):
		ans += b[i]
	print(cost, len(ans))
	print(*ans)


def main():
	n = int(input())
	for i in range(n):
		s = input()
		step = False
		if ord(s[0]) < ord(s[-1]):
			step = False
		elif ord(s[-1]) < ord(s[0]):
			step = True
		arr = [(ord(s[i]), i) for i in range(len(s))]
		arr.sort(reverse=step, key=lambda x: x[0])
		start = arr.index((ord(s[0]), 0))
		end = arr.index((ord(s[-1]), len(s) - 1))
		arr = arr[start:end + 1]
		cost = 0
		ans = [1]
		for i in range(1, len(arr)):
			cost += abs(arr[i][0] - arr[i - 1][0])
			ans.append(arr[i][1] + 1)
		print(cost, len(ans))
		print(*ans, sep=' ')
main()