[十二省联考2019]皮配

题目背景

一年一度的综艺节目《中国好码农》又开始了。本季度,好码农由 Yazid、Zayid、小 R、大 R 四位梦想导师坐镇,他们都将组建自己的梦想战队,并率领队员向梦想发起冲击。 四位导师的**派系**不尽相同,节目组为了营造看点,又将导师分成了不同的**阵营**,与此同时对不同阵营、不同派系都作出了战队总人数限制: - 四位导师分成两个**阵营**: - Yazid、小 R 两位导师组成**蓝阵营**,他们两位的战队人数**总和**不得超过 $C_0$。 - Zayid、大 R 两位导师组成**红阵营**,他们两位的战队人数**总和**不得超过 $C_1$。 - 四位导师分成两个**派系**: - Yazid、Zayid 两位导师属于**鸭派系**,他们两位的战队人数**总和**不得超过 $D_0$。 - 小 R、大 R 两位导师属于 **R 派系**,他们两位的战队人数**总和**不得超过 $D_1$。

题目描述

本季好码农邀请到了全国各路学生精英参赛。他们来自全国 $c$ 个城市的 $n$ 所不同学校(城市的编号从 $1$ 至 $c$,学校的编号从 $1$ 至 $n$)。其中,第 $i$ 所学校所属的城市编号为 $b_i$,且共有 $s_i$ 名选手参赛。 在【题目背景】中提到的各总人数限制之外,本季度《中国好码农》的导师选择阶 段有额外规则如下: - 来自同城. 市. 的所有选手必须加入相同的**阵营**。 - 来自同学. 校. 的所有选手必须选择相同的**导师**。 对于导师,大部分学校的学生对导师没有**偏好**。但是有 $k$ 所学校,其中每所学校的学生有且仅有一位他们不喜欢的导师。同一所学校的学生不喜欢的导师相同,他们**不会加入他们不喜欢的导师的战队**。 面对琳琅满目的规则和选手的偏好,作为好码农忠实观众的你想计算出,在所有选 手都进行了战队选择后,战队组成共有多少种可能的局面? - 两种战队组成的局面被认为是不同的,当且仅当在存在一所学校,使得在这两种 局面中这所学校的选手加入了不同导师的战队。 - 由于答案可能很大,你只需输出可能局面数对 $998244353$ 取模的结果即可。

输入输出格式

输入格式


单个测试点中包含多组数据,输入的第一行包含一个非负整数 $T$ 表示数据组数。接下来依次描述每组数据,对于每组数据: - 第 $1$ 行 $2$ 个正整数 $n$, $c$,分别表示学校数目、城市数目。 - 第 $2$ 行 $4$ 个正整数 $C_0$, $C_1$, $D_0$, $D_1$,分别表示题目中所描述的四个限制。 - 接下来 $n$ 行每行 $2$ 个正整数: - 这部分中第 $i$ 行的两个数依次为 $b_i$, $s_i$,分别表示第 $i$ 所学校的所属城市以及选手数目。 - 保证 $b_i \leqslant c$,$s_i \leqslant\min\left\{M, 10\right\}$。其中 $M = \max \left\{C_0, C_1, D_0, D_1\right\}$。 - 接下来 $1$ 行一个非负整数 $k$,表示选手有偏好的学校数目。 - 接下来 $k$ 行,每行 $2$ 个整数 $i$, $p$,描述编号为 $i$ 的学校选手有偏好: - 其中,$p$ 为一个 $0$ 至 $3$ 之间的整数,描述该校选手不喜欢的导师:$0$ 代表 Yazid,$1$ 代表小 R,$2$ 代表 Zayid,$3$ 代表大 R。 - 保证 $1 \leqslant i \leqslant n$,且各行的 $i$ 互不相同。 对于输入的每一行,如果其包含多个数,则用单个空格将它们隔开。

输出格式


依次输出每组数据的答案,对于每组数据: - 一行一个整数,表示可能局面数对 $998244353$ 取模的结果。

输入输出样例

输入样例 #1

2
2 1
3 2 2 2
1 1
1 2
1
1 0
4 2
10 30 20 30
1 6
2 4
1 7
2 4
2
2 3
3 1

输出样例 #1

1
22

说明

#### 样例解释 对于第 $1$ 组数据: - 唯一的城市 $1$ 包含共 $3$ 名选手,但红阵营的总人数限制为 $2$,无法容纳这些选手,因此他们被迫只能选择蓝阵营。 - 在此基础上,由于 $1$ 号学校的选手不喜欢 Yazid 老师,因此他们就必须加入 R 派系的小 R 老师麾下。 - 由于 R 派系总人数限制为 $2$,因此小 R 老师战队无法容纳 $2$ 号学校的选手,所以他们只能被迫加入Yazid 老师战队。 - 综上所述,可能的局面仅有这一种。 对于第 $2$ 组数据: - 一个显然的事实是,$1$ 号城市的所有选手都无法加入蓝阵营,这是因为 $1$ 号城市的选手总人数超过了蓝阵营的总人数限制,因此他们被迫全部加入红阵营。 - 对于 $2$ 号城市选手加入蓝阵营的情况,稍加计算可得出共有 $15$ 种可能的局面。 - 对于 $2$ 号城市选手加入红阵营的情况,稍加计算可得出共有 $7$ 种可能的局面。 - 综上所述,可能的局面数为 $15 + 7 = 22$ 种。 #### 子任务 ![img](https://s2.ax1x.com/2019/04/07/AfzWPe.png) 其中,$M = \max\left\{C_0, C_1, D_0, D_1\right\}$。 对于所有测试点,保证 $T \leqslant5$。 对于所有测试点中的每一组数据, 保证 $c \leqslant n \leqslant 1000$,$k \leqslant 30$,$M \leqslant 2500$,$1 \leqslant s_i \leqslant \min\left\{M, 10\right\}$。 **另外,请你注意,数据并不保证所有的 $c$ 个城市都有参赛学校。**