Person in charge

• 035966_L3

Background

You are an ordinary pilot from Country U. On this morning, you received a critical mission: fly to Country J and bomb City G.

You will always remember this extraordinary date: August 6, 5491 AD.

You successfully completed the mission. However, your superior issued an additional order: conduct another bombing raid on the outskirts of City G to completely destroy Country J's military headquarters.

Problem Description

The outskirts of City G form an $8\times8$ grid. Country J's military headquarters occupies a $3\times3$ area (guaranteed to be entirely within the $8\times8$ grid), with the center square being the commander's office. Destroying this office will eliminate the entire headquarters. Unfortunately, the headquarters is underground, so you cannot determine its location.

Your plane carries $7$ bombs remaining, each capable of bombing one grid square. After bombing, you will receive one of three responses:

1. The bombed square is neither the commander's office nor part of the headquarters
2. The bombed square is part of the headquarters but not the commander's office
3. The bombed square is the commander's office (mission accomplished)

Design an algorithm to determine bombing coordinates that guarantees mission success.

Interaction Protocol

This is an interactive problem.

After each output line, use fflush(stdout); / cout.flush(); / cout << endl; to flush the buffer.

Before interaction begins, read a positive integer $1 \le T \le 36$ indicating test cases.

For each test case, conduct $1 \sim 7$ rounds of interaction:

1. Output two integers $1 \le x,y \le 8$ representing bombing coordinates $(x,y)$
2. Read an integer $0 \le z \le 2$ indicating the result:
   • $0$: Miss (not part of headquarters)
   • $1$: Hit (part of headquarters but not office)
   • $2$: Direct hit (commander's office destroyed)
3. The test case ends when:
   • either $z=2$ is received (success),
   • or $7$ bombing attempts are made.

Successfully completing all test cases results in AC.

Sample

3

0

0

0

1

2

0

1

1

2

2

1 1

4 4

7 7

4 7

3 7

1 1

4 1

6 1

5 2

6 6

Hint

Below is an annotated sample interaction where:

• [I] represents input your program receives
• [O] represents output your program sends
• [N] represents explanatory notes (not part of actual interaction)

[I] 3
[N] Interaction started. There are 3 testcases in this test.
[N] Testcase #1 started.
[N] Round #1:
[O] 1 1
[I] 0
[N] (1, 1) Exploded: Missed.
[N] Round #2:
[O] 4 4
[I] 0
[N] (4, 4) Exploded: Missed.
[N] Round #3:
[O] 7 7
[I] 0
[N] (7, 7) Exploded: Missed.
[N] Round #4:
[O] 4 7
[I] 1
[N] (4, 7) Exploded: Hit headquarter.
[N] Round #5:
[O] 3 7
[I] 2
[N] (3, 7) Exploded: Destroyed commander's office.
[N] Testcase #1 passed: Mission completed using 5 bombs.
[N] Testcase #2 started.
[N] Round #1:
[O] 1 1
[I] 0
[N] (1, 1) Exploded: Missed.
[N] Round #2:
[O] 4 1
[I] 1
[N] (4, 1) Exploded: Hit headquarter.
[N] Round #3:
[O] 6 1
[I] 1
[N] (6, 1) Exploded: Hit headquarter.
[N] Round #4:
[O] 5 2
[I] 2
[N] (5, 2) Exploded: Destroyed commander's office.
[N] Testcase #2 passed: Mission completed using 4 bombs.
[N] Testcase #3 started.
[N] Round #1:
[O] 6 6
[I] 2
[N] (6, 6) Exploded: Destroyed commander's office.
[N] Testcase #3 passed: Mission completed using 1 bomb.
[N] Interaction ended. All testcases passed. You got an accepted!