JOI, who has been selected as a representative of Japan for the International Olympiad in Informatics, has been given the following task by the Chairperson K of the Japanese Committee for the International Olympiad in Informatics to improve her information processing skills.

Chairperson K wrote a string $S$ in a notebook without JOI knowing. $S$ consists of four types of characters: ‘<’, ‘>’, ‘[’, and ‘]’. Chairperson K gave JOI a printout containing the details of the task and the length of $S$.

JOI's task is to determine whether $S$ is a "good string". Here, a good string is defined as follows:

• The empty string (i.e., a string of length 0) is a good string.
• If $x$ is a good string, then $$ (i.e., the string $x$ enclosed in angle brackets $<>$) is a good string.
• If $x$ is a good string, then $[x]$ (i.e., the string $x$ enclosed in square brackets $[]$) is a good string.
• If $x$ and $y$ are good strings, then $xy$ (i.e., the string formed by concatenating $x$ and $y$ in this order) is a good string.
• Only strings defined as good strings by the above rules are good strings.

For example, "<>[]" and "[<>]<>" are good strings, while "><" and "[<]>" are not.

JOI can call Chairperson K at most once every day at noon. In the call, by specifying an integer $I$, she can ask Chairperson K to tell her the $I$-th character of $S$.

Now, a major constraint is imposed on JOI: "You must not take notes for this task." JOI goes to bed at 22:00 every night and wakes up at 6:00 in the morning, but she can only remember 22 bits of information while sleeping. More precisely, she must memorize one integer between $0$ and $2^{22} - 1$ before going to bed, and the next day she must work on the task based only on the memorized integer. However, since the length of $S$ is written on the printout, she can refer to it at any time.

Instead of memorizing an integer before going to bed, JOI may answer to Chairperson K via email whether $S$ is a good string. In this case, the task ends, and it is judged whether the answer is correct or incorrect. However, if she does not send an email within 15,000 days from the start of the task, it is judged as incorrect.

Task

Implement JOI's strategy and create a program that can correctly solve the above task.

Implementation Details

You must write a single program that implements JOI's strategy. The program must include Memory_lib.h.

The program must implement the following function:

• int Memory(int N, int M)

This function corresponds to JOI's action for the day, given the length of $S$ and the memorized integer.

• The argument N is the length $N$ of the string $S$.
• The argument M is the integer $M$ representing the content memorized before going to bed the previous day. Note that at the start of the task, it is treated as if $M = 0$ is memorized.
• Within this function, you can call the function Get at most once, as described below.
• This function must return an integer between $0$ and $2^{22} - 1$, or $-1$, or $-2$. If a value outside this range is returned, it will be judged as incorrect [1].
  • If the return value is an integer between $0$ and $2^{22} - 1$, it means that this value is to be memorized before going to bed.
  • If the return value is $-1$, it means answering via email that "S is a good string".
  • If the return value is $-2$, it means answering via email that "S is not a good string".
• This function is expected to behave depending only on the values of the arguments N, M, and the return value of the called Get. Also, in the actual grading program, this function is called $2^{22} \times 4$ times. For details, refer to "Grading Procedure" and "Important Notes".

You can call the following function in your program:

• char Get(int I)

This function can be called at most once per call of Memory. If it is called two or more times, it will be judged as incorrect [2].

The argument I must be an integer $I$ satisfying $1 \le I \le N$. If this is not satisfied, it will be judged as incorrect [3].

The return value of this function represents the $I$-th character of the string $S$.

Grading Procedure

Each input data for grading consists of multiple test cases, and the length of the string $S$ is the same value $N$ in all of them.

Grading is performed according to the following procedure. If it is judged as incorrect, the program is terminated at that point.

(1) Examine the behavior of Memory for all cases of the values of arguments N, M, and the return value of the called Get. That is, for each integer $M$ satisfying $0 \le M \le 2^{22} - 1$, perform the following: (i) For each character $c \in \{‘<’, ‘>’, ‘[’, ‘]’\}$, perform the following: Call Memory with argument N as $N$ and argument M as $M$. At this time, if Get is called, the character $c$ is returned. Let the value returned by Memory be $m(M, c)$. (ii) In the four calls to Memory in (i), whether to call Get or not must be the same. Furthermore, if Get is called, the same integer $I$ must be called as argument $I$ in all four cases, and if Get is not called, the same value must be returned in all four cases. If these are not satisfied, it will be judged as incorrect [4]. Let the argument $I$ when Get is called be $i(M)$ (however, if Get is not called, let $i(M) = 1$).

(2) For the string $S$ in each test case, simulate the task described in the problem statement. That is, perform the following: (i) Let $M = 0$. (ii) Repeat the following: (a) Let $c$ be the $i(M)$-th character of $S$. (b) Replace $M$ with $m(M, c)$. (c) If $M = -1$ or $M = -2$, proceed to (iii). (d) If this item is reached 15,000 times, it will be judged as incorrect [5]. (iii) If any of the following cases occur, it will be judged as incorrect [6]: $S$ is a good string, but $M = -2$. $S$ is not a good string, but $M = -1$.

(3) It is judged as correct.

Important Notes

• The execution time measurement and memory usage measurement are based on step (1) in "Grading Procedure". Note that Memory is called $2^{22} \times 4$ times in step (1).
• Note that in all $2^{22} \times 4$ calls to Memory in step (1), you must not cause incorrect [1], [2], [3], or a runtime error.

Constraints

All input data satisfy the following conditions:

• $1 \le (\text{length of } S) \le 100$.
• Each character of $S$ is one of ‘<’, ‘>’, ‘[’, ‘]’.

Subtasks

Subtask 1 [10 points] * $(\text{length of } S) \le 8$ is satisfied.

Subtask 2 [10 points] * $(\text{length of } S) \le 14$ is satisfied.

Subtask 3 [5 points] * $(\text{length of } S) \le 24$ is satisfied.

Subtask 4 [5 points] * $(\text{length of } S) \le 30$ is satisfied.

Subtask 5 [10 points] * Each character of $S$ is one of ‘<’, ‘>’.

Subtask 6 [60 points] * There are no additional constraints.

Examples

Input 1

4 1
<>[]

Output 1

-1

Note

The following is an example of the interaction between grader-simple and the program.

Memory(4, 0) -> Get(1) -> '<' -> 2015
Memory(4, 2015) -> Get(3) -> '[' -> 3
Memory(4, 3) -> Get(2) -> '>' -> 23
Memory(4, 23) -> Get(4) -> ']' -> 4194303
Memory(4, 4194303) -> Get(3) -> '[' -> -1

When the above interaction occurs, grader-simple outputs -1.