Description

This season, “China’s Best Coder” invites student elites from all over the country to compete. They come from $n$ different schools in $c$ cities nationwide (cities are numbered from $1$ to $c$, and schools are numbered from $1$ to $n$). The city index of school $i$ is $b_i$, and there are $s_i$ contestants from this school.

Besides the total size limits mentioned in Background, the mentor selection stage this season has additional rules:

• All contestants from the same city must join the same camp.
• All contestants from the same school must choose the same mentor.

For mentors, students from most schools have no preference. However, there are $k$ schools where, for each such school, the students have exactly one mentor they dislike. Students in the same school dislike the same mentor, and they will not join the team of the mentor they dislike.

With so many rules and preferences, as a loyal viewer you want to compute: after all contestants have chosen teams, how many different final outcomes are possible?

• Two outcomes are considered different if and only if there exists a school such that, in the two outcomes, contestants from this school join teams led by different mentors.
• Since the answer may be large, output it modulo $998244353$.

Input Format

Each test file contains multiple test cases. The first line contains a non-negative integer $T$ indicating the number of test cases. Then each test case is described as follows:

• Line $1$: two positive integers $n$, $c$, representing the number of schools and the number of cities.
• Line $2$: four positive integers $C_0$, $C_1$, $D_0$, $D_1$, representing the four limits described in the statement.
• Next $n$ lines, each with two positive integers:
  • On line $i$ of this part, the two numbers are $b_i$, $s_i$, representing the city of school $i$ and its number of contestants.
  • It is guaranteed that $b_i \leqslant c$, $s_i \leqslant\min\left\{M, 10\right\}$. Here $M = \max \left\{C_0, C_1, D_0, D_1\right\}$.
• Next line: a non-negative integer $k$, the number of schools with preferences.
• Next $k$ lines, each with two integers $i$, $p$, describing that contestants from school $i$ have a preference:
  • Here $p$ is an integer from $0$ to $3$, describing the mentor disliked by this school: $0$ means Yazid, $1$ means Little R, $2$ means Zayid, $3$ means Big R.
  • It is guaranteed that $1 \leqslant i \leqslant n$, and all $i$ are distinct.

For each input line, if it contains multiple numbers, they are separated by a single space.

Output Format

Output the answer for each test case in order:

• For each test case, output one line with one integer, the number of possible outcomes modulo $998244353$.

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
22

Hint

Sample 1 Explanation

For the $1$st test case:

• The only city $1$ contains a total of $3$ contestants, but the total size limit of the Red camp is $2$, so it cannot hold these contestants. Therefore, they are forced to choose the Blue camp.
• Based on this, since contestants from school $1$ dislike mentor Yazid, they must join mentor Little R in the R faction.
• Because the total size limit of the R faction is $2$, mentor Little R’s team cannot hold the contestants from school $2$, so they are forced to join mentor Yazid’s team.
• Therefore, there is only one possible outcome.

For the $2$nd test case:

• An obvious fact is that all contestants in city $1$ cannot join the Blue camp, because the total number of contestants in city $1$ exceeds the total size limit of the Blue camp, so they are forced to all join the Red camp.
• If contestants from city $2$ join the Blue camp, a small calculation shows there are $15$ possible outcomes.
• If contestants from city $2$ join the Red camp, a small calculation shows there are $7$ possible outcomes.
• Therefore, the number of possible outcomes is $15 + 7 = 22$.

Constraints and Notes

::cute-table{tuack}

Here, $M = \max\left\{C_0, C_1, D_0, D_1\right\}$.

For all test points, it is guaranteed that $T \leqslant5$.

For each test case in all test points, it is guaranteed that $c \leqslant n \leqslant 1000$, $k \leqslant 30$, $M \leqslant 2500$, $1 \leqslant s_i \leqslant \min\left\{M, 10\right\}$.

Also, note that the testdata does not guarantee that all $c$ cities have participating schools.

Additional Hint

There are also two additional sample files. Please download them from the attachments.

A warm reminder from the Twelve Provinces Joint Exam problem committee:

There are thousands of testdata, clearing arrays is the first rule.
If you forget to clear in multiple tests, you will cry with a zero score.

Translated by ChatGPT 5