A. From Y to Y

_From beginning till end, this message has been waiting to be conveyed._ 对于一个给定的无序多重集（“多重”表示一个字母可以出现多次）包含 #cf_span[n] 个小写英文字母，我们将所有字母视为长度为 #cf_span[1] 的字符串，并重复以下操作 #cf_span[n - 1] 次： 此类操作的代价定义为 ，其中 #cf_span[f(s, c)] 表示字符 #cf_span[c] 在字符串 #cf_span[s] 中出现的次数。 给定一个非负整数 #cf_span[k]，构造一个包含不超过 #cf_span[100 000] 个字母的任意有效非空多重集，使得整个过程的最小累积代价 *恰好* 为 #cf_span[k]。可以证明，解总是存在的。 输入的第一行且唯一一行包含一个非负整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]）——所需的最小代价。 请输出一个非空字符串，包含不超过 #cf_span[100 000] 个小写英文字母——任意满足要求的多重集，以字符串形式拼接而成。 注意：输出的字符串不需要是最终拼接后的字符串，它只需表示一个无序的字母多重集。 对于多重集 {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}，完成该过程的一种方式如下： 总代价为 #cf_span[12]，且可证明这是该过程的最小代价。 ## Input 输入的第一行且唯一一行包含一个非负整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]）——所需的最小代价。 ## Output 请输出一个非空字符串，包含不超过 #cf_span[100 000] 个小写英文字母——任意满足要求的多重集，以字符串形式拼接而成。注意：输出的字符串不需要是最终拼接后的字符串，它只需表示一个无序的字母多重集。 [samples] ## Note 对于多重集 {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}，完成该过程的一种方式如下： {_"ab"_, _"a"_, _"b"_, _"a"_, _"b"_, _"a"_, _"b"_}，代价为 #cf_span[0]； {_"aba"_, _"b"_, _"a"_, _"b"_, _"a"_, _"b"_}，代价为 #cf_span[1]； {_"abab"_, _"a"_, _"b"_, _"a"_, _"b"_}，代价为 #cf_span[1]； {_"abab"_, _"ab"_, _"a"_, _"b"_}，代价为 #cf_span[0]； {_"abab"_, _"aba"_, _"b"_}，代价为 #cf_span[1]； {_"abab"_, _"abab"_}，代价为 #cf_span[1]； {_"abababab"_}，代价为 #cf_span[8]。总代价为 #cf_span[12]，且可证明这是该过程的最小代价。

**Definitions** Let $ k \in \mathbb{Z}_{\geq 0} $ be the required minimum accumulative cost. Let $ S $ be a multiset of lowercase English letters, with $ |S| = n \geq 1 $, and let $ f(S, c) $ denote the frequency of character $ c $ in $ S $. **Operation** Repeatedly select two distinct characters $ c_1, c_2 \in S $, remove one occurrence of each, and add one new character (arbitrary, but not affecting cost) back to $ S $. This reduces the multiset size by 1. Repeat $ n - 1 $ times until one character remains. **Cost of Operation** The cost of removing one occurrence of $ c_1 $ and one of $ c_2 $ is $ f(S, c_1) + f(S, c_2) $, evaluated *before* the removal. **Objective** Construct any multiset $ S $ with $ 1 \leq |S| \leq 100{,}000 $ such that the *minimum possible total cost* over all valid sequences of operations is exactly $ k $. **Key Insight** The minimum total cost is independent of the order of operations and equals: $$ k = \sum_{c \in \Sigma} f(S, c) \cdot (f(S, c) - 1) / 2 $$ That is, the sum over all characters of the number of unordered pairs of identical letters. **Equivalent Formulation** Let $ n_i $ be the frequency of the $ i $-th distinct character in $ S $. Then: $$ k = \sum_{i} \binom{n_i}{2} = \sum_{i} \frac{n_i(n_i - 1)}{2} $$ We must find non-negative integers $ n_1, n_2, \dots, n_m $ (for some $ m \geq 1 $) such that: $$ \sum_{i=1}^m \binom{n_i}{2} = k, \quad \sum_{i=1}^m n_i \leq 100{,}000 $$ **Construction** Use at most two distinct characters: - If $ k = 0 $, output any single character (e.g., `"a"`). - Otherwise, find the largest integer $ a $ such that $ \binom{a}{2} \leq k $. Let $ r = k - \binom{a}{2} $. - If $ r = 0 $, use $ a $ copies of one letter (e.g., `'a' * a`). - If $ r > 0 $, use $ a $ copies of `'a'` and $ b = r + 1 $ copies of `'b'` (since $ \binom{b}{2} = \binom{r+1}{2} $, but we only need $ r = \binom{b}{2} - \binom{b-1}{2} = b-1 $, so set $ b = r + 1 $, then $ \binom{b}{2} - \binom{b-1}{2} = r $, and total cost is $ \binom{a}{2} + r = k $). Thus, construct: - If $ k = 0 $: `"a"` - Else: Let $ a = \left\lfloor \frac{1 + \sqrt{1 + 8k}}{2} \right\rfloor $ Let $ r = k - \binom{a}{2} $ If $ r = 0 $: output `'a' * a` Else: output `'a' * a + 'b' * (r + 1)` **Constraints** $ |S| = a + (r + 1) \leq 100{,}000 $ (guaranteed since $ k \leq 100{,}000 $, and $ a \leq \sqrt{2k} + 1 \ll 100{,}000 $). **Output** A string representing the multiset $ S $, as described.