CC BY-NC-SA 2.0 by Argonne National Laboratory on Flickr

在细菌与蛋白质中心，你拥有大量的 DNA 集合。事实上，新的 DNA 链一直在产生。为了整理海量数据，你通过其“唯一子串”来标识每一段 DNA：即数据库中尚未出现的子串。

你的数据库可以快速判断给定的 DNA 片段是否作为子串存在于数据库中。显然，如果某个 DNA 字符串存在于数据库中，那么它的所有子串也都在数据库中。

现在，你想要确定给定 DNA 片段的“唯一性”：它所包含的、不在数据库中的不相交子串的最大数量。

给定查询字符串 $q_1 \dots q_n$ 的长度 $n$，你可以反复询问数据库它是否包含子串 $q_i \dots q_{j-1}$。

举个例子，考虑第一个样例交互。在该案例中，数据库包含字符串 “TGC” 和 “CT”，查询字符串为 “CTGCAA”。它的唯一性为 3，因为它能被拆分为新的子串 “CTGC”、“A” 和 “A”。新的子串 “CTGC” 无法进一步拆分：例如，拆分为 “CT” 和 “GC” 是不允许的，因为这两个子串（可能作为子串）都存在于数据库中。注意，交互过程中并不使用字符串中的实际字符。

你最多可以使用 $2n$ 次数据库查询。

交互

这是一个交互式问题。你的提交将针对一个交互器运行，该交互器读取你的程序的标准输出，并向你的程序的标准输入写入内容。此交互需要遵循特定的协议：

交互器首先发送一行，包含一个整数 $n$ ($1 \le n \le 10\,000$)，即你需要计算唯一性的 DNA 片段的长度。

然后，你的程序应进行最多 $2n$ 次查询。每次查询通过打印一行格式为 “? $i$ $j$” ($0 \le i < j \le n$) 的内容来完成，表示你想查询从位置 $i$ 开始到位置 $j-1$ 结束的子串是否在数据库中出现。交互器将回复 “present” 或 “absent”，表示该子串是否在数据库中找到。

当你确定了该 DNA 片段的唯一性 $x$ 后，打印一行格式为 “! $x$” 的内容，随后交互将停止。打印答案不计入查询次数。

请确保在每次写入后刷新缓冲区。

提供了一个测试工具来帮助你开发解决方案。

使用超过 $2n$ 次查询将导致错误答案。

样例

输入格式 1

6
? 4 6
absent
? 4 5
absent
? 5 6
absent
? 0 1
present
? 0 2
present
? 2 4
present
? 1 4
present
? 0 4
absent

输出格式 1

? 4 6
? 4 5
? 5 6
? 0 1
? 0 2
? 2 4
? 1 4
? 0 4
! 3

输入格式 2

10
? 0 10
absent
? 0 9
present
? 1 10
present

输出格式 2

? 0 10
? 0 9
? 1 10
! 1