가짜 금화 찾기

준혁이는 번호가 $1$부터 $N$까지 적힌 금화 $N$개를 가지고 있다. 금화에 적힌 번호가 그 금화의 번호이다. 가지고 있는 금화 중 하나는 가짜 금화이다. 진짜 금화들의 무게는 모두 같고, 가짜 금화는 진짜 금화보다 가볍다. 준혁이는 가짜 금화를 찾기 위해 양팔 저울을 빌렸다. 양팔 저울로는 두 금화 묶음의 무게를 비교할 수 있다. 금화 묶음은 서로 다른 금화를 여러 개 모아놓은 것이며, 묶음의 크기는 $0$ 이상 $N$ 이하여야 한다. 준혁이는 양팔 저울을 최대 $5$회만 사용하려고 한다. 양팔 저울을 적절히 활용하여 가짜 금화의 번호를 찾아내자.

첫째 줄에 금화의 수 $N$이 주어진다. $(1 \le N \le 128)$

$N$을 입력받은 뒤로는 프로그램과 채점 시스템이 상호작용하며 실행된다. 프로그램은 채점 시스템에 최대 $5$번까지 질문할 수 있다. 질문은 ? A 0 B 0 형식으로 출력한다. A는 첫 번째 금화 묶음, B는 두 번째 금화 묶음이다. 각 묶음은 금화 번호를 아무 순서로 공백으로 구분하여 출력하고, 묶음의 금화를 모두 출력했음을 뜻하는 0을 출력한다. 금화 번호는 $1$과 $N$ 사이의 정수이다. 한 묶음에 같은 금화를 두 번 넣을 수 없고, 금화 하나를 두 묶음에 모두 넣을 수 없다. 채점 시스템은 다음 중 하나로 답한다. <는 금화 묶음 A가 더 가볍다는 뜻이다. >는 금화 묶음 B가 더 가볍다는 뜻이다. =는 두 묶음의 무게가 같다는 뜻이다. 답을 알아내면 ! x를 출력한다. 여기서 $x$는 가짜 금화의 번호이다. 답을 출력한 뒤에는 프로그램을 종료한다. 모든 출력 후에는 버퍼를 flush 해야 한다. C는 fflush(stdout), C++는 std::cout << std::flush, Java는 System.out.flush(), Python은 sys.stdout.flush()를 사용한다.

채점 시스템은 대화를 시작하기 전에 가짜 금화를 정해 두고, 그 금화에 따라 답한다. 대화 도중에 가짜 금화를 바꾸지 않는다.