Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

two pointers

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Double Knapsack

time limit per test

2.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given two multisets *A* and *B*. Each multiset has exactly *n* integers each between 1 and *n* inclusive. Multisets may contain multiple copies of the same number.

You would like to find a nonempty subset of *A* and a nonempty subset of *B* such that the sum of elements in these subsets are equal. Subsets are also multisets, i.e. they can contain elements with equal values.

If no solution exists, print - 1. Otherwise, print the indices of elements in any such subsets of *A* and *B* that have the same sum.

Input

The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 1 000 000) — the size of both multisets.

The second line contains *n* integers, denoting the elements of *A*. Each element will be between 1 and *n* inclusive.

The third line contains *n* integers, denoting the elements of *B*. Each element will be between 1 and *n* inclusive.

Output

If there is no solution, print a single integer - 1. Otherwise, your solution should be printed on four lines.

The first line should contain a single integer *k*_{a}, the size of the corresponding subset of *A*. The second line should contain *k*_{a} distinct integers, the indices of the subset of *A*.

The third line should contain a single integer *k*_{b}, the size of the corresponding subset of *B*. The fourth line should contain *k*_{b} distinct integers, the indices of the subset of *B*.

Elements in both sets are numbered from 1 to *n*. If there are multiple possible solutions, print any of them.

Examples

Input

10

10 10 10 10 10 10 10 10 10 10

10 9 8 7 6 5 4 3 2 1

Output

1

2

3

5 8 10

Input

5

4 4 3 3 3

2 2 2 2 5

Output

2

2 3

2

3 5

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2024 05:27:31 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|