一、题目理解

我们有 $n$ 个整数，两人轮流操作：

• 安娜：选一个数，反转它的数字（去掉前导零）。
  效果：可能减少数字的长度，因为末尾的零会被去掉（例如 $1200 \to 21$）。
• 萨沙：选两个数，按任意顺序拼接成一个新数。
  效果：长度是两者长度之和，不会减少数字总长度，只会合并。

游戏结束：萨沙无法操作时，即只剩一个数。
若最终数字长度 $\ge m+1$（因为 $\ge 10^m$ 意味着至少 $m+1$ 位），则 萨沙胜；否则 安娜胜。

---

二、关键转化

设一个数 $x$ 有 $c$ 位，则 $x \ge 10^{c-1}$。
所以 $\ge 10^m \iff$ 位数 $\ge m+1$。

因此游戏目标转化为：
最终那个数的位数 $\ge m+1$ 则萨沙赢，否则安娜赢。

---

三、谁会影响位数？

• 安娜操作：
  反转可能去掉末尾的零，从而 减少位数。
  比如 $1200$（4 位）$\to 21$（2 位），减少 2 位。

• 萨沙操作：
  拼接两个数：若长度分别为 $L_1, L_2$，则新数长度 $= L_1+L_2$。
  所以 总位数不变（只是合并）。

结论：
整个游戏的 总位数之和 只在安娜操作时可能减少，萨沙不会减少总位数。

---

四、最优策略推理

• 安娜的目标：让最后总位数尽量小（< m+1）。
  她应该每次选一个 末尾零最多 的数来反转，这样减少的位数最多（因为末尾零全消失）。

• 萨沙的目标：让最后总位数尽量大。
  他应该尽量 保护 那些末尾零多的数，不让安娜有机会反转它们。
  怎么做？
  在萨沙的回合，他会选一个末尾零最多的数，把它和一个非零结尾的数拼接，这样这些零就夹在中间，安娜以后无法反转去掉它们（因为安娜只能反转整个数，但中间的零会保留）。

但是，由于游戏流程是 安娜先手，然后轮流进行，所以：

---

博弈过程抽象

1. 所有数字初始有：

   • 原始长度 $len_i$
   • 末尾零个数 $z_i$（可去掉的长度）

2. 如果安娜反转一个数字，它会减少 $z_i$ 位（去掉末尾零），长度变为 $len_i - z_i$。

3. 萨沙拼接时，不改变总位数。

因此，最终总位数 = 所有数字的初始长度总和 − 安娜成功去掉的零的总数。

---

安娜如何最大化去掉的零总数？

她每次选当前末尾零最多的数字反转。
但萨沙可以“保护”一些数字：如果萨沙先手，他会把末尾零多的数字和一个数字拼接，这样这些零就永久保留在中间，安娜不能再动它。

但因为安娜 先手，所以：

• 第一回合：安娜直接反转末尾零最多的数（去掉它的所有末尾零）。
• 萨沙回合：他选剩下末尾零最多的数，拼接到别的数上，保护它。
• 下一回合：安娜再选剩下末尾零最多的数反转。
• 萨沙再保护下一个。
• 依次类推。

---

五、数学模型

设每个数的“可损失位数” = 末尾零个数 $z_i$。
安娜操作一次，能损失的就是当前最大 $z_i$。
萨沙操作一次，能保护当前最大 $z_i$（不让它损失）。

因为安娜先手，所以：

• 第 1 次安娜：损失最大的 $z_i$。
• 第 1 次萨沙：保护剩下的最大 $z_i$（以后安娜不能动它）。
• 第 2 次安娜：损失剩下的最大 $z_i$（在未被保护的那些里）。
• 第 2 次萨沙：保护剩下的最大 $z_i$。
• ...

所以最终 被安娜损失掉 的 $z_i$ 是：
把 $z_i$ 从大到小排序，安娜取第 1, 3, 5, … 大的（奇数位置，从 1 开始），萨沙取第 2, 4, 6, … 大的（偶数位置）。

---

六、最终位数计算

初始总位数 $S = \sum len_i$
安娜损失掉的零的总数 $Z_{\text{lost}} = \sum_{j \text{ 奇数}} z_{(j)}$（排序后从大到小）。

最终位数 $= S - Z_{\text{lost}}$

若 $\ge m+1$ 则萨沙赢，否则安娜赢。

等价于：
若 $S - Z_{\text{lost}} \ge m+1$，即 $S - Z_{\text{lost}} - 1 \ge m$，输出 "Sasha"，否则 "Anna"。

---

七、标程解读

void build() {
    memset(zrr, 0, sizeof(*zrr) * n);
    for (int i = 0; i < n; ++i) {
        len[i] = arr[i].size();
        for (auto it = arr[i].rbegin(); it != arr[i].rend() && *it == '0'; ++it) {
            ++zrr[i];
        }
    }
}

• 计算每个数的长度 $len_i$ 和末尾零个数 $z_i$。

string solve() {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += len[i] - zrr[i];
    }
    sort(zrr, zrr + n);
    reverse(zrr, zrr + n);
    for (int i = 0; i < n; ++i) {
        if (i & 1) ans += zrr[i];
    }
    return (ans - 1 >= m ? "Sasha" : "Anna");
}

