Subset Sum

You are given an integer $N$, and two sequences $a$ and $b$, each containing $N$ integers between $1$ and $N$.

Your task is to find non-empty subsets of $a$ and $b$, such that the sum of elements in each subset are equal.

In all test cases, it is guaranteed that a valid solution exists.

Input

The first line contains a single integer, $N$.

The second line contains $N$ space separated integers, $a_1, a_2, \dots, a_N$.

The third line contains $N$ space separated integers, $b_1, b_2, \dots, b_N$.

Output

The first line should contain up to $N$ space-separated integers in any order, corresponding to a subset of $a$.

The second line should contain up to $N$ space-separated integers in any order, corresponding to a subset of $b$.

If there are multiple solutions, you may print any of them.

Constraints

For all subtasks:

• $1 \le N \le 100\,000$
• $1 \le a_i, b_i \le N$

Subtasks

• Subtask 1 (20%): $1 \le N \le 8$
• Subtask 2 (15%): $a_i = a_{i+1}$ and $b_i = b_{i+1}$ for all $i$
• Subtask 3 (30%): All $a_i$ and $b_i$ are powers of $2$
• Subtask 4 (35%): No further restrictions apply