Problem G: 测谎仪1.0

Problem G: 测谎仪1.0

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 34  Solved: 18
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI最近在研究黑科技——测谎仪,但PIPI只是想好了它的功能,对功能的具体实现却一窍不通,所以它想白嫖你的idea~
测谎仪1.0功能如下:
PIPI认为机试班里的同学在寒假期间只做了两件事:(1)学习,(2)在群里当影帝“学不完了,又玩了一晚上,求求你们别学了”。
具体地,假设寒假有n天,PIPI可以询问一个同学,在第L天到第R天你学习了多少天?由于同学们都不想具体透露自己的学习天数,所以只会回答学习了奇数天还是偶数天。
现在PIPI会连续询问一个同学m个上述问题,该同学会对每一个询问进行回答。由于群里人均影帝,所以很有可能会说谎,例如回答了[1,5]学习了偶数天,[6,10]学习了奇数天,那么[1,10]就一定是学习了奇数天,如果回答偶数天就是在说谎。
测谎仪1.0会记录整个问答过程,并在结束所有询问后告诉PIPI,这位同学最早在第几个问题时开始出现矛盾。如果该同学所有回答都没有矛盾,说明他是真正的影帝——连自己都演。

Input

第一行为两个整数,n,q,分别表示寒假的天数以及询问次数 。(1<=n,q<=100000)
接下来q行,每行三个整数L,R,p,p=0表示在[L,R]学习了偶数天,p=1表示学习了奇数天。

Output

输出一个整数,表示最早出现矛盾的询问编号。如果全程无矛盾,输出"real king of the silver screen".

Sample Input

10 5
1 2 0
3 4 1
5 6 0
1 6 0
7 10 1

Sample Output

4