問題
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
3 1 -1 A 10 2 1 1 8 2 1 1 12
出力例1
8 10
解説
まずP君は、速度が10以上の場合は10まで下げるチューブを用意し、このチューブで長さ1の輪っかを作る。
その後、このチューブをビー玉が速度8で突入した場合、速度はそのまま8であるため、２つ目のクエリの答えは8である。
さらに、このチューブをビー玉が速度12で突入した場合、速度は10にまで減速するので、３つ目のクエリの答えは10である。
14:08訂正：誤った文章を修正
入力例2
7 1 -1 C 1 2 1 100 1 1 1 A 10 1 1 B 12 2 1 3 1 2 1 2 1 2 1 100 1
出力例2
101 10 12 11
解説
この入力は小課題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 123412341 142857142 154978354
解説
この入力は小課題1・2の制約を満たさない。