CF1729C.Jumping on Tiles

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.

波利卡普得到了一排瓷砖。每块瓷砖上有一个小写的拉丁字母。整排瓷砖构成字符串 $s$。

换言之，你被给定一个由小写拉丁字母组成的字符串 $s$。

初始时，波利卡普位于该排瓷砖的第一块（即索引为 $1$ 的位置），他希望通过在瓷砖上跳跃的方式到达最后一块瓷砖（即索引为 $n$ 的位置）。从第 $i$ 块瓷砖跳到第 $j$ 块瓷砖的代价为 $|index(s_i) - index(s_j)|$，其中 $index(c)$ 表示字母 $c$ 在字母表中的序号（例如，$index($'a'$)=1$，$index($'b'$)=2$，……，$index($'z'$)=26$）。

波利卡普希望以最小总代价抵达第 $n$ 块瓷砖，同时在此前提下使跳跃次数尽可能多。

换句话说，在所有能以最小总代价抵达最后一块瓷砖的路径中，他将选择跳跃次数最多的那一条。

波利卡普每块瓷砖最多访问一次。

波利卡普请你帮忙——请输出他应当跳跃所经过的字符串 $s$ 中各字符的索引序列（即位置编号序列）。

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$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例由一个字符串 $s$ 给出（$2 \le |s| \le 2 \cdot 10^5$），其中 $|s|$ 表示字符串 $s$ 的长度。字符串 $s$ 仅由小写拉丁字母组成。

保证所有测试用例中字符串 $s$ 的长度总和不超过 $2 \cdot 10^5$。

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.

每个测试用例的答案包含两行。

第一行输出两个整数 $cost$ 和 $m$，其中 $cost$ 表示路径的最小总代价，$m$ 表示在总代价恰好为 $cost$ 的前提下，Polycarp 能够访问的最大方块数量（即跳跃次数为 $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|$）。

若存在多个合法答案，输出任意一个即可。

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$.

在第一个测试用例中，所要求的路径对应于下图：

在此情况下，路径的总成本达到最小可能值。由于 $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$。