注意

制約に対して実行時間および使用メモリ制限が厳しく設定されています． 想定解を実装した提出（40 ~ 60 lines / 1,000 ~ 1,300 bytes 程度）の実行時間，実行時使用メモリ量は以下の通りです．

• C++：1,145 ms / 7,720 KB
• C#(csc)：1,757 ms / 28,800 KB
• PyPy：1,723 ms / 77,800 KB

問題文

整数列 $M,R$ があり，はじめどちらも空です． $Q$ 個のクエリを処理してください．クエリは以下のいずれかです．

• 追加クエリ 1 m r：$M$ の末尾に $m$ を，$R$ の末尾に $r$ をそれぞれ追加する．
• 削除クエリ 2 k：$M,R$ それぞれの末尾 $k$ 個の要素を削除する．
• 出力クエリ 3 m： $M=(M_1,M_2,\dots,M_n),R=(R_1,R_2,\dots,R_n)$ とする． 非負整数 $X$ で $i=1,2,\dots,n$ に対し $X\bmod M_i=R_i$ を満たすものが存在するとき，そのような $X$ として最小のものを $m$ で割った余りを出力する（特に $M,R$ が空ならば $0$ を出力する）． またそのような $X$ が存在しないとき $-1$ を出力する．

入力

$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\ \vdots$
$\mathrm{query}_Q$

• $Q$ は $1$ 以上 $10^4$ 以下の整数．
• $\mathrm{query}_i$ は $i$ 番目のクエリを表し，以下のいずれかの形式である．

1 $m$ $r$

• $m,r$ は $0\leq r\lt m\leq 10^9$ を満たす整数．

2 $k$

• $k$ は正整数．
• このクエリが与えられたとき，$M,R$ の長さは共に $k$ 以上である．

3 $m$

• $m$ は $1$ 以上 $10^9$ 以下の整数．

出力

各クエリへの答えを改行区切りで出力してください．

サンプル

10
1 3 2
1 5 3
1 7 2
3 100
1 10 7
3 1
2 2
1 10 8
1 21 5
3 1225

23
-1
68

21
3 843957008
1 472606293 274537750
3 64772011
1 193496841 55561237
1 451893048 386182462
3 55362928
2 2
1 809555949 430585126
1 332038764 226085506
1 382738349 129580124
3 539680759
1 231823672 217838911
1 306480274 85596938
3 179792542
2 3
1 331955943 153336259
1 252027932 57148750
1 804119517 717446500
3 413073477
3 401206962
3 163951831

0
15449706
42497622
132215773
-1
299588848
78602104
132982172