004 - 生存環境シミュレート

時間制限 2 秒 / メモリ制限 256 MB / 得点 7 / x 0 /

TLE
2sec
MLE
256MB
得点
7

課題

入力を修正、入出力例を追加しました。

2016年12月31日,21:00、水槽の基準点から右にaメートル地点からbメートル地点に浮かぶプランクトンの死骸を採集した。

~プランクトンについてわかったこと~

プランクトンの死骸は、1メートル*1メートル*1メートルの立方体の形をしている。
プランクトンの死骸を調査したところ、このプランクトンは死亡した際にプランクトンが死亡した場所の塩分を体内に蓄積し、それ以外の塩分は蓄積されない。
また、今回採集したプランクトンの死骸は全てが2016年12月31日の9:00に死亡したことも判明した。
プランクトンの死骸は死後その場にとどまり続けるが、水流の影響でのみ位置が動く。
また、この死骸はもろく、水槽の蓋にぶつかってしまうと壊れてしまう。
この水槽の蓋は水面ぎりぎりにあるため、死骸が少しでも水面から出ると蓋にぶつかってしまう。


たとえばこのときにパワー2の左斜め上水流が来たら




フタにぶつかってその死骸は壊れてしまう。




だがしかし死骸同士がぶつかっても壊れることはない。その場合、水流の向きに沿って死骸が押し出されていく感じとなる。もちろんこのとき押し出された死骸が蓋にぶつかれば、その死骸は壊れる。


たとえばこのときにパワー２の左斜め上水流が来たら




黄色は押し出されてフタにぶつかってその死骸は壊れてしまうが、緑はフタにぶつかっていないのでそのまま残る。






~さらなる調査~

あなたはこのプランクトンはどこで死亡したのかを知る手がかりとしてプランクトンの死骸の塩分濃度を調べた。
しかし、プランクトンの死骸からは塩分濃度を測ることは出来なかった。
そこであなたは、プランクトンの死骸が浮いていた水槽で、2016年12月31日の9:00〜21:00に起きた水流のデータを調べ、それを元にプランクトンの塩分濃度をシミュレートすることにした。

~水流について~

水流は45度に右斜め上、45度に左斜め上、下から上の三種類の水流がある。
・右斜め上の水流は、点(w,h)を通る傾き1の直線に沿って造られ，この直線以上の領域にあるプランクトンの死骸が，直線に沿って高さpiだけ右上に移動する．すなわち，この直線より上の点(x,y)は，点(x+pi,y+pi)に移動する．


・右斜め上の水流は、点(w,h)を通る傾き-1の直線に沿って造られ，この直線以上の領域にあるプランクトンの死骸が，直線に沿って高さpiだけ左上に移動する．すなわち，この直線より上の点(x,y)は，点(x-pi,y+pi)に移動する．


・下から上の水流は、点(w,h)を通る傾き0の直線に沿って造られ，この直線上の領域にあるプランクトンの死骸が，直線に沿って高さpiだけ真上に移動する．すなわち，この直線上の点(x,y)は，点(x,y+pi)に移動する．


また、塩分濃度がh未満の場所が、水流の影響を受ける。
すなわち塩分濃度がh以上の場所は水流の影響を一切受けない。

下から上の場合は、上に１ｍプランクトンの死骸が移動する距離が増える。
パワーが0の時は全く移動せず、パワーが負の値の場合や、整数ではない場合は無い物とする。

~水槽について~


この水槽は水面の塩分濃度が0で、水面から1m深くなるたびに塩分濃度が1増す。
水槽には横幅にも深さにも限界はなく、ひたすら水が無限に広がっている。
また、水槽のある部分に旗が立てられており、これを基準点としている。
上に書いてある基準点とは、このことである。

以上が今回わかったことである。これを元にシミュレートし、a~a+1メートル地点から順に、b-1~bメートル地点までのプランクトンの塩分濃度を調べてほしい。

入力

Q h
a b
w1 p1 d1
w2 p2 d2
.
.
.
wQ pQ dQ

1 行目に水流のデータの数Qと水流の影響を受けない場所hが与えられる。

2 行目にプランクトンの死骸を採集した場所を示す整数 a b が与えられる。

続くQ行の内のi行目(1≦i≦Q)には、3個の整数wi,pi,diが空白区切りで書かれる。
これは、i回目の水流の始点がwi,方向がdi(1の時は右斜め上、2の時は上、3の時は左斜め上),変動の量がpiであることを表す。
iが小さい順に水流は発生している。また、水流が同時に複数存在する状況はない。

出力

出力はb-a行からなる。標準出力のi行目(1≦i≦b-a)には、a+i-1メートルからa+iメートルで採集されたプランクトンの死骸の塩分濃度を表す整数を出力せよ。
また、場合によってはプランクトンの死亡位置が存在しない場合もある。そのときはその部分は-1と出力すること。

制約

全ての入出力ケースについて以下を満たす。

  • a≦b
  • 0 ≦ a,b ≦ 100000
  • 0 ≦ b-a ≦ 3000
  • 1 ≦ Q ≦ 3000
  • 1 ≦ h ≦ 108
  • -100000 ≦ wi ≦ 100000(1≦i≦Q)
  • 1 ≦ pi ≦ 100000(1≦i≦Q)

入出力例

入力例1

2 10
0 10
2 3 1
11 2 3

出力例1

3
5
5
5
5
5
5
5
2
2

解説

図の塩分濃度が0のところに塗られているマスが死骸が採集された場所で、それと同じ色が各色が死亡した時にいた位置である。

まず一つ目の水流はこの向きに流れる。

この水流は黒い波線のエリアにある死骸を移動させる。つまり今回は赤く囲った場所の死骸を移動させる。

これらはこの位置に移動する。
移動した結果がこれである。

二つ目の水流はこの向きに流れる。

この水流は黒い波線のエリアにある死骸を移動させる。つまり今回は赤く囲った場所の死骸を移動させる。

これらはこの位置に移動する。
移動した結果がこれである。採集時の状態と一致していることがわかる。

入力例2

3 10
-5 5
-2 9 2
4 10 2
5 10 2

出力例2

0
0
0
9
0
0
0
0
0
-1

解説

１つめの水流は-2メートルから-1メートルの間を下から上に水流が流れている。
このとき、塩分濃度９，-2メートルから-1メートルの間に死骸があった場合その死骸は水流に流れて9メートル上に上昇する。
２つめの水流は4メートルから5メートルの間を下から上に水流が流れている。
このとき、塩分濃度9，4メートルから5メートルの間に死骸があった場合その死骸は水流に流れて10メートル上に上昇する。しかし、これではフタにぶつかって死骸が壊れてしまう。
また、塩分濃度10,4メートルから5メートルの間に死骸があったとしてもそこは水流の影響を受けないのでその死骸が水面にあがってくる可能性はない。
３つめの水流は5メートルから6メートルの間を下から上に水流が流れている。 この水流は採集した死骸とは関係のない水流である。
出力の0のところは水面で死亡して水流の影響を全く受けなかった場合、塩分濃度0の死骸がそこに浮かんでいる。ということになる。
-1のところは、水流の影響でどの位置でプランクトンが死亡しても最終的にそこにたどり着けないため、-1となっている。

入力例3

>3 10
-5 5
-2 9 2
4 10 2
5 10 2

出力例3

6
6
6
6
6
6
9
6
6
6
6
6
6
6