Under construction

Still being built. Things may change

Hidden Rook

Time limit15sMemory limit256 MB

Summary
Find the cell of a hidden rook on an n by m board using at most 4 queries that count the cells a rectangle has under attack.
Level

Medium6 of 10

Topics
Binary search, Math
Solved
No attempts yet

Problem

Roman hid a rook on an n×mn \times m chessboard. Find its exact position.

This problem is interactive. You may ask the following question at most 4 times.

"How many cells (i,j)(i, j) with X1≤i≤X2X_1 \le i \le X_2 and Y1≤j≤Y2Y_1 \le j \le Y_2 are under the hidden rook's attack?"

A rook attacks every cell in its row and column, including its own cell.

Input

The first line contains an integer tt, the number of test cases (1≤t≤15 0001 \le t \le 15\,000).

Examples1

  1. Example 1

    Input
    2
6 6

8

2

7 5

11

4
    Expected output
    
? 1 1 3 6

? 2 2 2 3

! 2 3

? 1 1 7 5

? 1 1 1 4

! 1 4