版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T565373

题目背景

我欲于群山之巅，仰望群星璀璨之银河，俯瞰森罗万象的人间。

题目描述

这是一道交互题。

「神」正在游览他创造的「世界」。

他看到了一片长度为 $n$，逐渐拔高的山脉（即 $n$ 座高度严格上升的山峰），其高度分别为 $a_1\sim a_n$。

于是，「神」想要登上其中最高的山峰观赏这一带的风景，你需要告诉他最高山峰的位置。

不过他觉得这个问题对于你来说太简单了，所以他还会进行 $m$ 次修改，每次会将区间 $[l, r]$ 的山峰拔高或者压低若干高度。你需要在「神」每次修改之后告诉他最高峰的位置，如果有多座，回答任意一座均可。

当然，你有可能并没有「神」那样神力去了解每一座山峰的高度，因此每次「神」操作完之后，你都可以向他询问不超过 $k$ 次两座山峰 $x,y$ 的大小关系。如果「神」的答案是 0，表示 $a_x<a_y$；如果「神」的答案是 1，表示 $a_x\ge a_y$。

输入格式

第一行 $3$ 个整数 $n,m,k$。

然后 $m$ 行，每行两个整数 $l,r$。

输出格式

如果你需要向「神」询问 $x,y$ 两座山峰的大小关系，请输出 ? x y。

如果你想要告诉「神」最高峰的位置 $x$，请输出 ! x。

样例

5 3 100
1 2

0

2 4

0

1

1 2

1

? 2 5

! 5

? 1 2

? 4 5

! 4

? 2 4

! 2

样例解释

一开始山脉的高度为：$\{1,2,3,4,5\}$。
第一次操作在 $[1,2]$ 区间加 $1$，山脉高度变为：$\{2,3,3,4,5\}$。
第二次操作在 $[2,4]$ 区间加 $2$，山脉高度变为：$\{2,5,5,6,5\}$。
第三次操作在 $[1,2]$ 区间加 $3$，山脉高度变为：$\{5,8,5,6,5\}$。

数据范围

本题采用捆绑测试。

• 对于全部数据：
  • $1\le n\le10^5$。
  • $1\le m\le10^4$。
  • $34\le k\le10^5$。
  • $1\le l\le r\le n$。
  • $1\le a_1<a_2<\ldots<a_n\le10^9$。

你给出的 $x,y$ 应满足 $1\le x,y\le n$。

每次 SPJ 给你答复的时间复杂度为 $O(\log n)$。

请注意刷新缓冲区，你可以使用如下语句来刷新缓冲区：

• 对于 C/C++：fflush(stdout);
• 对于 C++：std::cout << std::flush;
• 对于 Java：System.out.flush();
• 对于 Python：stdout.flush();
• 对于 Pascal：flush(output);
• 对于其他语言，请自行查阅对应语言的帮助文档。
• 特别的，对于 C++ 语言，在输出换行时使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。