Training Site

# Subset Sum

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 1.0 seconds

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

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

• 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
• ### Sample Input 1

4
2 2 2 2
4 4 4 4


### Sample Output 1

2 2
4

• ### Sample Input 2

5
2 3 3 3 3
4 4 5 5 5


### Sample Output 2

2 3 3
4 4