Hamako Online Judge

TLE
1sec

MLE
64MB

得点
100

問題

P君は今人気のおもちゃ「チューブコースター」で遊んでいる。
このおもちゃは、様々な種類のチューブを組み合わせて、その中にビー玉を入れて転がして遊ぶものである。
チューブには一つの「投入口」と「排出口」があり、ビー玉は投入口から排出口に向かって転がる。
また、チューブは伸縮性のある素材で作られており、片方の排出口ともう片方の投入口を結合させたり、
連なったチューブの両端をつなげてを一つの輪にすることもできる。
チューブはすべて長さ1で、$n$個のチューブを結合させると長さ$n$の連なったチューブになる。

チューブには3つのタイプA,B,Cがある。どのチューブもある固有の自然数$v$が定められており、入ってきたビー玉をある一定の規則に従って加速させたり減速させたりする。

タイプAのチューブは、ビー玉が入ってきた速度が$v$以上の場合は$v$になるまで減速させて排出する。
タイプBのチューブは、ビー玉が入ってきた速度が$v$以下の場合は$v$になるまで加速させて排出する。
タイプCのチューブは、速度$x$で入ってきたビー玉を速度$x+v$にして排出する。

P君は今から$Q$個のクエリを実行する。各クエリは下の2つのうちいずれかである。

クエリ1:チューブ結合クエリ
このクエリでは3つの値$R$,$type$,$v$が与えられる。
P君は$R$番目のクエリで結合させたチューブの排出口とその次の投入口の間にタイプ$type$で固有の値が$v$のチューブを挿入する。
その結果、長さ$L$の輪っかだったチューブの連なりは長さ$L+1$の輪っかになる。
ただし、一番最初のクエリのみ、ただこのチューブのみ排出口と投入口をつなぎ合わせ、長さ1の輪っかを作る。(この時$R$の値は意味を持たない)
クエリ2:速度クエリ
このクエリでは3つの値$S$,$L$,$v$が与えられる。
P君は$S$番目のクエリで結合させたチューブにビー玉が速度$v$で突入し、長さ$L$通過した直後の速度を計測する。
ただし、$L$の値によってはビー玉が輪っかの中を1周し同じチューブを２度以上通過する可能性がある。

以上の二つのクエリを処理し、クエリ2の結果を出力するプログラムを作りなさい。

入力

入力は以下のように標準入力で与えられる。

$Q$
$com_1$ $x_1$ $y_1$ $z_1$
$com_2$ $x_2$ $y_2$ $z_2$
:
$com_Q$ $x_Q$ $y_Q$ $z_Q$

ただし$x_i$,$y_i$,$z_i$は、
$com_i=1$の場合はそれぞれ$R$,$type$,$v$、
$com_i=2$の場合はそれぞれ$S$,$L$,$v$である。

出力

クエリ2の答えを改行区切りで出力せよ。

制約

すべてのテストケースは以下の制約を満たす。

・$1 \le Q \le 200000$
・$1 \le v \le 10^9$
・$1 \le L \le 10^9$
・$R$,$S$は現在のクエリより前のチューブ結合クエリの番号である。(ただし最初のクエリに限り、$R=-1$である。)
・$type$は一文字で、A,B,Cのいずれかである。
・最初のクエリはクエリ1(チューブ結合クエリ)である。

この問題には部分点が設定されている。以下の小課題について正解した場合、対応する部分点が与えられる。

小課題1(+20点)

・$1 \le L \le 100$
・$R$は直前のクエリ1の番号である

小課題2(+20点)

・$1 \le L \le 100$

入出力例

入力例1

出力例1

8
10

解説

まずP君は、速度が10以上の場合は10まで下げるチューブを用意し、このチューブで長さ1の輪っかを作る。
その後、このチューブをビー玉が速度8で突入した場合、速度はそのまま8であるため、２つ目のクエリの答えは8である。
さらに、このチューブをビー玉が速度12で突入した場合、速度は10にまで減速するので、３つ目のクエリの答えは10である。

14:08訂正：誤った文章を修正

入力例2

出力例2

解説

この入力は小課題1の制約を満たさない。

入力例3

8
1 -1 A 142857142
2 1 1000000000 1
1 1 B 123412341
2 3 999999999 123123123
1 3 C 12121212
1 5 C 32123123
2 6 555555 666666
2 5 777777 888888

出力例3

解説

この入力は小課題1・2の制約を満たさない。

006 - tubequery

問題

入力

出力

制約