Source

This problem is proposed by . All rights reserved.

Problem Source: https://www.luogu.com.cn/problem/T565373

Problem Background

I wish to stand atop the mountains, gazing at the starry Milky Way above and the vast world below.

Problem Description

This is an interactive problem.

The "God" is touring the "world" he created.

He sees a mountain range of length $n$ with strictly increasing heights (i.e., $n$ peaks with heights $a_1\sim a_n$ in strictly ascending order).

Thus, "God" wants to climb the highest peak to enjoy the view, and you need to tell him the position of the highest peak.

However, he thinks this problem is too simple for you, so he will perform $m$ modifications, each time raising or lowering the heights of the peaks in the interval $[l, r]$ by a certain amount. After each modification by "God," you need to tell him the position of the highest peak (if there are multiple, any one is acceptable).

Of course, you may not have the divine power to know the exact height of each peak like "God," so after each operation, you can ask "God" no more than $k$ times to compare the heights of two peaks $x$ and $y$. If "God" answers 0, it means $a_x < a_y$; if the answer is 1, it means $a_x \ge a_y$.

Input Format

The first line contains three integers $n, m, k$.

Then, $m$ lines follow, each containing two integers $l, r$.

Output Format

If you need to ask "God" about the height comparison between peaks $x$ and $y$, output ? x y.

If you want to tell "God" the position $x$ of the highest peak, output ! x.

Samples

5 3 100
1 2

0

2 4

0

1

1 2

1

? 2 5

! 5

? 1 2

? 4 5

! 4

? 2 4

! 2

Sample Explanation

Initially, the mountain heights are: $\{1,2,3,4,5\}$.
The first operation adds $1$ to the interval $[1,2]$, changing the heights to: $\{2,3,3,4,5\}$.
The second operation adds $2$ to the interval $[2,4]$, changing the heights to: $\{2,5,5,6,5\}$.
The third operation adds $3$ to the interval $[1,2]$, changing the heights to: $\{5,8,5,6,5\}$.

Data Range

This problem uses bundled tests.

• For all data:
  • $1 \le n \le 10^5$.
  • $1 \le m \le 10^4$.
  • $34 \le k \le 10^5$.
  • $1 \le l \le r \le n$.
  • $1 \le a_1 < a_2 < \ldots < a_n \le 10^9$.

Your provided $x, y$ must satisfy $1 \le x, y \le n$.

The time complexity for each SPJ response is $O(\log n)$.

Please flush the buffer after each output. You can use the following commands to flush the buffer:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);
• For other languages, please refer to their respective documentation.
• Specifically for C++, using std::endl instead of '\n' will automatically flush the buffer.