問題文

クリスマスパーティーに向けて，あなたは整数を用意することになりました．

あなたははじめ，整数 $0$ を $10^{1000}$ 個持っています． また $2$ つの非負整数 $X,Y$ を投入すると，それらを消費して次で定まる非負整数 $Z$ を生み出す機械も所有しています：

• 任意の非負整数 $i$ に対し，$X,Y$ を $K$ 進表記したときの $K^i$ の位の数字をそれぞれ $x,y$ とすると $Z$ を $K$ 進表記したときの $K^i$ の位の数字は $(x+y)\bmod K$ である（$K$ は入力で与えられる $2$ 以上の整数）．

クエリが $Q$ 個与えられるので，与えられた順に処理してください． 各クエリでは整数 $t,x\ (1\leq t\leq 3)$ が与えられます．

• $t=1$ のとき：あなたは新たに正整数 $x$ を $10^{1000}$ 個入手する．これはこれ以降のクエリにも影響し，特にこのクエリの前後で良い数の集合は変化し得る．
• $t=2$ のとき：良い数のうち，小さい方から $x$ 番目の値を出力する．ただし良い数が $x$ 種類未満の場合は-1を出力する．
• $t=3$ のとき：良い数のうち，$x$ 以下であるものの個数を出力する．

入力

$K\ Q$
$t_1\ x_1$
$\vdots$
$t_Q\ x_Q$

• $2\leq K\leq 10^9$
• $1\leq Q\leq 10^4$
• $1\leq t_i\leq 3$
• $t_i=1$ ならば $1\leq x_i\leq 10^9$
• $t_i=2$ ならば $1\leq x_i\leq 10^{18}$
• $t_i=3$ ならば $0\leq x_i\leq 10^{18}$
• 入力は全て整数である

出力

$Q$ 個のクエリのうち $t$ が $2$ か $3$ であるものの個数を $M$ として，$M$ 行出力してください．

$j\ (1\leq j\leq M)$ 行目には，$t$ が $2$ か $3$ であるクエリのうち $j$ 番目のものの指示に従って整数を出力してください．

$M$ 行目の出力の後にも改行してください．

サンプル

2 8
1 13
1 5
1 9
2 5
3 5
1 11
2 5
3 5

8
4
4
6

17 10
1 20
2 23
3 12
1 17
2 20
3 23
1 12
2 17
3 20
2 23

-1
1
19
24
16
21
22

30 10
1 68045
1 39072
1 14466
2 846282
3 472013
2 294767
1 37755
2 50526
3 710447
3 946027

-1
7867
-1
505228
71046
81000

100000000 10
1 280891310
1 866405535
2 507843655
3 7490561978746756
1 181882853
2 869882551
3 44425977686455401
1 843088846
2 395320008
3 5837034220072028

5039218270
749056200000000
869882550
10000000000000000
395320007
5837034220072029