题意回顾

• 小写字母 $a$–$z$ 对应 ASCII 码 97–122，转为 8 位二进制。
• 一个长度为 $n$ 的字符串 $s$ 被转成 $8n$ 位的二进制串。
• 二进制串的比特顺序被打乱（即 0/1 的个数不变，但顺序随机）。
• 要求还原出原字母串或判断无解。

数据范围：$n \leq 10^5$。

---

关键观察

1. 字母的二进制特征

小写字母 ASCII 码范围 97–122，二进制形式特点：

• 最高位（第 8 位）总是 0（因为 97–122 < 128）
• 第 7 位总是 1（因为 97–122 ≥ 64）
• 所以每个字母的 8 位二进制形如 01xxxxxx，其中 x 是 0 或 1。

具体来说：

• 97 = 01100001
• 122 = 01111010

---

2. 统计约束

设输入 01 串中：

• 0 的总数 = $cnt_0$
• 1 的总数 = $cnt_1$

由于每个字母的二进制有：

• 固定 1 个 0 在第 8 位
• 固定 1 个 1 在第 7 位
• 其余 6 位中：0 的个数可以是 0–6，1 的个数 = 6 - (0 的个数)

所以对于 $n$ 个字母：

• 总 0 数 = $n$（来自最高位） + 其余位的 0 数
• 总 1 数 = $n$（来自第 7 位） + 其余位的 1 数

设其余 6n 位中 0 的个数为 $z$，则： $ cnt_0 = n + z,\quad cnt_1 = n + (6n - z) = 7n - z $ 因此： $cnt_0 + cnt_1 = 8n$ 并且： $cnt_1 - cnt_0 = (7n - z) - (n + z) = 6n - 2z$ 所以： $z = \frac{6n - (cnt_1 - cnt_0)}{2}$ $z$ 必须是整数且在 $[0, 6n]$ 之间，否则无解。

---

3. 可行性条件

设每个字母的其余 6 位中有 $k_i$ 个 0，则： $\sum_{i=1}^n k_i = z,\quad 0 \leq k_i \leq 6$ 并且每个字母的 ASCII 码必须在 97–122 之间。

ASCII 码值 = $64 +$（其余 6 位的整数值），范围 64–127。
但字母范围是 97–122，所以其余 6 位的值必须在 33–58 之间（因为 97-64=33, 122-64=58）。

---

4. 其余 6 位的值范围

其余 6 位看作 6 位无符号整数，范围 0–63。
但字母要求该值在 33–58 之间（十进制）。

二进制看：33 = 100001，58 = 111010。
所以其余 6 位的二进制必须满足数值在 33–58 之间。

---

问题转化

我们已知：

• 总 0 数 $cnt_0$，总 1 数 $cnt_1$
• 其余 6n 位中 0 的个数 $z = cnt_0 - n$
• 需要将 $z$ 个 0 分配到 $n$ 个 6 位组中，每个组 0 的个数 $k_i \in [0,6]$，且该 6 位二进制数值在 33–58 之间。

---

构造解法

1. 检查必要条件

• $cnt_0 + cnt_1 = 8n$
• $z = cnt_0 - n$ 是整数且 $0 \leq z \leq 6n$
• 存在 $n$ 个 $k_i \in [0,6]$ 且 $\sum k_i = z$，且对应数值在 33–58 之间

---

2. 判断是否存在这样的 $k_i$

我们检查每个可能的 $k$（0–6）对应的数值范围是否与 [33,58] 有交集。

$k$ = 其余 6 位中 0 的个数，那么 1 的个数 = $6-k$。

数值范围：最小是 把 1 放在高位，例如 $k=0$ 时是 63（111111），$k=6$ 时是 0（000000）。
但我们需要数值在 33–58 之间。

实际上，数值 = 6 位二进制数的十进制值。我们枚举 $k=0..6$，列出所有 6 位二进制数中 0 的个数为 $k$ 且值在 33–58 之间的那些。

---

3. 枚举验证

手工枚举（或程序预处理）：

• $k=0$: 只有 111111=63，不在 [33,58] → 不可行
• $k=1$: 有 111110=62, 111101=61, ..., 最小是 011111=31，最大 63，但 31<33，所以可能没有在 [33,58] 之间的？检查：101111=47, 110111=55, 111011=59, 111101=61, 111110=62，只有 47,55 在范围内。所以 $k=1$ 可行。
• $k=2$: 例如 110111=55, 101111=47, 100111=39, 011011=27(<33), 101011=43, 110011=51, 111001=57, 111010=58, 111100=60(>58) 等，有很多在 [33,58] 之间。
• $k=3$: 也有很多，如 101010=42, 101100=44, 110010=50, 110100=52, 101001=41 等。
• $k=4$: 如 100110=38, 101000=40, 100101=37, 100011=35, 010110=22(<33) 等，较少但存在。
• $k=5$: 如 100010=34, 100001=33, 010010=18(<33) 等，只有 33,34 可行。
• $k=6$: 只有 000000=0，不在范围。

所以可行的 $k$ 值集合 $S = \{1,2,3,4,5\}$。

---

4. 构造分配

我们需要将 $z$ 分配到 $n$ 个位置，每个位置取值在 $S$ 中。

这是经典的可行性分配问题：
设 $a = \min(S) = 1$，$b = \max(S) = 5$。
可行当且仅当 $n \cdot a \leq z \leq n \cdot b$。

因为我们可以用 $a$ 和 $b$ 调整总和：先全填 $a$，然后逐个增加至 $b$ 直到总和达到 $z$。

所以条件：$n \leq z \leq 5n$。

由于 $z = cnt_0 - n$，所以 $n \leq cnt_0 - n \leq 5n$，即： $2n \leq cnt_0 \leq 6n$ 这就是最终的可解条件。

---

5. 构造字母

一旦 $2n \leq cnt_0 \leq 6n$，我们一定可以构造出 $n$ 个字母：

• 先给每个字母分配 $k=1$（总和 = $n$）
• 需要增加 $z - n$ 个 0，每次将一个字母的 $k$ 从 1 增加到 2,3,4,5，每次增加 1–4 个 0
• 总能调整到总和 = $z$

并且每个 $k \in \{1,2,3,4,5\}$ 都对应至少一个在 97–122 之间的 ASCII 字符。

---

算法步骤

1. 读入 $n$ 和 01 串
2. 统计 $cnt_0$ 和 $cnt_1$
3. 检查 $cnt_0 + cnt_1 = 8n$ 且 $2n \leq cnt_0 \leq 6n$
4. 若不满足，输出 NIE
5. 否则：
   • 计算 $z = cnt_0 - n$
   • 确定每个位置的 $k_i$：先全 1，然后增加直到总和 $z$
   • 对每个 $k_i$，选一个对应的合法字母输出

---

复杂度

• 统计：$O(n)$
• 构造：$O(n)$
• 总 $O(n)$

---

总结

本题的关键在于：

1. 发现小写字母二进制格式固定（01xxxxxx）
2. 转化为其余 6 位的 0 的个数分配问题
3. 推导出可解条件 $2n \leq cnt_0 \leq 6n$
4. 构造时利用 $k=1..5$ 都有合法字母的性质

这样可在 $O(n)$ 时间内解决问题。