J. 二进制与、平方和
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

请你维护一个长度为 n 的非负整数序列 a1, a2, ..., an，支持以下两种操作：

  1. 第一种操作会将序列 al, al + 1, ..., ar 中的每个元素，修改为各自和 x 的"二进制与"（Bitwise binary AND）的值，其中 l, r, x 在每次操作时会给定；
  2. 第二种操作会询问序列 al, al + 1, ..., ar 中所有元素的平方和模 998 244 353 的值，即 模 998 244 353，其中 l, r 在每次操作时会给定。

总共有 q 次操作，请你在维护序列的过程中，输出第二种操作所询问的答案。注意需要取模。

Input

第一行，一个整数 n (1 ≤ n ≤ 3 × 105)，表示序列的长度。

第二行，共 n 个整数 ai (0 ≤ ai < 224)，表示序列。

第三行，一个整数 q (1 ≤ q ≤ 3 × 105)，表示询问的数量。

接下来 q 行，每行表示一个操作，输入有两种格式：

  1. 第一种操作的格式为 "1 l r x"，表示将序列中编号在区间 [l, r] 的所有元素，修改为和 x 二进制与操作后的值，其中 1 ≤ l ≤ r ≤ n, 0 ≤ x < 224；
  2. 第二种操作的格式为 "2 l r"，表示询问序列中编号在区间 [l, r] 的所有元素的平方和，模 998 244 353 的值，其中 1 ≤ l ≤ r ≤ n。

数据保证至少有一个第二种操作，即保证至少询问一次答案。

Output

每当遇到第二种操作时，输出询问的答案。注意需要取模。

Examples
Input
3
13 31 28
4
2 1 3
1 3 3 25
1 1 2 18
2 2 3
Output
1914
900
Input
5
9 11 12 5 1
7
2 1 3
1 3 3 0
1 1 3 9
1 4 5 13
2 1 3
1 4 5 14
2 1 5
Output
346
162
178
Input
4
16777215 16777215 16777215 16777214
4
2 2 2
1 1 4 16777214
2 1 4
2 3 4
Output
981185168
795789897
897017125
Note

"二进制与"（Bitwise binary AND）结果的第 i 个二进制位为 1，当且仅当两个操作数的第 i 位都为 1。