#!/usr/bin/env python3
#
# Testing tool for An Interactive Problem
#
# Usage:
#
#   python3 testing_tool.py [-f input_file] <program>
#
# The input file must consist of:
#  - One line with an integer n (1 <= n <= 100), the length of one of the sides of the square of lots.
#  - n lines, each with n integers v (1 <= v <= 10^9), the value of a lot (all lot values should be unique).
# If no input file is specified, it uses the sample "1.in" that is in the same directory as this testing_tool.py.
#
# You can compile and run your solution as follows.
# - You may have to replace 'python3' by just 'python'.
# - On Windows, you may have to replace '/' by '\'.
#
# If you have a Java solution that you would run using
# "java MyClass", you could invoke the testing tool with:
#
#   python3 testing_tool.py -f 1.in java MyClass
#
# If you have a Python solution that you would run using
# "python solution.py", you could invoke the testing tool with:
#
#   python3 testing_tool.py -f 1.in python solution.py
#
# If you have a C++ solution stored in a file called "sol.cpp",
# you must first compile using "g++ sol.cpp -o sol" and then
# invoke the testing tool with:
#
#   python3 testing_tool.py -f 1.in ./sol
#
# The tool is provided as-is, and you should feel free to make
# whatever alterations or augmentations you like to it.
#
# The tool attempts to detect and report common errors, but it
# is not guaranteed that a program that passes the testing tool
# will be accepted.
#
import argparse
import os
import subprocess
import sys
import traceback


def write(p, line):
    assert p.poll() is None, 'Program terminated early'
    print('Write: {}'.format(line), flush=True)
    p.stdin.write('{}\n'.format(line))
    p.stdin.flush()


def read(p):
    assert p.poll() is None, 'Program terminated early'
    line = p.stdout.readline().strip()
    assert line != '', 'Read empty line or closed output pipe. Make sure that your program started successfully.'
    print('Read: %s' % line, flush=True)
    return line


def wrong_answer(p, reason):
    sys.stdout.write('%s\n' % reason)
    p.kill()


parser = argparse.ArgumentParser(description='Testing tool for An Interactive Problem')
parser.add_argument('-f', dest='input_file', metavar='input_file', default=f"{os.path.dirname(__file__)}/1.in",
                    type=argparse.FileType("r"), help='Test file (for the syntax, check comments in testing_tool.py)')
parser.add_argument('program', nargs='+', help='Invocation of your solution')

args = parser.parse_args()

with args.input_file as f:
    lines = f.readlines()
    assert len(lines) >= 2

    n = int(lines[0])
    assert 1 <= n <= 100, 'Variable n must be between 1 and 100'

    lots = [list(map(int, line.split())) for line in lines[1:]]
    assert len(lots) == n, f'The square of lots is not square (expected {n} lines, got {len(lots)})'
    for i, line in enumerate(lots, start=2):
        assert len(line) == n, \
            f'The square of lots is not square (expected line {i} to have length {n}, got {len(line)})'
        for j, x in enumerate(line, start=1):
            assert 1 <= x <= 1e9, \
                f'The value of lot {j} on line {i} has value {x}, should be between 1 and 10^9'
    assert len(set(x for line in lots for x in line)) == n * n, 'The values of the lots should be unique'

queries = 0
queries_limit = n * n + 100

with subprocess.Popen(" ".join(args.program), shell=True, stdout=subprocess.PIPE, stdin=subprocess.PIPE,
                      universal_newlines=True) as p:
    try:
        while True:
            response = read(p)

            if response.startswith('? '):
                if queries == 50000:
                    wrong_answer(p, 'Program used too many queries, aborting')
                    break
                queries += 1
                x, y = map(int, response[2:].split())
                if 1 <= x <= n and 1 <= y <= n:
                    write(p, lots[y - 1][x - 1])
                else:
                    write(p, "ArrayIndexOutOfBoundsException")
            elif response.startswith('! '):
                answer = response[2:]
                assert answer.isnumeric(), 'Expected final guess to be a positive integer'
                answer = int(answer)
                if answer == max(max(line) for line in lots):
                    assert queries <= queries_limit, 'Program printed correct solution, but used too many queries'
                    assert p.stdout.readline() == '', 'Printed extra data after finding solution'
                    assert p.wait() == 0, 'Did not exit cleanly after finishing'
                    break
                else:
                    wrong_answer(p, 'Program printed incorrect solution')
                    break
            else:
                wrong_answer(p, 'Program gave invalid response')
                break
    except:
        traceback.print_exc()
    finally:
        sys.stdout.flush()
        sys.stderr.flush()
        sys.stdout.write(f'Used {queries} queries, limit is {queries_limit}.\nProgram exit code: {p.wait()}\n')
        sys.stdout.flush()