题目描述

交互器隐藏了一个长度为 $n$ 的小写字符串 $s$。你开始时只知道 $n$，需要通过询问还原整个字符串。

你可以使用两类询问：

• ? 1 i：询问第 $i$ 个字符，交互器返回 $s_i$；
• ? 2 l r：询问区间 $[l,r]$ 中不同字符的数量。

第一类询问最多 $26$ 次，第二类询问最多 $6000$ 次。

输入格式

交互开始时，交互器会先给出整数 $n$。

本地交互器的隐藏输入文件包含一个小写字符串 $s$，其长度即为 $n$。

输出格式

询问第 $1$ 类时输出 ? 1 i，询问第 $2$ 类时输出 ? 2 l r，每次询问后都需要刷新输出。

若已经还原字符串，输出一行 ! s，其中 $s$ 为你得到的完整字符串，然后刷新输出并结束程序。

若询问格式错误或次数超限，交互器会返回 $0$。

样例

5
4
u
2
g
e
s
1

? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess

样例说明

样例是隐藏串为 guess 时的一段交互记录。

数据范围

$1\le n\le 1000$，字符串只包含小写英文字母。第 $1$ 类询问不超过 $26$ 次，第 $2$ 类询问不超过 $6000$ 次。