33477번 - 위너의 반대말은? 서브태스크인터랙티브

문제

위너의 반댓말은? 아레나

2023년 여름 개최된 <제3회 MatKor Cup: 2023 Summer>은 역대 MatKor Cup 중 가장 특이한 대회이다. 우선 Solved.ac 아레나로 개최되었으며, 난이도별로 Div. 1과 Div. 2를 나누어 개최되었다. 또한, 문제의 지문이 전체적으로 매우 길 었 으 며, 2024년 12월 31일 기준 현재까지 열렸던 대회 중 가장 높은 티어의 문제가 출제되었다. 또한, 이 대회에서는 MatKor Cup 최초로 인터랙티브 문제가 등장한 대회이다. 그러나 놀랍게도 이 대회에 참가한 후 깊은 감명을 받아 MatKor에 가입한 사람이 있다.

이 문제는 인터랙티브 문제입니다

<제3회 MatKor Cup: 2023 Summer>에 출제되었던 오락 고! 의 경우 원형에서 게임을 진행하는데, 이를 보고 영감을 받은 세준이는 원형에서 진행하는 인터랙티브 문제를 내려고 한다.

수열 $A_1,A_2,\cdots ,A_N$의 원소가 서로 다르며, 1ドル$ 이상 $N$ 이하의 정수로 이루어져 있는 경우 순열이라 한다. 순열 $A$의 1ドル\le i<N$에 대해 $A_i$의 오른쪽에는 $A_{i+1}$이 있고, $A_N$의 오른쪽에는 다시 $A_1$이 쓰여진 원형으로 순열이 배치된 경우를 원순열이라 한다. 이 원순열의 $A_x=1,ドル $A_y=N$이라고 할 때, 다음 두 가지를 만족하면 바이토닉 원순열이라고 한다.

• $A_x$부터 시작하여 $A_y$까지 오른쪽으로 이동할 때 수가 증가한다.
• $A_x$부터 시작하여 $A_y$까지 왼쪽으로 이동할 때 수가 증가한다.

재우는 동우가 바이토닉 원순열을 가지고 있는 것을 안다. 1ドル$과 $N$의 위치 $x$와 $y$를 알아내려 한다. 재우는 정해진 상수 $M$에 대해 다음 질문을 최대 $Q$번 할 수 있다.

• ? $i$ : $A_i$부터 오른쪽 $M$개의 수들 중 최솟값과 최댓값을 물어본다. 이때, $M$개의 수는 $A_i$ 부터, $A_i$에서 $M-1$번째 오른쪽에 있는 수까지 양 끝을 포함한 수들을 의미한다.

재우는 위의 질문을 원하는 만큼 한 후, 위의 질문 횟수에 포함되지 않는 예측을 한 번 할 수 있다.

• ! $x$ $y$: 1ドル$과 $N$의 위치 $x$와 $y$를 예측한다.

재우를 도와 1ドル$과 $N$의 위치 $x$와 $y$를 예측해 보자.

입력

컴퓨터는 동우, 유저는 재우로 생각하고 인터랙티브가 진행된다.

먼저 컴퓨터가 순열의 원소의 개수 $N,ドル 정해진 정수 상수 $M,ドル 질문의 최대 횟수 $Q$가 공백으로 구분되어 주어진다.

유저는 질문을 하거나 예측을 해야한다. 질문과 예측은 문제에서 주어진 형식으로 해야 한다. 즉, 아래 중 하나의 형식으로 출력해야 한다.

• ? $i$: $A_i$ 부터 시작하여 $A_i$를 포함해 오른쪽 $M$개의 수들 중 최솟값과 최댓값을 물어본다. $(1\le i\le N)$
• ! $x$ $y$: 1ドル$과 $N$의 위치 $x$와 $y$를 예측한다. $(1\le x,y\le N)$

유저가 질문을 한 경우 컴퓨터는 최솟값과 최댓값을 순서대로 공백으로 구분하여 한 줄에 알려준다.

유저가 예측을 한 경우 컴퓨터는 더 이상 입력을 주지 않고 맞았는지 판단한다.

예측을 한 경우 추가적인 입력 혹은 출력 없이 즉시 프로그램을 종료해야 한다.

$Q+1$개 이상의 질문을 하거나 잘못된 예측을 한 경우 컴퓨터는 즉시 틀렸습니다를 띄우고 프로그램을 종료한다.

인터랙션 도중 컴퓨터에게 정상적인 출력이 전달되지 않았거나 덜 전달된 경우, 줄바꿈을 하지 않거나 flush를 하지 않은 경우, 혹은 정답 출력 후 프로그램이 종료되지 않는 경우 등의 상황에는 틀렸습니다 혹은 시간 초과를 받을 수 있다.

출력

제한

서브태스크

힌트