34199번 - 패스 구입 인터랙티브

문제

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

국렬이는 평소 즐겨 하던 D 게임의 패스 아이템을 구입하려 한다. 패스 아이템은 다음과 같이 두 종류가 있다:

• 1번 패스의 가격은 $P_1$이고, 유효 기한이 $T_1$일이다.
• 2번 패스의 가격은 $P_2$이고, 유효 기한이 $T_2$일이다.

국렬이는 한 번에 하나의 패스 아이템만 구입할 수 있으며, 현재 사용 중인 패스의 유효 기간이 끝나기 전에는 다른 패스를 새로 구입할 수 없다. 국렬이는 게임이 서비스를 종료하는 날까지, 하루도 빠짐없이 패스 효과가 이어지길 바란다. D 게임은 최소 1ドル$일 이상 서비스를 운영하며 최대 100ドル\ 000$일 내에 서비스가 종료된다. 다만, 국렬이는 정확히 언제 게임이 서비스를 종료하는지는 알지 못한다.

국렬이는 돈이 많지 않아서 패스 구입 비용을 최대한 줄이려 한다. 하지만 서비스 종료 일자가 언제인지 알 수 없기에, 언제 서비스가 종료되더라도 패스 효과가 끊기지 않으면서 항상 최소 비용만으로 패스를 구입하는 완벽한 전략은 존재하지 않는다. 대신, 최소 비용의 두 배를 넘지 않는 선에서 패스를 구입할 수 있는 전략은 있다.

계산이 어려운 국렬이를 대신해, 당신이 구매 전략을 세워주자!

입력

첫째 줄에 네 개의 양의 정수 $P_1,ドル $T_1,ドル $P_2,ドル $T_2$가 공백으로 구분되어 주어진다. $(1 \le P_1 \le P_2 \le 10^9;\ 1\le T_1, T_2 \le 1\ 000)$

2번 패스의 가격은 항상 1번 패스보다 비싸거나 같지만, 유효 기간은 더 짧을 수 있음에 유의하라.

출력

인터랙션은 처음에 당신이 1번 또는 2번 패스를 구입하는 것부터 시작된다.

채점 시스템과의 인터랙션은 다음과 같은 방식으로 이루어진다.

• ? 1: 국렬이가 1번 패스 아이템을 구입한다.
• ? 2: 국렬이가 2번 패스 아이템을 구입한다.
• !: 서비스가 종료되었음을 알았을 때 인터랙션을 종료한다.

?를 통해 패스를 구입 시 인터랙터는 다음을 반환한다. 반환을 받은 후에는 다시 위와 같은 방식으로 인터랙션을 해야한다.

• $D$ : $D$는 양의 정수이며, 이는 $D$일째에 새로운 패스를 구입해야 함을 의미한다. 즉, $D$는 (지금까지 구입한 패스 유효 기한의 합 + 1)을 의미한다.
• $-1$: 게임이 서비스를 종료하였음을 의미한다.

게임 서비스가 종료되지 않았음에도 !를 출력하거나 최소 비용의 2배를 초과하는 비용을 사용 시 틀렸습니다를 받는다.

각 질문을 출력한 후에는 반드시 표준 출력 버퍼를 flush해 주어야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다. 질문에 대한 답을 입력받지 않으면 런타임 에러를 받게 된다.

언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다. 기타 언어의 경우 각 언어의 문서를 참조하라.

• C : fflush(stdout)
• C++ : std::cout << std::flush
• Java : System.out.flush()
• Python : sys.stdout.flush()

제한

힌트