• ans 先累加 $len_i - z_i$，即去掉末尾零后的长度（这些是安娜无法去掉的部分）。
• 对 $z_i$ 从大到小排序。
• 奇数下标（$i=1,3,5,\dots$）的 $z_i$ 被安娜损失掉，所以 $ans$ 加上它们（因为这些 $z_i$ 在最终数字里不存在，但上面没加它们，所以这里加回？ 等等，这里需要仔细分析）。

其实代码逻辑是：

1. $ans = \sum (len_i - z_i)$
   这是如果所有数字都去掉末尾零的最小可能总位数（安娜全反转的情况）。
2. 然后排序 $z_i$ 从大到小。
3. 对奇数下标（$i=1,3,\dots$）的 $z_i$，这些是安娜 实际能去掉的（因为萨沙保护了偶数下标的那些），所以把这些 $z_i$ 加回 $ans$，表示它们不会被去掉，而是保留在最终数字中。

等等，这个推导容易乱。我们重新整理：

---

正确推导：

初始总位数 $S = \sum len_i$
假设我们让所有数字都去掉末尾零（安娜全胜），总位数 $= \sum (len_i - z_i)$。
但萨沙能保护一些零不被去掉。
保护的是：排序后偶数下标（从大到小，下标从 0 开始）的 $z_i$ 被保护。
所以最终位数 = $\sum (len_i - z_i) + \sum_{j \text{ even}} z_{(j)}$。

因为萨沙保护的那些 $z_i$ 会被保留，所以加回去。

因此：

• 先算 $base = \sum (len_i - z_i)$
• 排序 $z_i$ 降序
• 对所有偶数下标（0-based）的 $z_i$，$base += z_i$
• 最终 $base$ 就是最终位数

检查代码：if (i & 1) 是奇数下标（1-based 的偶数是 0-based 的奇数吗？），这里容易混。

我们验证例子：

比如 $z = [3,2,1]$，排序降序 $[3,2,1]$
下标 0 1 2
萨沙保护偶数下标 0 和 2 吗？ 不，安娜先手，安娜取下标 0（3），萨沙保护下标 1（2），安娜取下标 2（1）。
安娜实际去掉的是下标 0 和 2，萨沙保护的是下标 1。
所以被保留的零是 $z_1=2$。
最终位数 $= \sum (len_i - z_i) + 2$。

公式：保留的零 = 所有偶数下标（从 1 开始数）的 $z$，即 1-based 偶数是 0-based 奇数下标。
所以代码 if (i & 1) 对应 0-based 奇数下标，这些是萨沙保护的，所以加回 $ans$。

---

八、例子验证

例 1:
$n=2,m=2$, $a=[14,2]$
len = [2,1], z = [0,0]
base = 2+1=3
排序 z = [0,0]
奇数下标 i=1 加 0 → ans=3
ans-1=2 >= m=2 → Sasha ✓

例 2:
$n=4,m=5$, $a=[5000,123,30,4]$
len = [4,3,2,1], z = [3,0,1,0]
base = (4-3)+(3-0)+(2-1)+(1-0)=1+3+1+1=6
排序 z = [3,1,0,0]
i=1 加 1, i=3 加 0 → ans=7
ans-1=6 >= m=5 → Sasha ✓

---

九、复杂度

• 计算每个数的长度和末尾零：$O(\sum \text{len}(a_i))$
• 排序 $O(n \log n)$
• 总复杂度 $O(n \log n)$，可以通过计数排序优化到 $O(n)$，但 $n \le 2\times 10^5$ 时足够。

---

十、最终结论

核心思想：

1. 比较最终数字的位数是否 $\ge m+1$。
2. 安娜只能通过去掉末尾零减少位数。
3. 安娜先手，两人轮流，安娜去掉当前最大末尾零，萨沙保护下一个最大末尾零。
4. 按末尾零排序，奇数位置（0-based）的被保护，偶数位置被去掉。
5. 最终位数 = $\sum (len_i - z_i) + \sum_{\text{protected}} z_i$。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200200;

int n, m;
string arr[MAXN];
int len[MAXN], zrr[MAXN];

void build() {
    memset(zrr, 0, sizeof(*zrr) * n);
    for (int i = 0; i < n; ++i) {
        len[i] = arr[i].size();
        for (auto it = arr[i].rbegin(); it != arr[i].rend() && *it == '0'; ++it) {
            ++zrr[i];
        }
    }
}

string solve() {
    int ans = 0;
    // 先计算所有数字去掉末尾零后的总长度
    for (int i = 0; i < n; ++i) {
        ans += len[i] - zrr[i];
    }
    // 按末尾零个数从大到小排序
    sort(zrr, zrr + n);
    reverse(zrr, zrr + n);
    // 萨沙保护的末尾零（偶数下标，0-based）加回来
    for (int i = 0; i < n; ++i) {
        if (i & 1) { // 奇数下标（0-based）对应被保护的那些
            ans += zrr[i];
        }
    }
    // 最终位数是否 >= m+1
    return (ans - 1 >= m) ? "Sasha" : "Anna";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
        }
        build();
        cout << solve() << '\n';
    }
    
    return 0;
}