問題文

空の列 AA が与えられます。

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

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

制約

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

入力

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

Q
query1
query2
...
queryQ

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

1 x
2

出力

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

入出力例

入力例1
8
1 2
1 6
1 24
1 12
2
2
2
2
出力例1
2
6
12
12

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

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

55 番目のクエリでは、(2,6,24,12)(2, 6, 24, 12) の最大公約数である 22 を出力します。
66 番目のクエリでは、(6,24,12)(6, 24, 12) の最大公約数である 66 を出力します。
77 番目のクエリでは、(24,12)(24, 12) の最大公約数である 1212 を出力します。
88 番目のクエリでは、(12)(12) の最大公約数である 1212 を出力します。

入力例2
12
1 4
1 12
1 88
2
1 16
1 28
2
2
1 90
2
1 77
2
出力例2
4
4
4
2
1

提出


Go (1.21)