This is an interactive problem.

Big M is a person full of advantages, and he particularly dislikes matrices. Now he has the opportunity to communicate with a god, but the god is very fond of matrices.

There is a matrix in front of him. The god does not tell him what elements are in the matrix, but the god tells him that the elements in the matrix are all distinct and comparable. The god also tells him that the matrix is "monotonic," meaning that if the element at row $i$ and column $j$ is $a_{i, j}$, then for $i_1 < i_2$, $a_{i_1, j} < a_{i_2, j}$, and for $j_1 < j_2$, $a_{i, j_1} < a_{i, j_2}$. The god has also chosen an element $x$ that can be compared with all elements in the matrix, such that this element is different from all elements in the matrix. Big M does not know the value of $x$.

The god allows Big M to perform two types of queries: the first type allows Big M to query the relative order of two matrix elements, and the second type allows Big M to query the relative order of a matrix element and $x$.

Big M asks you to help him perform the queries and report to the god: how many elements in the matrix are smaller than $x$.

This problem uses code completion. You need to implement an int main(int n) function within the namespace query in the provided sample interactive program search.cpp. This function accepts the matrix size $n$ as a parameter, calls ask1 and ask2 to perform queries, and returns the calculated answer.

Note:

1. You should not call or access any functions or variables other than those within namespace query, the function ask1, and the function ask2 in any way. You should not attempt to read/output any information or try to change the behavior of the grader in any way. To ensure this, the code used for actual evaluation will differ from the provided code, and we will perform checks; submissions that do not comply will be awarded 0 points.
2. You only need to submit the code inside namespace query.
3. The interactive library used during evaluation uses no more than 340MB of memory, meaning you can use at least 256MB of memory.
4. The running time of the interactive library during evaluation will not exceed 2s provided the number of queries is within the limits, meaning your program has at least 2s of running time.
5. The interactive library used during evaluation is "essentially different" from the provided sample interactive library (in terms of input/output, correctness checking, etc.), but you do not need to worry about these.

The function you need to implement is:

int main(int n);

The parameter $n$ represents the matrix size, and the return value should be the answer to the problem (how many elements in the matrix are smaller than $x$).

The functions you can call are:

string ask1(int x1, int y1, int x2, int y2);

This corresponds to the first type of query. The parameters $(x_1, y_1)$ and $(x_2, y_2)$ represent two elements of the matrix. When calling, you must ensure $1 \leq x_1, y_1, x_2, y_2 \leq n$ and $(x_1, y_1) \neq (x_2, y_2)$. This function returns the string "<" or ">" (without quotes), representing the relative order of the two elements.

string ask2(int x, int y);

This corresponds to the second type of query. The parameters $(x, y)$ represent an element of the matrix. When calling, you must ensure $1 \leq x, y \leq n$. This function returns the string "<" or ">", representing the relative order of this element and $x$.

Input

The sample interactive program search.cpp reads from standard input in the following format:

The first line contains three integers $n, x, ans$, representing $n$, $x$, and the answer, respectively.

The next $n$ lines each contain $n$ integers representing the matrix.

It is guaranteed that the matrix elements and $x$ are all distinct and that the matrix satisfies the monotonicity constraints.

Output

The sample interactive program search.cpp prints the following information to standard output: whether your answer is correct, the number of calls to ask1, the number of calls to ask2, and other error information (if any).

Examples

Input 1

3 7 6
1 2 4
3 6 8
5 9 10

Output 1

(Depends on the interaction)

Constraints

Subtask 1 (10 points): $1 \leq n \leq 10$, allowed at most $64n$ calls to ask1 and at most $45$ calls to ask2.

Subtask 2 (20 points): $1 \leq n \leq 2\,000$, allowed at most $256n$ calls to ask1 and at most $45$ calls to ask2.

Subtask 3 (20 points): $1 \leq n \leq 2\,000$, allowed at most $192n$ calls to ask1 and at most $38$ calls to ask2.

Subtask 4 (25 points): $1 \leq n \leq 2\,000$, allowed at most $128n$ calls to ask1 and at most $36$ calls to ask2.

Subtask 5 (25 points): $1 \leq n \leq 2\,000$, allowed at most $64n$ calls to ask1 and at most $34$ calls to ask2.

For $100\%$ of the data, $1 \leq n \leq 2\,000$.

The problem guarantees that the matrix elements and the queried number are generated randomly in some way.

The 5 subtasks have $20, 30, 30, 30, 30$ test cases respectively; please evaluate the accuracy of your program.

When evaluating on QOJ, there are only two subtasks, where subtask 2 is worth 90 points and contains 120 test cases. Your score will depend on the number of times you call ask1 and ask2.