该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

特别地，对于 PyPy3 语言，时限 6000ms，但仍不建议使用 PyPy3 语言实现此题。

题目背景

一只羊发现，法阵上的某些区域会随着时间推移逐渐褪色。

不同的位置能够接受的颜色集合并不完全相同，而且这种限制还会不断发生变化。

题目描述

现在，一只羊有一个被分成了 $M$ 个区域的环形法阵，区域按顺时针方向依次编号为 $1,2,\dots,M$。

共有 $N$ 种颜色，颜色编号为 $1,2,\dots,N$。对于每个区域，只允许使用某个给定的颜色集合中的颜色进行染色。

为了方便描述，一只羊预先给出了 $S$ 种颜色集合模板，模板编号为 $1,2,\dots,S$。每个模板对应一个允许使用的颜色集合。

初始时，第 $i$ 个区域绑定了一个模板 $a_i$，表示这个区域只能使用模板 $a_i$ 中出现过的颜色。

如果两个区域有长度非零的公共边界，则称它们相邻。于是：

• 对于任意 $1\le i<M$，区域 $i$ 与区域 $i+1$ 相邻；

• 区域 $M$ 与区域 $1$ 也相邻。

要求任意两个相邻区域的颜色均不相同。

接下来会有 $Q$ 次修改操作。每次操作会将某一个区域绑定的模板修改为另一个模板。每次修改后，你都需要求出当前合法染色方案数。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

保证每个模板中给出的颜色编号两两不同，且都在 $1$ 到 $N$ 之间。

输入格式

第一行四个整数 $N,M,S,Q$，分别表示颜色种数、区域个数、模板个数和修改次数。

接下来 $S$ 行，第 $i$ 行先给出一个整数 $c_i$，表示第 $i$ 个模板中允许使用的颜色个数，随后给出 $c_i$ 个整数，表示这个模板允许使用的颜色编号。

接下来一行给出 $M$ 个整数 $a_1,a_2,\dots,a_M$，表示初始时每个区域绑定的模板编号。

接下来 $Q$ 行，每行两个整数 $x,t$，表示将第 $x$ 个区域绑定的模板修改为 $t$。

输出格式

输出 $Q$ 行，每行一个整数，表示对应修改后当前合法染色方案数对 $998244353$ 取模后的结果。

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

12  
7  
4  
3

数据范围