题目描述

这是一道交互题。

你是“皮薄馅大”牌餐盘制造厂的质检员。作为一个聪明的质检员，你接到了一个任务：检测你家盘子的质量。

已知你家的盘子从$0$米的高度摔下不会碎，从$N+1$米的高度摔下一定会碎，也就是说，我们一开始知道盘子的耐摔度在$[0,N]$之间。

你的测试方法是：选定一个整数高度$H$，然后把盘子从$H$米处扔下来，如果盘子碎了，说明你家盘子的耐摔度在$[0,H-1]$之间，如果没碎，说明你家盘子的耐摔度在$[H,N]$之间。

你需要通过若干次测试，把盘子的耐摔度确定成一个长度为$0$的整数区间。

由于你家的盘子皮薄馅大，生产难度很高，所以盘子很贵，你只拿到了$K$个盘子，也就是，盘子碎完你就不能继续测试了。

由于你的领导完美主义，追求极致，所以只让你测试最多$M$次。

现在，请你在$M$次内测试出这个盘子真正的耐摔度。

输入格式

首先，请你从标准读入里面读入$N,K,M$，参数如题意所示。

然后，你需要通过如下形式与交互库交互：

1：输出一个$[1,N]$范围内的正整数给标准输出，然后执行fflush(stdout)。

2：从标准输入中读入结果，如果盘子碎了，标准输入会输入到字符串gg，否则会输入到字符串notgg。

当你测试的过程中交互库发现已经能确定答案的时候，请输出$-ans$，然后记得执行fflush(stdout)。

输出格式

无。

样例输入1

5 1 5
notgg
notgg
gg

样例输出1

1
2
3
-2

样例解释1

你首先读入了$5,1,5$三个参数，由于你只有一个盘子，所以只能按顺序询问。

交互库会回答notgg,notgg,gg，当第盘子在高度$3$碎了，而高度$2$没碎的时候，我们已经可以确定答案是$2$了，所以输出了答案$-2$。

样例输入2

4 2 3
gg
notgg
gg

样例输出2

3
1
2
-1

样例解释2

这次你有$2$个盘子，你先询问了$3$米的高度，盘子碎了，因此你得知答案在$[0,2]$范围内，你又询问了$1$，盘子没碎，答案在$[1,2]$范围内，接下来你询问了$2$，盘子碎了，因此你得知答案是$1$。

数据范围

因为出题人的懒惰，本题交互库不是自适应的，而是会预先选好一个答案。

Subtask 1（5分）：$K=1,N=M$。

Subtask 2（15分）：$K=M=10,N\leq 1000$。

Subtask 3（15分）：$N\leq 100$。

Subtask 4（10分）：$K=2,N\leq 1000,M=45$。

Subtask 5（15分）：$K=3,N\leq 1000,M=19$。

Subtask 6（10分）：$N\leq 1000,K\leq 10$。

Subtask 7（30分）：无特殊限制。

对于所有数据：$N\leq 10^9,K\leq 30，1\leq M\leq 40000$，给定的$M$保证有解。

提示

对于彻底没用过CF式交互的同学，这是一个例子。

int n,k,m;
cin>>n>>k>>m;
int lef=0,rig=n;
for (int i=1;i<=m;i++)
{
    int pos=rand()%n+1;
    cout<<pos<<endl; fflush(stdout);
    string s;
    cin>>s;
    if (s=="gg") rig=min(rig,pos-1); else lef=max(lef,pos);
}
if (lef==rig) cout<<-lef<<endl;
else cout<<"我不会"<<endl;