시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB82161016.667%

문제

베시는 길이가 4의 배수인 수열을 하나 가지고 있다. 놀랍게도 수열의 원소는 ax+b의 형태로 나타낼 수 있는 등차수열이다.

따라서, 수열은 [b, a+b, 2a+b, 3a+b, ...] 형태가 된다. 하지만 베시의 컴퓨터가 고장나 이 중 1/4개의 원소에 k값이 더해져버렸다. 당신은 베시에게 아래와 같은 질문을 할 수 있다.

? p q - 수열의 p번째 원소와 q번째 원소의 합을 물어본다. (1 ≤ p ≤ N, 1 ≤ q ≤ N, p ≠ q)

이 질문은 최대 200번까지 가능하다. 베시가 가지고 있던 원래 수열을 알아냈다면, 다음과 같은 형태로 답한다.

! a b k - 공차가 a(1 ≤ a ≤ 109)이고 초항이 b(1 ≤ b ≤ 109)인 등차수열이면서 더해져있던 값은 k(1 ≤ k ≤ 109)이다.

답을 한 이후에는 다른 쿼리를 보내지 않고 프로그램을 종료해야 한다. 베시를 위해 원래 수열을 알려주자!

입력

첫 번째 줄에 베시가 가지고 있는 수열의 크기 N(4 ≤ N ≤ 500,000)이 주어진다. 두 번째 줄부터는 ? p q를 통한 질문에 대한 답이 한 줄씩 주어진다.

인터랙션

  • ? p q - 배열의 p번째 원소와 q번째 원소의 합을 물어본다. (1 ≤ p ≤ N, 1 ≤ q ≤ N, p ≠ q)
  • ! a b k - 공차가 a(1 ≤ a ≤ 109)이고 초항이 b(1 ≤ b ≤ 109)인 등차수열이면서 더해져있던 값은 k(1 ≤ k ≤ 109)이다.

예제 입력 1

4

12

10

12

16

18

16

예제 출력 1

? 1 2

? 1 3

? 1 4

? 2 3

? 2 4

? 3 4

! 2 3 4

힌트

예제 1의 경우 a=2, b=3, k=4인 경우이며 2번째 원소에 k가 더해져 있다.

예제는 인터렉티브의 동작을 돕기 위한 예시로 풀이와는 관련없으며 각 입력/출력마다 개행 문자는 정확히 하나여야 한다.

출처

University > 경북대학교 > 2021 Goricon J번

채점 및 기타 정보

  • 예제는 채점하지 않는다.