Data-mining huge data sets can be a painful and long lasting process if we are not aware of tiny patterns existing within those data sets.

One reputable company has recently discovered a tiny bug in their hardware video processing solution and they are trying to create software workaround. To achieve maximum performance they use their chips in pairs and all data objects in memory should have even number of references. Under certain circumstances this rule became violated and exactly one data object is referred by odd number of references. They are ready to launch product and this is the only showstopper they have. They need YOU to help them resolve this critical issue in most efficient way.

Can you help them?

Input
Input file consists from multiple data sets separated by one or more empty lines.

Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.

Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of references: X, X+Z, X+2Z, X+3Z, …, X+KZ, …(while (X+KZ)<=Y).

Your task is to data-mine input data and for each set determine weather data were corrupted, which reference is occurring odd number of times, and count that reference.

Output
For each input data set you should print to standard output new line of text with either “no corruption” (low case) or two integers separated by single space (first one is reference that occurs odd number of times and second one is count of that reference).

Sample Input

1 10 1
2 10 1

1 10 1
1 10 1

1 10 1
4 4 1
1 5 1
6 10 1

Sample Output

1 1
no corruption
4 3

题目大意

输入多组X、Y、Z的值，每组值按照公式得到一系列数 X, X+Z, X+2Z, X+3Z, …, X+KZ, …(while (X+KZ)<=Y)；
找到这些数中出现奇数次的那个数，如果找到了，输出这个数的值和出现的次数，否则输出no corruption。题目保证出现奇数次的数唯一。

例如样例1
1 10 1
2 10 1

由1 10 1得到1，2，3，4，5，6，7，8，9，10；
由2 10 1得到2，3，4，5，6，7，8，9，10；

1出现了一次，其它数都出现了两次，得到答案1 1；

例如样例3

1 10 1
4 4 1
1 5 1
6 10 1

X Y Z
1 10 1	1	2	3	4	5	6	7	8	9	10
4 4 1				4
1 5 1	1	2	3	4	5
6 10 1						6	7	8	9	10

4出现了奇数次3，其它的都出现偶数次，得到答案4 3；

解题思路：

那么它和二分有什么关系呢？
首先看样例3的图

X Y Z
1 10 1	1	2	3	4	5	6	7	8	9	10
4 4 1				4
1 5 1	1	2	3	4	5
6 10 1						6	7	8	9	10
次数	2	2	2	3	2	2	2	2	2	2
前缀和	2	4	6	9	11	13	15	17	19	21

是否可以发现前缀和在4之前都是偶数，在4之后都是奇数呢？

细想一下很容易得证。

那么我们只要二分答案，求出前缀和是奇数的最小数就可以了。

如答案区间本来在 [0,10]，
因为(0+10)/2=5的前缀和是奇数可以把区间缩减为[0,5],
因为(0+5)/2=2的前缀和是偶数可以把区间缩减为[3,5],
因为(3+5)/2=4的前缀和是奇数可以把区间缩减为[3,4],
因为(3+4)/2=3的前缀和是偶数可以把区间缩减为[4,4],
此时得到答案是4；
而出现的次数就是4的前缀和减去3的前缀和即 9 - 6 = 3次

那么前缀和怎么求呢？
如果按暴力求法时间复杂度为O(n*m),n是组数，m是区间的大小，整体的复杂度达到平方阶，运行超时。
有什么办法快速求出来呢？
容易看出每组数都是一个等差数列，那么求在数字num之前有多少个数字，可以用以下公式求出

long long sum=0;
for(int i=0;i<n;i++){
	if(m<X[i]){
		continue;
	}
	int mi=min(m,Y[i]);	//如果m比Y[i]大那么可以直接用Y[i]来求 
	sum+=(mi-X[i])/Z[i]+1;	//等差数列求个数，这个自己理解一下 
}

完整代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int X[100010],Y[100010],Z[100010],n,ma=0;
char s[200];

long long Sum(int m){	//求m的前缀和 
	long long sum=0;
	for(int i=0;i<n;i++){
		if(m<X[i]){
			continue;
		}
		int mi=min(m,Y[i]);	//如果m比Y[i]大那么可以直接用Y[i]来求 
		sum+=(mi-X[i])/Z[i]+1;	//等差数列求个数，这个自己理解一下 
	}
	return sum;
}

void Solve(){//二分解题 
	int l=0,m;
	long long r=ma;
	while(r>l){
		m=(l+r)/2;
		if(Sum(m)%2==0){
			l=m+1;
		}else{
			r=m;
		}
	}
	if(l==ma){
		cout<<"no corruption"<<endl;
	}else{
		cout<<l<<' '<<Sum(l)-Sum(l-1)<<endl;
	}
	n=0;
}

int main() {
	while(gets(s)!=NULL){
		if(strlen(s)!=0){
			sscanf(s,"%d%d%d",&X[n],&Y[n],&Z[n]);	//sscanf用法自己去学习一下 
			ma=max(ma,Y[n]+1); 
			n++;
		}else if(n){
			Solve();
		}
	}
	if(n){	//输入数据有点坑，必须考虑末处理 
		Solve();
	}
}