No.814 ジジ抜き

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 42
作問者 : Lepton_sLepton_s / テスター : 37zigen37zigen
1 ProblemId : 2097 / 出題時の順位表

問題文

イルカちゃんは、動画を投稿するためにジジ抜きで遊ぼうとしています。 イルカちゃんはエコロケーションでカードに書かれている数を知ることができるため、ゲームが始まる前に「ジジ」となる数を計算しようとしています。

イルカちゃんは、$N$ 人でジジ抜きを始めようとしています。 手札は既に配られていて、対になっていた手札は全て捨てられています。
プレイヤー $i$ は手札を$K_i$枚持っていて、書かれている整数は、$\{L_i, L_i+2^{D_i}, L_i+2\times 2^{D_i}, \cdots, L_i+(K_i-1)\times 2^{D_i}\}$ となっています。
ある整数 $x$ が存在していて、「$x$ が書かれているカードを所持しているプレイヤーは奇数人で、$x$ 以外のすべての整数 $y$ について、$y$ が書かれているカードを所持しているプレイヤーは偶数人」です。 $x$ を求めてください。

補足 (読まなくても大丈夫です):
この問題のジジ抜きでは、現実のトランプとは異なり、カードに書かれている数は、$0$ 以上 $10^{18}$ 以下であり、それぞれの種類のカードは $10^{100}$ 枚ずつあります。
$x$ が書かれたカードを 1 枚だけ取り除いてから、残りのすべてのカードを $N$ 人のプレイヤーに配ります。それぞれのプレイヤー毎に配られるカードの枚数は均等である必要はありません。
それぞれのプレイヤーは手札が配られたあと、「同じ数が書かれた手札のペアを見つけて、そのペアを両方とも捨てる」という操作を、操作が行えなくなるまで繰り返します。

入力

$N$
$K_1$ $L_1$ $D_1$
$\dots$
$K_N$ $L_N$ $D_N$

$1$ $\le$ $N$ $\le$ $3 \times 10^5$
$K_i$ $\ge$ $1$
$0$ $\le$ $D_i$ $\le$ $59$
$0$ $\le$ $L_i$ $\le$ $L_i+(K_i-1)*2^{D_i}$ $\le$ $10^{18}$
全て整数
1 行目に $N$ が与えられ、
続く $N$ 行にプレイヤー $i$ の手札の情報が与えられる。
問題文に書かれている $x$ がただ一つ存在する。

出力

答えを 1 行で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
1
1 1 50
出力
1

一人しかいない場合もあります。 $\{1\}$ のカードを持っています。

サンプル2
入力
2
5 1 0
6 0 0
出力
0

1 人目は、$\{1, 2, 3, 4, 5\}$ のカードを持っていて、
2 人目は、$\{0, 1, 2, 3, 4, 5\}$ のカードを持っています。

サンプル3
入力
3
6 1 0
3 1 1
2 2 2
出力
4

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。