問題文

空の列 $A$ が与えられます。

$Q$ 個のクエリが与えられるので、順番に処理してください。
クエリは次の $2$ 種類のいずれかです。

• 1 x : $A$ の最後尾に $x$ を追加する。
• 2 : $A$ の要素の最大公約数を出力し、その後に最初の要素を削除する。このクエリが与えられるとき、$A$ は空でないことが保証される。

制約

• $1 \leq Q \leq 10^5$
• $1 \leq x \leq 10^9$
• クエリ 2 が与えられるとき、$A$ は空でない。
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

Q
query1
query2
...
queryQ

$i \: (1 \leq i \leq Q)$ 番目の query $i$ では、まずクエリの種類 $t_i$ $(1, 2$ のいずれか$)$ が与えられ、$t_i = 1$ のときは追加で $x$ が与えられる。
すなわち、各クエリは以下に示す $2$ つの形式のいずれかが与えられる。

1 x

2

出力

$t_i = 2$ を満たすクエリの個数を $q$ として、$q$ 行出力せよ。
$j \: (1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

入出力例

8
1 2
1 6
1 24
1 12
2
2
2
2

2
6
12
12

入力例 $1$ において、$i$ 番目のクエリを処理した後の $A$ の状態を $i$ 行目に示すと以下のようになります。

• $(2)$
• $(2, 6)$
• $(2, 6, 24)$
• $(2, 6, 24, 12)$
• $(6, 24, 12)$
• $(24, 12)$
• $(12)$
• $()$

$5$ 番目のクエリでは、$(2, 6, 24, 12)$ の最大公約数である $2$ を出力します。
$6$ 番目のクエリでは、$(6, 24, 12)$ の最大公約数である $6$ を出力します。
$7$ 番目のクエリでは、$(24, 12)$ の最大公約数である $12$ を出力します。
$8$ 番目のクエリでは、$(12)$ の最大公約数である $12$ を出力します。

12
1 4
1 12
1 88
2
1 16
1 28
2
2
1 90
2
1 77
2

4
4
4
2
1