在你的帮助下，跳蚤国王终于打开了最后一间房间的大门。然而，picks 博士和他的猴子们早已通过地道逃跑了。万幸的是，因为阿姆斯特朗回旋加速喷气式阿姆斯特朗炮本身太过笨重，无法从地道中运走，所以还被静静的停放在房间的正中央。

拥有了征服世界的力量，跳蚤国王感觉非常一颗赛艇。为了试验这个传说中的武器的威力，跳蚤国王让士兵们把炮口对准空无一人的实验室开炮。

然而，事情总是没有这么顺利。片刻之后，一个士兵匆匆跑到跳蚤国王身前：“报！picks 博士给它设置了保险！但是我们根本不知道解除方法！”

经过研究，跳蚤国王发现，picks 博士所设置的保险措施可以简化为这样一个问题：

首先炮身的屏幕上显示了 $n$ 个数，接着在模 $998244353（7\times 17\times 2^{23}+1$，一个质数$）$ 意义下，给出了 $m$ 条指令，每一条指令都是下列两种之一：

1. 给所有数加上某一个数。
2. 让所有数都变成原来的逆元。（保证这时所有数的逆元都存在）

在每个指令完成之后，你要回答当前屏幕上所有数的和。

跳蚤国王思索了片刻，发现这个问题奥妙重重，于是他让你——这附近最著名的民间科学家来帮他解决这个难题。

输入格式

第一行两个正整数 $n,m$，含义如题意所述。

第二行$n$个数，表示屏幕上最初显示的 $n$ 个数。

接下来$m$行，表示 $m$ 条指令，第 $i$ 行第一个数$t_i$表示第 $i$ 个操作的类型。

若 $t_i=1$ 则接下来有一个整数 $x_i$，表示给所有数都加上 $x_i$。

若 $t_i=2$ 则表示将所有数都变成原来的逆元。

输出格式

输出$m$行，第$i$行一个整数表示第$i$条指令之后当前屏幕上每个数的和。

样例一

input

5 5
1 2 3 4 5
1 1
2
1 1
2
2

output

20
349385525
349385530
292342993
349385530

explanation

执行每个指令后的数列分别如下：

2 3 4 5 6

499122177 332748118 748683265 598946612 166374059

499122178 332748119 748683266 598946613 166374060

665496236 249561089 399297742 831870295 142606337

499122178 332748119 748683266 598946613 166374060

样例二

见样例数据下载。这组数据符合1号测试点的限制与约定。

样例三

见样例数据下载。这组数据符合3号测试点的限制与约定。

限制与约定

对于所有数据，$1\le n\le 100000$, $1\le m\le 60000$, $t_i\in \{1,2\}$，其他所有数均为区间$[1,998244352]$中的整数。

保证任何时候每个数的逆元均存在。

时间限制：$4\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载

后记

在你的帮助下，保险被成功解除，并进入了发射倒计时状态。

“5,4,3,2,1，发射！”然而，就在所有人屏息以待，想要见证它超强的破坏力的时候，预想当中的炮击声并没有出现——炮口上弹出了一大簇鲜花！

这时从旁边的地（窨）道（井）口（盖）下，跳出来了一个 picks 博士，他手上举着一支鲜花并大喊：“愚人节快乐！”

P.S. 跳蚤国的愚人节是2月28号！（一本正经的胡说八道ing）

从此跳蚤国王和 picks 博士过上了幸（没）福（羞）快（没）乐（臊）的生活（o(*////▽////*)q 好像剧情往奇怪的方向发展了）