该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P1040 The nflsM Tokens (HARD)

Problem Background

See problem P1039 The nflsM Tokens (EASY) (Fib3 Queue 2).

Problem Statement

Define $F^{m}_{n}=F^{m}_{n-1}+F^m_{n-2}+\cdots+F^{m}_{n-m}\ (n\ge m),F^m_0=0,F^m_1=F^m_2=\cdots=F^m_{m-1}=1$ with $m\ge2$.

Originally we have $m=2$.

Given $T$ queries. Each query is formatted like these below:

• 1 x means to make $m$ equal $x$.
• 2 n means to ask you to print $F^m_n$ modulo $998244353$ with the current $m$.

Input

$t$
$\text{Query}_1$
$\text{Query}_2$
$\text{Query}_3$
$\ \ \ \ \ \vdots$
$\text{Query}_t$

For each query, it is formatted by two integers; more see problem statement.

Output

For each query with the $2^{nd}$ operation, print the answer.

Constraints

• $1 \le t \le 100$.
• For each query with the $1^{st}$ operation, $2 \le x \le 30$.
• For each query with the $2^{nd}$ operation:
  • For $20\%$ test cases: $1 \le n \le 10^5$.
  • For all test cases: $1 \le n \le 10^{9}$.

Samples

Input 1

7
2 10
1 3
2 5
1 10
2 11
1 2
2 5

Output 1

55
7
18
5