问题1188--难题

1188: 难题

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 512 MB

题目描述

“游戏一时爽,训练……”

“啊不,身后有余忘缩手,眼前无路想回头……”

沉迷游戏的Miaoyao显然没有在这个寒假里好好学习算法,于是当他回到TJU ICPC集训队时,看着强大的lhl322出的题目,欲哭无泪。

lhl322有n个正整数,依次编号为a1到an。但是,lhl322并不想直接告诉Miaoyao它们的值,而是每次选择一个区间[l,r],告诉Miaoyao这个区间内正整数的异或和,即al xor al+1 xor ... xor ar的值x。其中,xor表示按位异或运算,即对于两个数的每个二进制位分别运算,在每个二进制位上,有0 xor 0=0, 0 xor 1=1, 1 xor 0=1, 1 xor 1=0。在C++中,你可以使用运算符“^”或者关键字xor来表示异或运算。

但是,由于lhl322想要考验Miaoyao,因此他所给出的信息可能是前后矛盾的。lhl322要求Miaoyao指出第一次矛盾是出现在哪一条信息上。

输入

第一行两个整数n,m,分别表示整数个数和信息条数。

接下来m行,每行三个整数l,r,x,表示al xor al+1 xor ... xor ar的值为x。

输出

仅一行,若信息存在矛盾,则输出第一次出现矛盾时的信息编号,否则输出“Correct!”。

样例输入 Copy

4 3
1 2 0
3 4 1
1 4 2 

样例输出 Copy

3

提示

1<=n<=2*10

1<=m<=200000

1<=l<=r<=n

0<=x<231

来源/分类