問題文

ルエラちゃんは、ボールの鉛直投げ上げ運動の実験を行いました。この実験では、投げ上げるボールを途中で増やしながら、指定された時刻でのボールの変位の最大値を順に実験レポートに書くことになっていました。しかし、ルエラちゃんは実験結果を残していなかったため、予想で実験レポートを書くことにしました。

ルエラちゃんの住んでいる星の重力加速度は $2a$ で与えられます。ボールの鉛直投げ上げ運動の変位は時刻の $2$ 次関数で表され、 $2$ 次の係数が $-a$ であるとします。すなわち、ボールが投げ上げられて戻るまでの間の時刻 $t$ でのボールの変位 $h$ は、ある定数 $b,c$ を用いて $h=-at^2+bt+c$ と表せます。

このとき、以下の $Q$ 個のクエリ $\{q_i\}$ に答えてください。

• 1 s t　実験するボールを追加する。ボールは時刻 $s$ のとき変位 $0$ から投げ上げられ、時刻 $t$ で変位 $0$ に戻ってくる。
• 2 t　ボールの時刻 $t$ での変位の最大値を出力して改行する。ただし、時刻 $t$ で鉛直投げ上げ運動をしているボールがない場合、0を出力して改行する。

なお、この問題の制約下で、出力する値が全て整数となることが証明できます。

また、クエリ $2$ の形式で与えられる $t$ はクエリの順に従った広義単調増加であるものとします。すなわち $q_i\ (1\leq i\leq Q)$ が「 $2\ t_i$ 」でクエリ $q_j\ (1\leq j\leq Q)$ が「 $2\ t_j$ 」であるとき、 $i\lt j$ ならば $t_i\leq t_j$ が成立します。

入力

$a$
$Q$
$q_1$
$q_2$
$q_3$
$\vdots$
$q_Q$

クエリ $q_i\ (1\leq i\leq Q)$ は以下のどちらかの形式で与えられます。

$1\ s\ t$

$2\ t$

• 入力は全て整数
• $1\leq a\leq 100$
• $2\leq Q\leq 10^5$
• $0\leq s\leq 10^8$
• $0\leq t\leq 10^8$
• 1 s tの形式のクエリについて、 $s\lt t$
• 2 tの形式のクエリで与えられる $t$ は広義単調増加
• クエリ $q_1$ は、1 s tの形式
• 2 tの形式のクエリが存在する

出力

2 tの形式のそれぞれのクエリについて、時刻 $t$ での変位の最大値または $0$ を出力して改行してください。

サンプル

5
7
1 0 2
2 1
1 0 4
2 1
2 3
1 1 6
2 4

5
15
15
30

5
3
1 0 2
1 4 6
2 3

0

3
10
1 2 4
2 1
2 3
2 4
1 0 5
2 4
2 6
1 1 9
2 6
2 8

0
3
0
12
0
45
21