fork()==0世界线变动

本题为交互题，使用 IO 交互。

在你输出一行后，请清空缓冲区：

• 在 C++ 中，使用 fflush(stdout) 或 cout.flush()。

• 在 Pascal 中，使用 flush(output)。

• 在 Python 中，使用 stdout.flush()。

• 其他语言请自行查阅文档。

请遵循题目完成交互，发出不合法询问可能会出现 TLE，WA 等问题。

给定一个长度为 $n$ 且只包含小写字母的字符串 $S$，你需要猜出它。

一共有 $4$ 种交互方式：

| 格式 | 允许调用次数 | 限制 | 返回值 | 说明 |

| :----------: | :----------: | :----------: | :----------: | :----------: |

| 无 | $1$ | 无 | 一个整数，$n$ 的值。 | 在最开始调用。 |

| ? 1 i | $26$ | $i$ 为 $[1,n]$ 范围内的整数。 | 一个字符，$S_i$（$S$ 的第 $i$ 个字符）。 | 无 |

| ? 2 l r | $6 \times 10^3$ | $1 \le l \le r \le n$，且 $l,r$ 为整数。 | 一个整数，$S_{l \ldots r}$（$S$ 的第 $l$ 至 $r$ 个字符）中不同字符的种数。 | 无 |

| ! s | $1$ | $s$ 是一个字符串，代表你所认为的 $S$。 | （评测结果——AC 或 WA。） | 最后调用，然后停止交互。 |

对于 $100\%$ 的数据，$1 \le n \le 10^3$。

题意简述

要求您构造一个长度为 $n$ 的由小写字母构成的字符串，使得字符串内每个字串出现奇数次。

输入格式

第一行输入一个整数 $t$ 表示数据组数。

对于每组数据输入一个整数 $n$ 表示字符串长度。

输出格式

对于每组数据，输出一行长度为 $n$ 的满足题意的字符串。若有多组解任意输出一组即可。

说明/提示

在第一组数据里， $\texttt{abc}$ 的每个子串都恰好只出现一次。

在第三组数据里，$\texttt{bbcaabbba}$ 的每个子串出现奇数次，其中 $\texttt{b}$ 出现 $5$ 次，$\texttt{a}$ 和 $\texttt{bb}$ 各出现 $3$ 次，其它子串各出现 $1$ 次。

数据范围及约定

对于 $100\%$ 的数据，$1\le t\le 500$，$1\le n \le 10^5$，$1\le \sum n\le 3\times 10^5$。

给定一个大小为 $n \times m$ 的网格，每一个网格都有颜色 $c_{i,j}$。

最初，你有一个没有颜色的网格，可以进行若干次操作：

• 选择两个整数 $i$ 和 $j(1\le i < n,1 \le j < m)$，并且选择一种颜色 $k(1 \le k \le nm)$。

• 将格子 $(i,j)$，$(i + 1,j)$，$(i,j+1)$，$(i+1,j+1)$ 涂为颜色 $k$。

询问是否能进行不超过 $nm$ 次操作，将空白网格涂成给定的网格。

如果不能，输出 $-1$，否则输出方案。

数据范围：

$2\le n,m \le 1000,1 \le c_{i,j} \le nm$。

Koxia 和 Mahiru 正在玩一个游戏。游戏使用 $a,b,c$ 三个长度为 $n$ 的数组，共进行 $n$ 轮。

每一轮中，Koxia 先在 $a_i,b_i,c_i$ 中选择一个数字，Mahiru 再从未选择的两个数字中选择一个。

如果 $n$ 轮后 Mahiru 选择的数字刚好包含 $1$ 至 $n$ 中每个数字各一个（即为 $1$ 至 $n$ 的一个排列），则 Koxia 获胜。否则，Mahiru 获胜。

假设双方都采取最优策略，给定 $a,b$ 数组，求使得 Koxia 必胜的 $c$ 数组的个数。

有一棵树，有3种颜色，第$i$个节点染成第$j$种颜色的代价是$c_{j,i}$，现在要你求出一种染色方案，使得总代价最小，且对于任意三个相邻的节点，颜色不能相同。输出最小代价与其中一种方案。无解输出$-1$。

$3\le n\le 10^5$

有 $T$ 组数据，每组数据有一个长度为 $n$ 的 $\tt 01$ 字符串，求构造一个 $n$ 个结点的树满足每个结点的度数的奇偶性符合 $\tt 01$ 串 $s$，且将这些点依次排列到一个环上，任意两条边不在非端点处相交。

现在有一个正整数序列 $a$ , 你可以选择一个位置 $i$ ，进行一次操作：将 $a_i$ 减去 $2$ ，将 $a_{i-1}$（如果存在）减去 $1$ ，将 $a_{i+1}$（如果存在）减去 $1$，问至少要多少次操作可以使数列中至少出现两个非正整数。

Translated by CmsMartin