Problem1415--PIPI种庄稼Ⅱ

1415: PIPI种庄稼Ⅱ

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

Description

PIPI看淡了世间的纷争,选择继续种田退隐江湖。
已知PIPI有n块田,编号为1-n。每次PIPI会选择一个区间[L,R],在该区间内所有的田地种上作物W。
经过m次这样的操作后,PIPI想知道几号田地的作物种类最多?

Input

第一行输入正整数n和m,其中n,m<=10^5。
接下来m行,每行三个正整数L,R,W(L<=R<=n,W<=10^9),其中W表示作物种类的编号,若W不同,表示种类不同。

Output

输出作物种类最多的田地编号,若答案不唯一,输出编号最小的那个。

Sample Input

1 1
1 1 1

Sample Output

1

Source/Category