問題文

数列S = { 1 } が渡されます。以下の2種類のクエリを合計q回実行してください。

A,i,j ： S[k] = i を満たすいずれか一つのkに対して、「S[k]を取り除き、その位置に数列V = { i,j,i } を挿入する」という操作を行う。

B,i,j ： 今までのクエリでできる可能性のある数列すべてに対して、 「S[a] = i, S[b] = jを満たし、|a-b|が最小になるときのa, bに対し、{ S[k] | (min(a, b) < k < max(a, b)) } に含まれる数の種類」を求めてから、 その中で最も小さい数を出力する。

制約

3 \leq q \leq 200000

i,jは非負整数です。

1 \leq i,j \leq q

最初の二つは必ずクエリAが渡されます。

クエリAについて、iは数列に存在している数のみ、jは数列に存在しない数のなかで、最も小さい正の整数が出現します。

クエリBについて、i,jは数列に存在している数のみ出現し、i \neq jです。

入力例 1

7
A 1 2
A 1 3
A 2 4
A 2 5
B 3 5
A 1 6
B 3 6

出力例 1

2
1

{ 1 }

これが初期状態です。以降できる可能性のある数列を列挙していきます。

• A,1,2

{ 1,2,1 }

• A,1,3

{ 1,3,1,2,1 } , { 1,2,1,3,1 }

• A,2,4

{ 1,3,1,2,4,2,1 } , { 1,2,4,2,1,3,1 }

• A,2,5

{ 1,3,1,2,5,2,4,2,1 } , { 1,3,1,2,4,2,5,2,1 } , { 1,2,5,2,4,2,1,3,1 } , { 1,2,4,2,5,2,1,3,1 }

• B,3,5

各数列に対して、最も距離の近い3と5の間にある数字の種類を求めていきます。

各数列における値は2,3,3,2なので2を出力します。

• A,1,6

{ 1,6,1,3,1,2,5,2,4,2,1 } , { 1,6,1,3,1,2,4,2,5,2,1 } , { 1,6,1,2,5,2,4,2,1,3,1 } , { 1,6,1,2,4,2,5,2,1,3,1 } , { 1,3,1,6,1,2,5,2,4,2,1 } , { 1,3,1,6,1,2,4,2,5,2,1 } , { 1,2,5,2,4,2,1,6,1,3,1 } , { 1,2,4,2,5,2,1,6,1,3,1 } , { 1,3,1,2,5,2,4,2,1,6,1 } , { 1,3,1,2,4,2,5,2,1,6,1 } , { 1,2,5,2,4,2,1,3,1,6,1 } , { 1,2,4,2,5,2,1,3,1,6,1 }

• B,3,6

各数列における値は1,1,4,4,1,1,4,4,1,1,4,1なので、1を出力します。