$N$ magicians gather to socialize and share their magic at a workshop. During this workshop, they play an interesting game for one day.

The game takes place in a large conference room. In this room, there is a round table with $N$ seats. Each seat on the round table looks identical, and the magicians also look identical, so they cannot be distinguished from one another. The magicians cannot speak at all while the game is in progress.

The game proceeds in three stages, and each stage is as follows:

• In the morning, the magicians sit around the round table. At each seat, there is one empty sheet of paper and one sheet of paper with an integer between $0$ and $N-1$ written on it. The integers written on each sheet are all distinct. The magicians can see the integer written on the paper at their own seat and the paper at the seat to their right. Based on this, the magicians write an integer between $0$ and $10^9$ on the empty sheet of paper. They write this integer carefully so that only they can see it. Afterward, they fold the paper they just wrote on and place it on the seat, then take the paper with the integer that was originally on the seat and leave the conference room.
• At lunch, the magicians sit around the round table. At each seat, there is one empty sheet of paper and one sheet of paper with the number they wrote in the morning. The magicians can see the integers written on the papers at their own seat and the seats to their left and right. Based on this, the magicians write an integer between $0$ and $10^9$ on the empty sheet of paper. They write this integer carefully so that only they can see it. Afterward, they fold the paper they just wrote on and place it on the seat, then take the paper with the number they wrote in the morning and leave the conference room.
• In the evening, the magicians sit around the round table. At each seat, there is one empty sheet of paper and one sheet of paper with the number they wrote at lunch. The magicians can see the integers written on the papers at their own seat and the seats to their left and right. Based on this, the magicians write an integer between $0$ and $10^9$ on the empty sheet of paper. They write this integer carefully so that only they can see it. Afterward, they fold the paper they just wrote on and place it on the seat, then take the paper with the number they wrote at lunch and leave the conference room.

When they leave the conference room, the paper in their hand disappears due to magic, and they forget all actions taken in the conference room. The position of the seat each magician sits in is the same in the morning, at lunch, and in the evening.

The magicians do not know $N$, but they know that $10 \le N \le 100\,000$.

After the game ends, the workshop organizers unfold all the papers placed on the seats. For the magicians to win the game, the numbers written on the papers at adjacent seats on the round table must be different from each other. Also, it is desirable that only small numbers are written on the papers when the game ends (i.e., when the evening ends).

Although the magicians cannot speak while the game is in progress, they can agree on a common strategy before the game begins. You must devise a strategy on behalf of the magicians to write the smallest possible numbers on the papers.

Implementation Details

You must implement the following functions:

void init()

• This function is called exactly once, before any other functions are called.
• If there is any preprocessing or global variable initialization required for subsequent function calls, you should implement it in this function.

int morning(int my_num, int right_num)

• my_num: The integer written on the paper at the magician's seat in the morning.
• right_num: The integer written on the paper at the seat to the magician's right in the morning.
• This function must return the integer the magician will write on the empty sheet of paper in the morning. The return value of this function must be between $0$ and $10^9$.
• The return value of this function must depend only on the values of my_num and right_num.
• This function is called at most $2\,000\,000$ times.

int afternoon(int left_num, int my_num, int right_num)

• left_num: The integer written on the paper at the seat to the magician's left at lunch.
• my_num: The integer written on the paper at the magician's seat at lunch.
• right_num: The integer written on the paper at the seat to the magician's right at lunch.
• This function must return the integer the magician will write on the empty sheet of paper at lunch. The return value of this function must be between $0$ and $10^9$.
• The return value of this function must depend only on the values of left_num, my_num, and right_num.
• This function is called at most $2\,000\,000$ times.

int evening(int left_num, int my_num, int right_num)

• left_num: The integer written on the paper at the seat to the magician's left in the evening.
• my_num: The integer written on the paper at the magician's seat in the evening.
• right_num: The integer written on the paper at the seat to the magician's right in the evening.
• This function must return the integer the magician will write on the empty sheet of paper in the evening. The return value of this function must be between $0$ and $40$.
• The return value of this function must depend only on the values of left_num, my_num, and right_num.
• This function is called at most $2\,000\,000$ times.

