23636번 - 배열 알아맞히기 인터랙티브

베시는 양의 정수로 이루어진 수열 $A = \{A_1, A_2, \cdots, A_N\}$를 가지고 있다. 이 수열은 다음과 같은 특징을 가진다.

• $A$의 길이 $N$은 4의 배수이다.
• $A$의 원소는 모두 $A_i=a \times (i-1)+b$ 의 형태로 나타낼 수 있다. 즉, $A$는 공차가 $a$이고 초항이 $b$인 등차수열의 첫 $N$개의 항이다. ($1 \leq a, b \leq 1,000,000,000$, $~a, b$는 정수)

하지만 베시의 컴퓨터가 고장 나 수열의 $N/4$개의 원소에 양의 정수 $k$가 더해졌다. ($1 \leq k \leq 1,000,000,000$)

베시를 위해 수열 $A$의 공차 $a$, 초항 $b$, 그리고 더해진 값 $k$를 구해보자.

첫 번째 줄에 베시가 가지고 있는 수열의 크기를 나타내는 정수 $N$이 주어진다.

• $1 \leq N \leq 500,000$
• $N \equiv 0 \pmod 4$

채점기는 적응적이지 않다. 즉, 베시의 수열은 채점 데이터에 저장되어 있으며, 실행 중에 생성되거나 변경되지 않는다.

당신은 베시에게 아래와 같은 질문을 최대 200번까지 할 수 있다. 질문 횟수가 200번을 초과하거나 조건을 만족하지 않을 경우 틀렸습니다를 받는다.

• ? p q - 수열의 $p~$번째 원소와 $q~$번째 원소의 합을 물어본다. ($1 \leq p, q \leq N,~ p \neq q$, $~p, q$는 정수)

정답은 다음과 같이 출력한다.

• ! a b k - 공차가 $a$이고 초항이 $b$이며, 더해진 값은 $k$이다. ($1 \leq a, b, k \leq 1,000,000,000$, $~a, b, k$는 정수)

각 출력에 대해 개행 문자는 정확히 하나여야 한다. 질문이나 정답을 출력한 다음에는 반드시 표준 출력 버퍼를 flush 해야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다.

정답을 출력한 이후에는 다른 출력을 하지 않고 프로그램을 종료해야 한다.

언어 별로 표준 출력 버퍼를 flush 하는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()
• 기타 언어의 경우 각 언어의 documentation을 참조하라.