This is an interactive problem.

Ruozhi is an alchemist. After a long dream, he finally discovered the method for crafting one-way portals.

Ruozhi has crafted $N$ portals, numbered $0 \sim N-1$. Initially, the level of portal $i$ is $a_i$. If a portal has level $l$, entering it will lead you to exit from portal $l$, and at that moment, you will be standing behind portal $l$. Therefore, the levels of all portals are non-negative integers less than $N$.

Ruozhi can use his abilities to change the levels of the portals. However, breaking the balance is a taboo for alchemists. If Ruozhi wants to increase the level of a portal by $1$, he must first enter that portal, turn around to decrease the level of the portal in front of him by $1$, and then walk back to portal $x$ to increase its level by $1$. Conversely, if Ruozhi wants to decrease the level of a portal by $1$, he must first enter that portal, turn around to increase the level of the portal in front of him by $1$, and then walk back to portal $x$ to decrease its level by $1$.

Of course, to ensure that the levels of all portals remain non-negative integers less than $N$, all addition and subtraction operations here are performed modulo $N$.

For example, if there are $3$ portals with levels $1, 2, 1$ in order of their indices, and Ruozhi wants to increase the level of portal $1$ (which is currently $2$), he must enter portal $1$, then turn around. He will be facing portal $2$ (because entering portal $1$ leads him to exit from portal $2$). After decreasing the level of portal $2$, he increases the level of portal $1$. Consequently, the levels of the three portals become $1, 0, 0$ in order of their indices.

Today is Ruozhi's birthday, and he wants to change the level of portal $i$ to $b_i$ for every $i$. However, he does not know how to achieve his goal, so could you help him? If you help him, he will treat you to a meal.

Task Introduction

You need to implement a function adjust to help Ruozhi adjust the portal levels.

• adjust(N, a, b)
  • N is the number of portals, and a and b are the two arrays described in the problem.

In each test case, the interactor will call the adjust function exactly once.

You can call the functions Inc and Dec to perform modifications.

• Inc(x)

  • Increases the level of portal $x$ by $1$. Of course, you must follow the rules above: pass through the portal, turn around, and decrease the level of the portal in front of you by $1$.

• Dec(x)

  • Decreases the level of portal $x$ by $1$. Of course, you must follow the rules above: pass through the portal, turn around, and increase the level of the portal in front of you by $1$.

Again, note that all addition and subtraction operations are performed modulo $N$.

Note that the functions Inc and Dec will not change the contents of the parameter a within the adjust function.

Implementation Details

This problem only supports C++.

Your source code must include the header file portals.h.

You need to implement the following function:

int adjust(int N, int* a, int* b)

For arrays a and b, you can only access indices in the range $0 \sim N-1$; otherwise, the program's behavior is not guaranteed.

If it is impossible to achieve Ruozhi's goal, the function should return $-1$; otherwise, it should return $0$.

The interface for Inc is as follows:

void Inc(int x)

The interface for Dec is as follows:

void Dec(int x)

How to Test Your Program

You need to compile your program using the following command in the problem directory:

g++ -o guess grader.cpp guess.cpp

The executable will read data from standard input in the following format:

The first line contains a positive integer $N$, where $N \leq 1000$.

The second line contains $N$ integers, $a_0, a_1, \dots, a_{N-1}$, where $0 \le a_i < N$.

The third line contains $N$ integers, $b_0, b_1, \dots, b_{N-1}$, where $0 \le b_i < N$.

After reading the input, the interactor will call the adjust function.

Then, the interactor will output the following information to standard output:

The first line contains $N$ integers, $a'_0, a'_1, \dots, a'_{N-1}$, representing the level of each portal after your operations.

The second line is in the format cnt tot, where cnt is the number of indices $i$ such that $a'_i = b_i$, and tot is equal to $N$.

The third line is the return value of the adjust function.

Examples

Input 1

3
1 2 1
1 0 0

Output 1

1 0 0
3 3
0

Note 1

This example is the one described in the problem statement. This is the output obtained using the grader and sample source code provided in the problem directory.

Scoring

For each test case, the interactor first compares the return value of the adjust function with the correct return value. If the correct return value is $0$ and you do not return $0$, the score for this test case is $0$.

If the return value of adjust is $-1$ and the correct return value is also $-1$, the score for this test case is $1$.

If the return value of adjust is $0$ and the correct return value is also $0$, let $cnt = \sum_{i=0}^{N-1}[a'_i = b_i]$, then your score is $\max\{S, 0.1\}$, where $S$ is a function of $cnt$ and $N$. The calculation of $S$ varies by subtask.

If the return value of adjust is $0$ and the correct return value is $-1$, the score for this test case is $S$.

The specific calculation method for $S$ in each subtask is given in the "Constraints" section.

The score for a subtask is equal to the minimum score of all test cases in that subtask multiplied by the total points for that subtask.

Constraints

It is guaranteed that there are no more than $20$ test cases in a subtask.

Subtask 1 (20 points): $N \leq 8, S = \left(\frac{cnt}{N}\right)^{2.3}$.

Subtask 2 (20 points): $N \leq 25, S = 0.9^{N-cnt}$.

Subtask 3 (20 points): $N \leq 200, S = \max\{0.85^{N-cnt}, 0.75 \times \left(\frac{cnt}{N}\right)^{1.5}\}$.

Subtask 4 (40 points): $N \leq 1000, S = \left(\frac{cnt}{N}\right)^3$.

The time and memory limits given in the problem apply to the combined usage of your code and the interactor.

We guarantee that at least $2 \times 10^7$ calls to Inc or Dec can be performed within 1s, and the remaining part of the interactor runs in no more than 0.1s, meaning the actual time available to the contestant is at least 0.9s.

We guarantee that for any valid data and calls within the limits, the memory used by any version of the interactor (including those provided to contestants and those used for final evaluation) will not exceed 12MB, meaning the actual memory available to the contestant is at least 500MB.