You must not execute any input/output functions in any part of the source code you submit.

The return values of the morning, afternoon, and evening functions must depend only on the values of the given parameters. If a function returns different values when called multiple times with the same parameter values, it will be treated as an incorrect answer regardless of whether the game was won or lost.

Each test case consists of one or more independent games. There is no guarantee that the morning, afternoon, and evening functions will be called in order, but it is guaranteed that the game will proceed according to the method presented in the problem statement based on the return values of the functions.

In each test case, your program is executed twice. In the competition system, the execution time is measured as the sum of the execution times of the two program runs, and memory usage is also measured as the sum of the memory usage of the two program runs. The time limit and memory limit are based on the combined results of the two runs. The call count constraints for the morning, afternoon, and evening functions are also based on the sum of the calls in the two runs.

When submitting, you may assume that the worst-case time consumed by the grading program is within 2 seconds.

Constraints

• $10 \le N \le 100\,000$
• In each test case, the morning function is called at most $2\,000\,000$ times.
• In each test case, the afternoon function is called at most $2\,000\,000$ times.
• In each test case, the evening function is called at most $2\,000\,000$ times.

Subtasks

1. (5 points) $N \le 40$
2. (95 points) No additional constraints

If, in any test case, the magicians do not win the game based on the return values of the morning, afternoon, and evening functions, you will receive 0 points for that subtask.

Subtask 2 has partial points. For this subtask, let $m$ be the maximum value returned by the evening function plus 1. Your score for this subtask is given in the table below.

Examples

Input 1

Consider the case where $N=10$ and the numbers written on the papers at each seat in the morning are $[3, 8, 7, 0, 2, 4, 5, 9, 6, 1]$ in counter-clockwise order.

The grader calls the following functions:

morning(8, 7) = 1
morning(6, 1) = 4
morning(1, 3) = 6
morning(3, 8) = 0
morning(7, 0) = 2
morning(0, 2) = 3
morning(2, 4) = 2
morning(4, 5) = 3
morning(5, 9) = 1
morning(9, 6) = 2

In this case, the numbers written on the desk after the morning are $[0, 1, 2, 3, 2, 3, 1, 2, 4, 6]$. Based on these values, the grader calls the following functions:

afternoon(2, 3, 2) = 3
afternoon(1, 2, 3) = 2
afternoon(2, 4, 6) = 2
afternoon(3, 2, 3) = 1
afternoon(2, 3, 1) = 5
afternoon(0, 1, 2) = 4
afternoon(6, 0, 1) = 3
afternoon(3, 1, 2) = 3
afternoon(4, 6, 0) = 1
afternoon(1, 2, 4) = 0

In this case, the numbers written on the desk after lunch are $[3, 4, 2, 3, 1, 5, 3, 0, 2, 1]$. Based on these values, the grader calls the following functions:

evening(5, 3, 0) = 0
evening(4, 2, 3) = 0
evening(1, 3, 4) = 0
evening(3, 1, 5) = 0
evening(0, 2, 1) = 0
evening(2, 3, 1) = 1
evening(1, 5, 3) = 1
evening(3, 0, 2) = 1
evening(2, 1, 3) = 1
evening(3, 4, 2) = 1

In this case, the numbers written on the desk after the evening are $[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]$. Since the two numbers written at adjacent positions are always different from each other, the magicians won the game in this case. Here, $m = 2$.

It is worth observing that the order in which each function is called is independent of the actual arrangement of the round table. The grader can shuffle the function calls arbitrarily, provided that the parameters of the morning function form a fixed permutation, and the parameters of the afternoon and evening functions are the return values of the morning and afternoon functions, respectively. In addition to this method, various mechanisms are implemented to prevent the morning, afternoon, and evening functions from communicating with each other.