Interactive Board Gathering Minimum Time

Troy is playing a game with you using a (R \times C) board. There are (N) pieces numbered from (1) to (N) placed on the board. The (i)-th piece is initially positioned at ((X_i, Y_i)) (note that multiple pieces can be in the same cell).

Troy defines the score of a cell ((p,q)) as the minimum number of seconds required to move all (N) pieces to that cell. In one second, Troy can move exactly one piece to a cell that is horizontally or vertically adjacent. Thus, if a piece is at ((X_i, Y_i)), moving it to ((p,q)) requires (|X_i - p| + |Y_i - q|) moves (seconds), and the total time needed (when moving pieces one at a time) is

[ S(p,q) = \sum_{i=1}^{N} \Big(|X_i - p| + |Y_i - q|\Big)] ]

Your task is to determine the minimum score among all cells in the board, that is, to compute

[ Z = \min_{1 \le p \le R,; 1 \le q \le C} S(p,q)] ]

This is an interactive problem: Initially, you are given (R), (C) and (K) — the board dimensions and the maximum number of queries allowed. You can ask at most (K) queries of the form

? p q

to obtain the score of cell ((p,q)). Once you determine the minimum score (Z), you must output

! Z

and exit, flushing the output after each line.

Note: In this offline simulation, the input includes additional information: a hidden integer (N) and then (N) lines with the coordinates (X_i) and (Y_i) for testing purposes. In an actual interactive environment, these values would not be directly provided.

inputFormat

The input begins with a single line containing three integers (R), (C), and (K), representing the dimensions of the board and the maximum number of queries allowed. For the purpose of offline simulation, the next line contains an integer (N) (the number of pieces), followed by (N) lines, each containing two integers (X_i) and (Y_i) (the coordinates of the (i)-th piece).

outputFormat

Output a single integer (Z), the minimum score across all cells on the board. (In an interactive solution, you would output queries and finally output the answer with a preceding '!'. In this offline simulation, simply output (Z)).

sample

5 5 10
3
1 1
3 3
5 5

8