130146 / 艾玛的梦

题号：NC25208
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

“艾玛，谢谢”
“对不起骗了你”
“不要再受伤了”
“也不要太任性了”
“要好好吃饭”
“越狱就拜托了”
“没事的，绝不要放弃”
“艾玛，再见”

诺曼走了。夜里艾玛在床上辗转反侧。疲惫的她最终在悲伤与心痛之中睡去。她做了一个很奇怪的梦……

在梦中，有 n 个小岛，分别标号为 1 至 n 。岛与岛之间有若干条有向边连接，每条边 $i \rightarrow j$ 有一个权值 $v_{i \rightarrow j}$ 。这 n 个小岛构成了一张 n 个点的图。而这个图满足每个点只向自己连有一条权值为 1 的边。当 n=3 时，如下图所示。

每座小岛还有一个梦幻值 $d_i$ 。每时每刻小岛上的梦幻值都在变化。具体来说，在任意一个时刻 $t \; (t \in \mathbb{R})$ ，对任意一个小岛 $i \; (1 \le i \le n)$ ，其梦幻值 $d_i$ 的增长速度恰好等于 $\displaystyle \sum_{边 i \rightarrow j 存在于图中} d_j \times v_{i \rightarrow j}$ （单位梦幻值 / 单位时间）。可以发现当给定图以及每个点在 0 时刻的梦幻值时，每个点的梦幻值都可以表示为一个关于时间 t 的函数。这个函数的定义域为实数集 $\mathbb{R}$ 。而这些函数可以用多项式来表示。

接下去我们需要定义图的复合。

两张边带权的有向图的复合依然是一张边带权的有向图。复合要求两张图均为边带权的有向图，均没有重边，同时点数相同，且均标号 1 至 n 。复合图 A 和图 B 的过程如下：
1. 如果图 A 中有边 $u \rightarrow v$ ，权值为 $p_1$ ；同时图 B 中有边 $v \rightarrow w$ ，权值为 $p_2$ ，那么在新图 C 中添加边 $u \rightarrow w$ ，权值设为 $p_1 \times p_2$ 。
2. 第 1 步后所得的图 C 中含有重边。于是对于 C 中的任意两个有序点对 u, v ，将 C 中所有边 $u \rightarrow v$ 的权值相加，得到权值和 q 。若 $q \not=0$ ，则在新图 D 中添加一条 $u \rightarrow v$ 权值为 q 的边。
3. 所得的图 D 即为图 A 和图 B 复合的结果。可以发现，图 D 依然是一个有 n 个点的，无重边的，边带权的有向图。我们将图的复合表示为 $\otimes$ 运算。故上述过程有 $A \otimes B = D$ 。可以发现图的复合不满足交换律。
例如：
与复合得到

继续我们的故事。

艾玛继续做着她的梦。突然，一股不明力量扯开了这 n 座平静的小岛，将这一幅图，扯开成了两幅图 $G_1$ 和 $G_2$ 。所产生的两张图满足：

1. 这两张图之间没有边连接。

2. 两图的复合和原来的图相同。即 $G_1 \otimes G_2$ 等于原图。这里两张图相同当且仅当两张图点数相同，并且对于所有的有序点对 u, v ，都满足：要么边 $u \rightarrow v$ 在两张图中都不存在，要么边 $u \rightarrow v$ 同时存在于两张图中，并且权值相同。

3. 图 $G_1$ 中每个点设有一个权值 $w_i$ （是一个属性）。对于每个有序点对 $u, v \; (u \not= v)$ ，在图 $G_1$ 中都存在一条边 $u \rightarrow v$ ，其权值为 $w_u$ 。图 $G_1$ 中不存在其它边。根据这一点可以唯一确定图 $G_1$ 的形态。之后就可以根据第 2 点唯一确定图 $G_2$ 的形态。

当 n=3 ， $w_1=2, w_2=3, w_3=-1$ 时，图 $G_1$ 长这样：

紧接着，这股力量凭空捏造了另一张图 $G_3$ 。这张图满足：

1. 有 n 个点，标号为 1 至 n 。是一张无重边的边带权的有向图。

2. 对于点 $i \; (1 \le i \le n)$ ，存在边 $i \rightarrow i$ ，权值为 k 。

3. 对于点 $i \; (1 \le i < n)$ ，存在边 $i \rightarrow i + 1$ ，权值为 1 。

4. 除了上述两种边之外，没有其它边。

当 n=3, k=4 时，这张图长这样：

然后这股力量又将这三张图复合为了一张图 G'。具体来说， $G' = G_1 \otimes G_3 \otimes G_2$ （请注意这里的顺序！）。这时 G' 不一定再和原来的图相同了，它可能会变得复杂起来。
而此时图 G' 上每个点的梦幻值依然满足之前提到的性质。需要注意的是，得到新图 G' 后，每个点上的梦幻值会相应作出改变，以满足之前的性质。
好奇的艾玛在梦里想要知道，在给定点数 n 、图 $G_1$ 中每个点的权值 $w_i$ 、值 k 以及图 G' 中每个点 0 时刻的梦幻值时，某个点上梦幻值关于时间的函数是什么。请将这个函数以多项式的形式输出，模 $x^{n+1}$ ，各项系数模 998244353 。

不过，梦总是无法预测的。所以，梦中会发生一些改变。可能的改变有：

· 1 x y ：将图 $G_1$ 中点 x 的权值 $w_x$ 修改为 y 。保证 $1 \le x \le n, 1 \le y \le 10^8$ 。

· 2 x ：将值 k 修改为 x 。保证 $0 \le x \le 10^8$ 。

· 3 x y ：将图 G' 中点 x 在 0 时刻的梦幻值修改为 y 。保证 $1 \le x \le n, 0 \le y \le 10^8$ 。

· 4 x ：询问此时图 G' 中点 x 上梦幻值关于时间的函数。保证 $1 \le x \le n$ 。

注：操作具有后效性；任一操作完成后，每个点上的梦幻值依然会相应做出改变以满足性质。

艾玛沉浸在痛苦中无法自拔，所以只能请你来回答这个问题了。

输入描述:

第一行包含一个正整数 n ，表示点数。
第二行包含 n 个正整数  ，表示图  中点的权值。
第三行包含一个整数 k ，意义如题面所述。
第四行包含 n 个整数  ，表示图 G' 中每个点在 0 时刻的梦幻值。
第五行包含一个正整数 q ，表示操作次数。
接下去 q 行，每行按题面中所述格式描述一个操作。

输出描述:

输出前 n 行每行 n+1 个整数。第 i 行表示初始未修改时图 G' 中第 i 个点的函数在模  、各项系数模 998244353 意义下的答案。从低次到高次依次输出，共 n+1 个数。同一行中的相邻两个数用一个空格隔开。
接下去若干行，每行对应一次 4 操作的答案。每行共 n+1 个数，格式同上。

示例1

输入

复制

输出

复制

1 83187031 582309207 207967574
1 831870296 415935149 166374060
1 4 623902725 790276782
1 55458024 526851192 665496239
5 705109114 205986935 685302673
1 51 677380396 71304082

备注:



保证 1 操作的个数不超过 300 。


数据保证一定有解。