CodeForces - 618F Double Knapsack

Discription

You 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

Input

5
4 4 3 3 3
2 2 2 2 5

Output

2
2 3
2
3 5

    一道神构造。
    设sa[]为a[]的前缀和，sb[]为b的前缀和，对于每个0<=i<=n,我们找到一个最大的使得sb[j]<=sa[i]的j，这样每个sa[i]-sb[j]都是[0,n-1]的整数了(因为如果sa[i]-sb[j]>=n的话，j可以继续后移(a[],b[]中元素都<=n))
    所以至少会有一对 i和i'满足 sa[i]-sb[j] == sa[i']-sb[j']，直接输出就行了。。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1000005;

ll a[maxn],b[maxn];

int px[maxn],py[maxn],n;

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

void W(int x){ if(x>=10) W(x/10); putchar(x%10+'0');}

int main(){

	n=read();

	for(int i=1;i<=n;i++) a[i]=read(),a[i]+=a[i-1];

	for(int i=1;i<=n;i++) b[i]=read(),b[i]+=b[i-1];

	for(int i=0,j=0,D;i<=n;i++){

		for(;j<n&&b[j+1]<=a[i];j++);

		D=a[i]-b[j];

		if(px[D]){

			W(i-px[D]+1),puts("");

			for(int o=px[D];o<=i;o++) W(o),putchar(' ');

			puts(""),W(j-py[D]+1),puts("");

			for(int o=py[D];o<=j;o++) W(o),putchar(' ');

			return 0;

		}

		px[D]=i+1,py[D]=j+1;

	}

	return 0;

}

巴特西

CodeForces - 618F Double Knapsack

最新文章

热门文章