Problem Statement

For a digit string $s$, define $f(s)$ as follows.

• Regard each of the $2^{|s|}-1$ non-empty, not necessarily contiguous, substrings of $s$ as an integer written in decimal notation; the value is the sum of these integers.

You are given a digit string $S=S_0 S_1 \ldots S_{2^n-1}$ of length $2^n$ and $Q$ queries. Process them.

• 1 x y: Replace $S_x$ with $y$.
• 2 L R X: Let $T=S_{L\oplus X}S_{(L+1) \oplus X}S_{(L+2) \oplus X} \ldots S_{R\oplus X}$, and output $f(T)$ modulo $998244353$.

Here, $\oplus$ denotes the bitwise exclusive OR.

Input

$n$
$S$
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

$1\ x\ y$

$2\ L\ R\ X$

• $1\leq n\leq 18$
• $|S|=2^n$
• $1\leq S_i\leq 9 (0\leq i\lt 2^n)$
• $1\leq Q\leq 10^5$
• $0\leq x\lt 2^n, 1\leq y\leq 9$
• $0\leq L\leq R\lt 2^n, 0\leq X\lt 2^n$
• There is at least $1$ query of the $2$nd format.
• All input values are integers.

Output

Output the answers to the queries as instructed in the problem statement, separated by newlines.

Sample

3
12345678
5
2 0 2 0
2 1 4 1
1 0 9
2 0 2 0
2 1 4 1

177
2479
1145
13127

4
6871158633369156
10
2 11 14 6
2 1 10 8
1 10 5
1 4 9
2 1 15 14
2 0 5 6
2 13 15 10
1 12 7
1 4 4
2 4 10 0

2345
974835551
235766910
1518120
944
9236338