2270. Day5 C - ?? 的魔法宝藏
?? 是一位探险家。
?? 根据藏宝图找到了一处宝藏。不幸的是，一面刻有 T 行符文的巨墙挡住了他的去路。
他将藏宝图翻到背面，发现上面写有瓦解这面巨墙的方法！
每一行符文都由若干个 0 \sim 9 的数字、下划线、小写字母、大写字母构成。
对于一个字符，我们按如下方式定义它的魔力值：
- 若它是数字，它的魔力值就是它自身 +1 。
- 若它是下划线，它的魔力值就是 11。
- 若它是小写字母，它的魔力值就是它自身的 ASCII 码 -85。
- 若它是大写字母，它的魔力值就是它自身的 ASCII 码 -27。
对于一行有 n 个字符的符文，我们按如下方式定义它的魔力值：
- 从左往右数，记符文第 i 个字符的魔力值为 f_i。
- 则该符文的魔力值为 \sum_{i=1}^n f_i \cdot 127^{n-i}。
巨墙的中央嵌有一根法杖。借助它，?? 可以对墙上地字符任意次地进行下面的操作：
- 选择一个数字 0，将其变为 1。
- 选择一个数字 1，将其变为 0。
- 选择一个魔力值为 d>2 的字符，把它分裂成左右两个魔力值分别为 d-2 和 d-1 的字符（魔力值较小的字符在左边）。
- 选择左右相邻的两个字符，要求左边字符的魔力值为 d < 62，右边字符的魔力值为 d+1。将它们合并成一个魔力值为 d+2 的字符。
如果在某次操作后，墙上的 T 行符文魔力值均达到可以达到的最小状态，则整面巨墙会轰然倒塌。
现在，?? 需要你帮忙求出 T 行符文魔力值最小时的状态。
输入
第一行一个正整数 T (1 \leq T \leq 100)，表示墙上的符文行数。
之后 T 行，每行一个由数字、下划线、大小写字母构成的字符串 s_i (1 \leq |s_i| \leq 500)，表示第 i 行的符文。
输出
输出共有 T 行，第 i 行表示符文 s_i 魔力值最小时的状态。
样例
| 标准输入 复制文本 |
6 CReatiQ Kan_kiz Lacrymabre asxziill youthPaul Hojstyer |
| 标准输出 复制文本 |
aeitCS biknzK 9bfmpsyL aikmsxz ahlowyP ejoruyH |
提示
以 CReatiQ 为例：
| 字符 | C | R | e | a | t | i | Q |
|---|---|---|---|---|---|---|---|
| 对应魔力值 | 40 | 55 | 16 | 12 | 31 | 20 | 54 |
| 所乘数 | 127^6=4195872914689 | 127^5=33038369407 | 127^4=260144641 | 127^3=2048383 | 127^2=16129 | 127^1=127 | 127^0=1 |
CReatiQ 的魔力值 =40\times 127^6+55\times127^5+16\times127^4+12\times127^3+31\times 127^2+20\times 127^1+54\times 127^0=169656214302390
操作后魔力值最小的字符串 aeitCS 的魔力值=12\times127^5+16\times127^4+20\times127^3+31\times 127^2+40\times 127^1+56\times 127^0=400664219935
可以证明可达的字符串中不存在魔力值更小的字符串。
登录以提交代码。