Polycarp 得到了一排瓷砖。每个图块包含一个拉丁字母的小写字母。整个图块序列形成字符串 $$$s$$$。
换句话说,给你一个由小写拉丁字母组成的字符串$$$s$$$。
最初,Polycarp 位于该行的第一块图块上,并希望通过跳跃到最后一块图块。从第 $$$i$$$ 个图块跳转到第 $$$j$$$ 个图块的成本等于 $$$|index(s_i) - index(s_j)|$$$,其中 $$$index(c)$$$ 是字母表中字母 $$$c$$$ 的索引(例如,$$$index($$$'a'$$$)=1$$$, $$$index($$$'b'$$$)=2$$$, ..., $$$index($$$'z'$$$)=26$$$) 。
Polycarp 希望以最小的总成本到达第 $$$n$$$ 块,但同时进行最大的跳跃次数。
换句话说,在以最小的总成本到达最后一块砖的所有可能方法中,他会选择跳跃次数最多的方法。
Polycarp 最多可以访问每个方块一次。
Polycarp 请求你帮忙 — 打印他应该跳转的字符串 $$$s$$$ 的索引序列。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
每个测试用例由字符串 $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$) 给出,其中 $$$|s|$$$ — 是字符串 $$$s$$$ 的长度。字符串 $$$s$$$ 由小写拉丁字母组成。
保证所有测试用例的字符串长度 $$$s$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
每个测试用例的答案由两行组成。
在第一行中打印两个整数 $$$cost$$$,$$$m$$$,其中 $$$cost$$$ 是路径的最小总成本,$$$m$$$ 是 Polycarp 可以在最小总成本 $$$cost$$$ 下到达 $$$n$$$ 块的最大访问图块数(即跳转次数为$$$m-1$$$)。
在下一行中打印 $$$m$$$ 不同的数字 $$$j_1, j_2, \dots, j_m$$$ ($$$1 \le j_i \le |s|$$$) - Polycarp 将跳转的图块索引序列。序列中的第一个数字必须是 $$$1$$$(即 $$$j_1=1$$$),最后一个数字必须是 $$$|s|$$$ 的值(即 $$$j_m=|s|$$$)。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
6 logic codeforces bca aaaaaaaaaaa adbaadabad to
输出 #1
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
注意
第一个测试用例中,所需路径对应图片:
在这种情况下,实现了路径的最小可能总成本。由于$$$index($$$'l'$$$)=12$$$,$$$index($$$'o'$$$)=15$$$,$$$index($$$'g'$$$)=7$$$,$$$index($$$'i'$$$)=9$$$,$$$index($$$'c'$$$)=3$$$,则路径的总成本为$$$|12-9|+|9-7|+|7-3|=3+2+4=9$$$。