时空限制

2.5S/512M

题目描述

这是一道交互题。

apiadu 面前有 $n$ 个人，每个人要么是“精明人”，要么是“糊涂人”。 已知这 $n$ 个人中精明人占多数，即至少有 $\lfloor \frac{n}{2} \rfloor+1$ 个精明人。

由于糊涂人总是胡言乱语，apiadu 对此感到头疼。定义 apiadu 当前的痛苦度为 $2^c$，其中 $c$ 为这群人中糊涂人的总个数。

现在，apiadu 打算施展一次魔术。他需要从这 $n$ 个人中恰好选出 $k$ 个人，这 $k$ 个人的身份将会发生反转（精明人变为糊涂人，糊涂人变为精明人）。 他想知道：在所有的挑选方案中，施展魔术后最终的痛苦度之和是多少？

由于答案可能很大，你需要将答案对 $998244353$ 取模。

但这 $n$ 个人的初始身份是隐藏的，你最多只能进行 $n-1$ 次询问来推断信息。

在一次询问中，你可以让其中一个人评价另一个人是什么身份。具体含义请参考样例说明。

已知：精明人永远说真话，而糊涂人永远说假话。

格式

交互格式

首先，你的程序需要从标准输入中读取两个正整数 $n$ 和 $k$，意义如题目描述。

接下来，你可以发起最多 $n-1$ 次询问。对于每次询问：

• 你需要向标准输出打印 ? x y（其中 $x$ 和 $y$ 是 $1 \sim n$ 之间的整数，表示询问第 $x$ 个人觉得第 $y$ 个人是什么人，且 $x \ne y$），并刷新缓冲区。（例如 C++ 中的 cout << endl; 或 fflush(stdout);）

• 随后，你的程序需要从标准输入读取一个整数。交互器返回的值有以下 $3$ 种情况：

  • 1：代表第 $x$ 个人认为第 $y$ 个人是精明人。
  • 0：代表第 $x$ 个人认为第 $y$ 个人是糊涂人。
  • -1：代表询问次数过多或者询问不合法。遇到此情况，你应该立即结束程序并接受 WA（答案错误）的状态，否则状态可能会变成 RE 或 TLE。

当你计算出最终答案后，你需要按如下格式输出：

• 向标准输出打印 ! ans（其中 ans 是方案的痛苦度之和对 $998244353$ 取模后的结果），并刷新缓冲区，随后正常结束程序。

注意：在每次输出后，请务必打印换行符并刷新标准输出缓冲区。否则，可能会被判为 TLE（超时）。

• 如果你的输出格式不正确或程序异常提前终止，判定结果将是不确定的。
• 在输出答案后，请立即终止程序。

样例

样例输入/输出 #1

以下是一个交互的示例。在这个例子中，第 $3$ 个人是糊涂人，其他人均为精明人。

你的程序输出（标准输出）	交互器返回（标准输入）	解释
	5 2	读取到总人数 $n=5$，挑选进行魔术的人数 $k=2$
? 3 5		询问第 $3$ 个人觉得第 $5$ 个人是什么人
	0	第 $3$ 个人是糊涂人，会说假话，所以回答 0（糊涂人）
? 1 5		询问第 $1$ 个人觉得第 $5$ 个人是什么人
	1	第 $1$ 个人是精明人，会说真话，所以回答 1（精明人）
! 56		成功得出答案并输出。

样例解释：

以下是施展魔术后的所有情况（1 表示精明人，0 表示糊涂人，初始状态为 11011）：

1. 选择第 $1$ 个人和第 $2$ 个人：00011 ，此时痛苦度为 $2^3 = 8$。
2. 选择第 $1$ 个人和第 $3$ 个人：01111 ，此时痛苦度为 $2^1 = 2$。
3. 选择第 $1$ 个人和第 $4$ 个人：01001 ，此时痛苦度为 $2^3 = 8$。
4. 选择第 $1$ 个人和第 $5$ 个人：01010 ，此时痛苦度为 $2^3 = 8$。
5. 选择第 $2$ 个人和第 $3$ 个人：10111 ，此时痛苦度为 $2^1 = 2$。
6. 选择第 $2$ 个人和第 $4$ 个人：10001 ，此时痛苦度为 $2^3 = 8$。
7. 选择第 $2$ 个人和第 $5$ 个人：10010 ，此时痛苦度为 $2^3 = 8$。
8. 选择第 $3$ 个人和第 $4$ 个人：11101 ，此时痛苦度为 $2^1 = 2$。
9. 选择第 $3$ 个人和第 $5$ 个人：11110 ，此时痛苦度为 $2^1 = 2$。
10. 选择第 $4$ 个人和第 $5$ 个人：11000 ，此时痛苦度为 $2^3 = 8$。

所有情况的痛苦度求和为 $8 + 2 + 8 + 8 + 2 + 8 + 8 + 2 + 2 + 8 = 56$。

注意，样例只是说明交互格式，无法保证得出结果的过程有依据。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	限制条件
$1$	$30$	第 $1$ 个人是糊涂人
$2$	$70$	无特殊限制

对于 $100\%$ 的数据，满足 $1 \le n \le 10^5$，$1 \le k \le n$，且初始状态下至少有 $\lfloor \frac{n}{2} \rfloor+1$ 个精明人。每个人是否是精明人在交互开始前就已经固定，交互器不是自适应的。