2022 年 11 月 14 日，lr580 参加 ICPC 西安站，在做 L 题写长链剖分时，将 d[v]>d[mx[u]] 写成了 d[u]>d[mx[u]]，致使本可以 2.5h 内通过的题直到比赛最后 2 分钟才 AC，浪费了半场比赛的时间，引以为戒，望周知。

自此之后，lr580 看到字母 u 和 v 都会感到非常不悦。为了让 lr580 重振，先修班成员们打算采用暴露疗法，故意展示大量的 u 和 v 给 lr580。

设先修班共有 n 名成员，每名成员均在修仙群里连续发送了若干条消息。设时间从第 1 秒开始。其中，第 i 名成员在第 [l_i,r_i] 秒内每秒都发送了一条消息，且为了不过于刺激 lr580，每条消息只包含一个 u 或一个 v。

因为多个成员同时发消息，所以在具体的某一秒内，lr580 会看到若干个 u 和 v。设在第 j 秒 lr580 共看到了 x 个 u 和 y 个 v，则 lr580 会产生 (x+y)!(x+1)(y+1) 的不悦值。请你求出在第几秒 lr580 的不悦值最大，如果有多个时间点 lr580 的不悦值一样大，请输出最早的一个时间点。

输入一行一个整数 n(1\le n\le 10^5)，代表先修班成员数。

接下来输入 n 行，第 i 行三个整数 l,r,c(1\le l\le r\le 10^9,1\le c\le 2)，代表第 i 名成员在从第 l 开始到 r 秒(含第 l,r 秒)内均发送了一条消息，若 c=1，则发送的是 u，否则发送的是 v。

输出一行一个整数 t，代表 lr580 最早到达最大不悦值是第 t 秒。