#joi2016hoe. [joi2016ho_e]断層 (Geologic Fault)
[joi2016ho_e]断層 (Geologic Fault)
遠い昔,IOI 文明という高度な文明が栄えていた.しかし,火山の噴火により,この高度な文明はついに滅んでしまった.IOI 文明は直線状の河川に沿って繁栄しており,IOI 文明が滅んだとき,その地表面は平らであった.IOI 文明の跡地は座標平面の 軸と見なすことができる. 軸は高さ方向を表す.すなわち,座標平面において,直線 は地表を,領域 は地上を,領域 は地下を表す.また,IOI 文明が滅んだとき, 年前 () の地層は,直線 の位置にあった.
IOI 文明が滅んだ後,IOI 文明の跡地では 回の地殻変動が起きた. 回目 () の地殻変動は,位置 ,方向 ,変動の量 で表される. は または である. 回目の地殻変動は以下のように起きる.
- 地層の移動が次のように起きる.
- のとき,断層が点 を通る傾き の直線に沿って造られ,この直線より上の領域にある地層が,直線に沿って高さ だけ移動する.すなわち,この直線より上の点 は,点 に移動する.
- のとき,断層が点 を通る傾き の直線に沿って造られ,この直線より上の領域にある地層が,直線に沿って高さ だけ移動する.すなわち,この直線より上の点 は,点 に移動する.
- そのすぐ後に,領域 の地層が風化によってすべて消える.
時は変わり現代,考古学者の JOI 博士は IOI 文明の遺跡を発掘することにした.JOI 博士はどの位置の地表の地層が,IOI 文明が滅ぶ何年前の地層であるかを知りたい.どのような地殻変動が起きたかは分かっている.あなたの仕事は,JOI 博士にかわって, を満たす各整数 について,点 と点 の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを求めることである.
課題
IOI 文明の跡地に起きたの情報が与えられたとき,すべての整数 () に対し,点 と点 の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを出力せよ.
入力
標準入力から以下の入力を読み込め.
- 行目には, 個の整数 が空白を区切りとして書かれている.これは,答えを求める地点の数が ,地殻変動の回数が であることを表す.
- 続く 行のうちの 行目 () には, 個の整数 が空白を区切りとして書かれている.これは, 回目の地殻変動の位置が ,方向が ,変動の量が であることを表す.
出力
出力は 行からなる.標準出力の 行目 () には,点 と点 の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを表す整数を出力せよ.
制限
すべての入力データは以下の条件を満たす.
- .
- .
- $\-1\\,000\\,000\\,000 \\leqq X_i \\leqq 1\\,000\\,000\\,000$ ().
- ().
- ().
小課題
小課題 1 [18 点]
以下の条件を満たす.
- .
- .
- ().
- ().
小課題 2 [16 点]
以下の条件を満たす.
- .
- .
小課題 3 [66 点]
追加の制限はない.
入力例 1
出力例 1
この入力例は,以下の図に対応する.
入力例 2
出力例 2
この入力例は,小課題 の制約を満たす.