006 - VeryManyApples

問題

あなたは屋台で$10^{(10^{100})}$個のリンゴ飴の販売をしていました。
$i$個目のリンゴ飴は$i$円します。
流石に値段の格差がありすぎると思ったあなたはいくらかのリンゴ飴を値引きしようと思いました。

これからあなたは$Q$個のクエリを処理します。
$i$個目のクエリでは$L_i,R_i,A_i$という3つの整数が与えられ、「$L_i≦x≦x+A_i≦R_i$をみたすすべての$x$について順番に、$x$番目のリンゴ飴の値段を$S$、$x+A_i$番目のリンゴ飴の値段を$T$としたとき、$max(S,T)$円のリンゴ飴をすべて$min(S,T)$円に値下げする。($S=T$の場合は何もしない)」という動作を行います。

最初、客が選べる値段の種類は$1$円から$10^{(10^{100})}$円の$10^{(10^{100})}$通りです。すべてのクエリを処理した後、客が選べる値段の種類を$T$としたとき、$10^{(10^{100})}-T$を出力しなさい。

入力

$Q$
$L_1\ R_1\ A_1$
:
$L_Q\ R_Q\ A_Q$

１行目には一つの整数$Q$($1≦Q≦50000$)が与えられます。
つづく$Q$行のうち$i$行目には、3つの整数$L_i,R_i,A_i$($1≦L_i≦R_i≦10^{18},0≦A_i≦100$)が与えられます。

出力

答えを一行に出力しなさい。

入出力例

入力例1

3
1 7 3
6 8 2
5 6 1

出力例1

6

最初、リンゴ飴の値段は順番に
{1,2,3,4,5,6,7,8,9,10,11,...}
である。最初のクエリを処理した後、リンゴ飴の値段は
{1,2,3,1,2,3,1,8,9,10,11,...}
となる。2つ目のクエリによって、
{1,2,3,1,2,3,1,3,9,10,11,...}
3つ目によって、
{1,2,2,1,2,2,1,2,9,10,11,...}
となる。最終的に客が選べる値段の種類は$10^{(10^{100})}-6$のため、答えは6である。

入力例2

2
1 10 1
100 1000 1

出力例2

909

すべての10円以下のリンゴ飴は1円に値下げされ、100円以上1000円以下のリンゴ飴は100円に値下げされる。

入力例3

2
1 1000000000000000000 8
1 1000000000000000000 6

出力例3

999999999999999998

$10^{18}$円以下のリンゴ飴はすべて1円または2円に値下げされる。