Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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

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
  • 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