ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2063. Black and White

Time limit: 1.0 second
Memory limit: 64 MB
Let’s play a game. You are given a row of n balls, each ball is either black or white. Their positions in a row are numbered from 1 to n. You know the total number of balls n, but have no information about the order of their colors. You don’t even know how many white balls are there.
You are allowed to make queries v u (1 ≤ v, un). If the ball on position v is black and the ball on position u is white, then these two balls are swapped. Otherwise, nothing happens. Even if the balls are swapped, you don’t get any feedback.
After a number of queries (can be zero) you a required to make a "statement." "Statement" also consists of two positions v, u. Your goal is to choose positions, that contain two balls of the same color.
In this problem we ask you to print both queries and a "statement", that comes after them.
A single test can contain several games. Furthermore, all tests except the first one contain 99 game descriptions. In the first game n = 2, in the second — n = 3 ... in the last game n = 100.
First test is the same as the sample below.
In all other tests your program must make the right statement at least in 80 games.
Note, that we do not guarantee that the tests are random.

Input

First line contains m — number of games in the test. For every test, except for the first one, m=99.
Remaining lines contain ciphered (except for the first test) order of balls in the row. Thus we guarantee, that the tests are determined beforehand and do not depend on your strategy. Please, do not try to use this data in any way and do not try to decipher it.

Output

Output m game descriptions.
One description consists of (k+1) lines, where k — number of queries made by your program.
First k lines should contain the queries in the following format: ? v u (1 ≤ v, un, vu).
The last line should contain the "statement": ! v u (1 ≤ v, un, vu).
Total amount of lines (over all games in a test) should not exceed 5 · 105.

Sample

inputoutput
2
01
101
? 1 2
? 2 1
? 1 2
! 2 1
? 1 2
? 3 1
! 1 2

Notes

In the sample test white balls are marked as 0, black ones — as 1. Let’s examine the sample closely.
First game: 01 → 01 → 10 → 01 — we did not guess correctly.
Second game: 101 → 011 → 110 — we guessed correctly.
In this test we have guessed correctly in one game out of two.
Problem Author: Alexey Danilyuk
Problem Source: Ural Regional School Programming Contest 2015