这是一个交互式问题。

岛上有 $N$ 名骑士。每一名骑士在任何时刻要么是光明骑士，要么是黑暗骑士。光明骑士对任何问题都回答真话，而黑暗骑士对任何问题都撒谎，即把“是”回答为“否”，把“否”回答为“是”。

当任何一名骑士回答“是”时，他在回答后会立即改变阵营，即光明骑士变为黑暗骑士，黑暗骑士变为光明骑士。

你被派往岛上执行一项重要的秘密任务：在你离开岛屿的那一刻，报告光明骑士的数量。

为了获取信息，你可以询问任何一个人关于任何其他人（骑士编号为 $1$ 到 $N$ 的整数）的问题，形式为“骑士 $Y$ 是光明骑士吗？”或“骑士 $Y$ 是黑暗骑士吗？”。你不能询问骑士关于他自己的问题，因为这看起来太可疑了。

你能在有限次数的提问内完成这项任务吗？如果可以，请使用最少可能的提问次数，然后报告当前光明骑士的数量。

注意，评测系统有证据表明，对于任何存在解的情况，都定义了解决此任务的最优提问次数。

交互

在交互开始时，你将收到一个整数 $N$ ($1 \le N \le 1000$)，代表岛上的骑士数量。

然后你可以开始提问。

如果你想询问骑士 $X$，“骑士 $Y$ 是光明骑士吗？”，请使用格式 ? L X Y。 如果你想询问骑士 $X$，“骑士 $Y$ 是黑暗骑士吗？”，请使用格式 ? D X Y。其中 $X$ 和 $Y$ 是 $1$ 到 $N$ 之间的整数。

回答 $1$ 代表“是”，$0$ 代表“否”。

如果你在若干次提问后（或立即）判定无法完成任务，请输出 ! -1 并退出。

如果你在某一时刻判定你已知当前光明骑士的数量，请输出 ! Nl，其中 $Nl$ 是当前光明骑士的数量，并退出。

注意，交互器是自适应的，即它可能会根据你的提问生成初始分布。

如果你判定任务无法完成，你在做出决定前最多可以询问 $4N/3$ 次问题。如果你打算给出答案，你必须使用最少可能的提问次数。

样例

输入 1

3
0
1
0

输出 1

? L 1 2
? D 1 2
? D 3 1
! 0

说明

请记住在每次查询或最终答案的最后一个整数后打印换行符，并刷新输出缓冲区。否则，你的程序可能会出现 WTL 错误。

注意，题目中的样例交互仅用于说明格式——提问者可能没有任何理由得到这些回答，他（如果成功的话）仅仅是靠运气。