背景

SBW在MC中砍树
SBW会经过多个树林
在每个树林中砍一棵树
(为保护环境，SBW不想多砍)
树林中有桦树和橡树
SBW想知道自己砍一定棵数橡树的方案数
SBW要求所有方案数对998244353取模

描述

给出树林数\(N\)和
各个树林中橡树的棵数\(X_i\)和桦树的棵数\(H_i\)
询问砍0至N棵橡树的方案数
但树数会变M次
变了之后SBW不想考虑那么多
你只需回答砍\(\left \lfloor \frac{N}{2} \right \rfloor\)棵的方案数

输入

第一行两个正整数N,M
第二行N个数为\(H_i\)
第三行N个数为\(X_i\)
接下来M行每行三个正整数
p h x 表示树林p的桦树数变为h，橡树数变为x

输出

第一行N+1个数
为未变化时砍各棵数橡树的方案数
接下来M行，每行一个数
为变化后砍\(\left \lfloor \frac{N}{2} \right \rfloor\)棵橡树的方案数

样例

输入

4 2
1 1 1 1
1 1 1 1
1 2 4
2 1 2

输出

1 4 6 4 1
18
26

范围

40% N<=3000 M<=5 \(H_i\),\(X_i\),h,x<=100
70% N<=\(10^5\) M<=10
100% 1<=N<=\(2\ast 10^5\) 0<=M<=20 1<=\(H_i\),\(X_i\),h,x<=\(10^8\)
有50% M=0

限制

3000ms
128M