Problem Description

There is a $2 \times n$ table filled without repetition with the numbers $1 \sim 2 \times n$. You can perform several operations, each operation involving selecting a $2 \times 2$ square area and rotating it $180\degree$.

Given the current state and the target state of the table, determine if it is possible to reach the target state. If possible, what is the minimum number of operations required?

Input Format

The first line contains a positive integer $n$.

The next two lines, each containing $n$ positive integers, represent the current state of the table.

The following two lines, each containing $n$ positive integers, represent the target state of the table.

Output Format

If there is no solution, output one line dldsgay!!1.

Otherwise, output an integer representing the minimum number of operations.

Sample Input and Output

Sample Input #1

1
1
2
2
1

Sample Output #1

dldsgay!!1

Sample Input #2

2
1 2
3 4
4 3
2 1

Sample Output #2

1

Sample Input #3

2
1 2
3 4
1 2
4 3

Sample Output #3

dldsgay!!1

Sample Input #4

3
1 6 2
4 3 5
2 4 3
5 1 6

Sample Output #4

2

Notes

Subtasks

This problem uses batched testing.

For $100\%$ of the data: $1 \leq n \leq 10^6$.

There are a total of $10$ subtasks, each with its own score and constraints:

• Subtask $1$ ($1$ point): Guaranteed output is dldsgay!!1.
• Subtask $2$ ($1$ point): Guaranteed that the target state is the same as the current state.
• Subtask $3$ ($4$ points): $n=1$.
• Subtask $4$ ($5$ points): $n=2$.
• Subtask $5$ ($14$ points): $1 \leq n \leq 20$.
• Subtask $6$ ($19$ points): $1 \leq n \leq 100$.
• Subtask $7$ ($19$ points): $1 \leq n \leq 1000$.
• Subtask $8$ ($8$ points): Guaranteed that the first row of the target state is $1 \sim n$ and the second row is $n + 1 \sim 2n$.
• Subtask $9$ ($10$ points): Guaranteed that there is no unsolvable case.
• Subtask $10$ ($19$ points): No special restrictions.

见题面 Input 部分

见题面 Output 部分