【CodeForces - 988C 】Equal Sums （思维，STLmap，STLset，tricks）

题干：

You are given kk sequences of integers. The length of the ii-th sequence equals to nini.

You have to choose exactly two sequences ii and jj (i≠ji≠j) such that you can remove exactly one element in each of them in such a way that the sum of the changed sequence ii (its length will be equal to ni−1ni−1) equals to the sum of the changed sequence jj (its length will be equal to nj−1nj−1).

Note that it's required to remove exactly one element in each of the two chosen sequences.

Assume that the sum of the empty (of the length equals 00) sequence is 00.

Input

The first line contains an integer kk (2≤k≤2⋅1052≤k≤2⋅105) — the number of sequences.

Then kk pairs of lines follow, each pair containing a sequence.

The first line in the ii-th pair contains one integer nini (1≤ni<2⋅1051≤ni<2⋅105) — the length of the ii-th sequence. The second line of the ii-th pair contains a sequence of nini integers ai,1,ai,2,…,ai,niai,1,ai,2,…,ai,ni.

The elements of sequences are integer numbers from −104−104 to 104104.

The sum of lengths of all given sequences don't exceed 2⋅1052⋅105, i.e. n1+n2+⋯+nk≤2⋅105n1+n2+⋯+nk≤2⋅105.

Output

If it is impossible to choose two sequences such that they satisfy given conditions, print "NO" (without quotes). Otherwise in the first line print "YES" (without quotes), in the second line — two integers ii, xx (1≤i≤k,1≤x≤ni1≤i≤k,1≤x≤ni), in the third line — two integers jj, yy (1≤j≤k,1≤y≤nj1≤j≤k,1≤y≤nj). It means that the sum of the elements of the ii-th sequence without the element with index xx equals to the sum of the elements of the jj-th sequence without the element with index yy.

Two chosen sequences must be distinct, i.e. i≠ji≠j. You can print them in any order.

If there are multiple possible answers, print any of them.

Examples

Input

2
5
2 3 1 3 2
6
1 1 2 2 2 1

Output

YES
2 6
1 2

Input

Output

NO

Input

4
6
2 2 2 2 2 2
5
2 2 2 2 2
3
2 2 2
5
2 2 2 2 2

Output

YES
2 2
4 1

Note

In the first example there are two sequences [2,3,1,3,2][2,3,1,3,2] and [1,1,2,2,2,1][1,1,2,2,2,1]. You can remove the second element from the first sequence to get [2,1,3,2][2,1,3,2] and you can remove the sixth element from the second sequence to get [1,1,2,2,2][1,1,2,2,2]. The sums of the both resulting sequences equal to 88, i.e. the sums are equal.

题目大意：

给你 n 个整数数列 a1,a2,…an ，每个数列的长度为Li。

请你找出两个编号不同的数列，并从这两个数列中各恰好删除一个数，使得这两个数列的和相等。

解题报告：

首先看到读入这么多数据，所以肯定不能用数组保存下来在离线处理，肯定是边读入边判断的，这种题通常是读入的同时，用数据结构记录一些信息，然后用后面读入的数去判断的。这样就很容易想到，需要记录的信息就是有哪些数字是可用的，题意都不用转化，模拟题意就行了：删去一个数求和。所以先记录下sum，然后再减去每一个数，用map记录下是第几个序列的第几个位置，方便后来查询的时候输出答案。

然后为了处理不在同一个序列中，这个问题，刚开始想把序列离散化了，后来想了想不行，，因为还需要记录当前数的位置，所以干脆直接判断原来那个数是否也是第i个序列。或者还有一种处理方法

AC代码：（156ms，改成uset则124ms）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int,int> PII;//pair<第i个序列 , 第j个字符>
const int MAX = 2e5 + 5;
int a[MAX];
map<int,PII> mp;
set<int> ss;
int main()
{
	int n,len,flag = 0;
	int ans1,ans2,ans3,ans4;
	cin>>n;
	for(int i = 1; i<=n; i++) {
		scanf("%d",&len);
		int sum = 0;
		for(int j = 1; j<=len; j++) scanf("%d",a+j),sum += a[j];
		if(flag) continue;
		for(int j = 1; j<=len; j++) {
			int tmp = sum - a[j];
			if(ss.count(tmp) && mp[tmp].fi != i) {
				flag = 1;
				ans1 = mp[tmp].fi; ans2 = mp[tmp].se;
				ans3 = i; ans4 = j;
			}
			else {
				ss.insert(tmp);
				mp[tmp] = pm(i,j);
			}
		}
		
	} 
	if(flag) {
		puts("YES");
		printf("%d %d\n%d %d\n",ans1,ans2,ans3,ans4);
	}
	else {
		puts("NO");
	}
	return 0 ;
 }

另一种处理办法：（78ms）

	for(int i = 1; i<=n; i++) {
		scanf("%d",&len);
		int sum = 0;
		for(int j = 1; j<=len; j++) scanf("%d",a+j),sum += a[j];
		if(flag) continue;
		for(int j = 1; j<=len; j++) {
			int tmp = sum - a[j];
			if(mp.count(sum - a[j])) {
				flag = 1;
				ans1 = mp[tmp].fi; ans2 = mp[tmp].se;
				ans3 = i; ans4 = j;
			}
		}
		for(int j = 1; j<=len; j++) {
			int tmp = sum - a[j];
			mp[tmp] = {i,j};
		}
	}

错误代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int,int> PII;//pair<第i个序列 , 第j个字符>
const int MAX = 2e5 + 5;
int a[MAX];
map<int,PII> mp;
set<int> ss;
int main()
{
	int n,len,flag = 0;
	int ans1,ans2,ans3,ans4;
	cin>>n;
	for(int i = 1; i<=n; i++) {
		scanf("%d",&len);
		int sum = 0;
		for(int j = 1; j<=len; j++) scanf("%d",a+j),sum += a[j];
		sort(a+1,a+len+1);
		int x = unique(a+1,a+len+1) - a - 1;
	//	printf("x = %d\n",x);
		if(flag) continue;
		for(int j = 1; j<=x; j++) {
			int tmp = sum - a[j];
			if(ss.count(tmp)) {
				flag = 1;
				ans1 = mp[tmp].fi;
				ans2 = mp[tmp].se;
				ans3 = i;
				ans4 = j;
			}
			else {
				ss.insert(tmp);
				mp[tmp] = pm(i,j);
			}
		}
		
	} 
	if(flag) {
		puts("YES");
		printf("%d %d\n%d %d\n",ans1,ans2,ans3,ans4);
	}
	else {
		puts("NO");
	}
	return 0 ;
 }