题目描述

在一个聚会上，除了你以外还有 $N$ 个人。你想给他们表演一个非常厉害的魔术。

你给每个人发一本笔记本，最初每本笔记本都是空的。随后你的眼睛被蒙上。接下来重复以下过程 $Q$ 次：

1. 有一个人走到你面前；

2. 你最多可以向这个人提出 $K$ 个问题，问题形式为：

   kas x
   

   含义是：“你的笔记本里是否已经写有单词 $x$？”

   对方会如实回答。如果单词 $x$ 还没有写在他的笔记本里，那么他会把它写进去。

3. 当你问完足够多的问题后，必须说出下面两种判断之一：

   uus y
   

   表示：“你是第一次来到我面前，我给你取昵称 $y$。”

   或：

   vana y
   

   表示：“你之前已经来到过我面前，我之前给你的昵称是 $y$。”

4. 如果你的判断正确，这个人就离开；如果判断错误，则魔术失败，你的程序会在该测试中得到 $0$ 分。

你的任务是编写程序，成功完成这个魔术。

交互协议

本题在原比赛中是交互题。Hydro 版本中，评测程序会在同一进程中模拟交互。你的程序仍然按照交互题方式读写标准输入输出。

首先，程序需要读入四个整数：

$$N, Q, K, A$$

其中：

• $1 \le N \le 900$；
• $1 \le Q \le 900$；
• $K = 75$；
• $1 \le A \le 4$，表示测试组编号，见“评分方式”。

提问

如果你想问一个问题，应输出一行：

kas x

其中 $x$ 是一个单词。

单词可以包含 ASCII 编码在 $33$ 到 $126$ 之间的所有字符，也就是数字、英文字母大小写和常见标点符号，但不能包含空格。单词长度不能超过 $30$ 个字符。

评测程序会返回一行：

jah

或：

ei

其中 jah 表示“是”，ei 表示“否”。

作出判断

如果你认为当前的人是第一次出现，应输出：

uus y

如果你认为当前的人以前已经出现过，应输出：

vana y

其中 $y$ 是昵称，格式限制与单词相同：长度不超过 $30$，且只能包含 ASCII 编码 $33$ 到 $126$ 的字符，不能包含空格。

如果判断正确，评测程序会返回：

ok

如果发生错误，评测程序会返回：

viga

此时该测试得 $0$ 分，你的程序应立即结束。

错误情况

如果发生以下任意一种情况，评测程序会返回 viga，并且该测试得 $0$ 分：

• 输出的行不符合协议，例如：
  • 空行；
  • 不是以 kas、uus 或 vana 开头；
  • 单词或昵称过长；
  • 单词或昵称包含非法字符；
  • 除命令和单词/昵称以外还有多余内容；
• 连续向同一个人提出超过 $K$ 个问题；
• 试图给某个人取一个已经被其他人使用过的昵称；
• 使用 vana y，但昵称 $y$ 此前没有给任何人使用过；
• 作出错误判断。

关于适应性

评测程序是适应性的。也就是说，来到你面前的人的顺序不一定预先固定，评测程序可以根据你的程序行为动态决定。

甚至在某些测试中，评测程序可能直到你作出判断时，才真正确定当前站在你面前的是谁。

不过，评测程序保证：它给出的回答始终与至少一种可能的出场顺序一致。

输出刷新

为了保证评测程序及时收到你的输出，每输出一行后必须刷新输出缓冲区。

C++ 中可以使用：

cout << "kas " << x << endl;

或：

cout << "kas " << x << "\n" << flush;

Python 中可以使用：

print(..., flush=True)

或手动调用：

sys.stdout.flush()

样例交互

下面仅展示一次可能的交互过程，实际评测中的出场顺序和回答可能不同。

评测程序输出

4 3 75 4

你的程序与评测程序交互

kas apple

ei

uus Alice

ok

kas apple

jah

vana Alice

ok

评分方式

测试分为 $4$ 个测试组。只有通过某个测试组中的所有测试，才能获得该组分数。

测试组	分值	限制
1	5	$N = 2$
2	20	$N = 30$
3		每个人最多出现在你面前两次
4	15	无额外限制

Hydro 版本说明

本题原本是交互题。为了适配 Hydro OJ，本包内提供了模拟交互的 grader.cpp。选手提交仍然写成普通交互程序：从标准输入读取 $N,Q,K,A$，然后按协议输出 kas / uus / vana 并读取评测程序回复。