题目描述

纳塔悬木人部族中有 $N$ 个卷叶符印排成一排，下标从 $1$ 到 $N$，卷叶符印 $i$ 将会被第 $a_i$ 个人使用。对于编号为 $x$ 的人，使用方式是从第一个 $a_j = x$ 的位置 $j$ 开始，每次移动到下一个自己准备使用的卷叶符印，如果没有，就结束使用。

虽然用卷叶符印移动十分快速，但是同时有很多人使用就会有撞在一起的风险。

现在基尼奇想快速跑图，他可以任意选择一个非空卷叶符印序列 $b$ 使用，满足所有人的移动路线不存在严格交叉。即不存在 $i < j < k < l, a_i = a_k, a_j = a_l, a_i \neq a_j$，不存在 $i < b_j < k < b_l, a_i = a_k$，不存在 $b_i < j < b_k < l, a_j = a_l$。

求出有多少种满足限制的非空序列 $b$ 的选择方案，对 $998244353$ 取模。

由于这个问题太简单了，你还要支持 $Q$ 次修改，每次修改会在上一次修改的基础上更改位置 $u$ 的限制为：无限制、必不选、必选。每次修改后输出开头是 $L$、结尾是 $R$、满足当前限制的非空序列 $b$ 的选择方案数模 $998244353$ 的值。

输入格式

第一行一个正整数 $N$，表示序列长度。

第二行 $N$ 个数 $a_1, \dots, a_n$，表示 $a$ 序列。

第三行一个非负整数 $Q$，表示修改次数。

随后 $Q$ 行，每行四个整数 $u, t \in \{0, 1, 2\}, L, R$ 。 $t = 0$ 时表示 $u$ 没有限制；$t = 1$ 表示 $u$ 必不选；$t = 2$ 表示 $u$ 必选。

输出格式

第一行输出没有任何修改时满足限制的选择 $b$ 序列的方案对 $998244353$ 取模的结果。

接下来 $Q$ 行，每行一个整数，表示每次修改后的答案对 $998244353$ 取模的值。

样例1

样例输入

5
1 2 4 2 1
10
3 1 1 4
4 0 2 4
2 1 1 4
2 0 1 3
1 2 1 1
5 2 1 5
4 2 1 5
4 0 1 5
1 2 1 5
4 2 1 5

样例输出

24
2
1
1
0
1
4
2
4
4
2

其他样例见下发文件，每个 Subtask 都唯一对应一组其编号的下发样例。

说明/提示

保证 $1 \le L \le R \le N$ ， $1 \le a_i \le N$ ， $1 \le u \le N$ 。

各测试点的附加限制及分值如下表所示。

• 特殊性质 A： $L = 1$， $R = N$
• 特殊性质 B： $t = 0$（所有位置均无限制）