The annual variety show "China's Best Coder" has begun again. This season, the show features four dream mentors: Yazid, Zayid, Little R, and Big R. Each of them will form their own dream team and lead their members to strive for their dreams.

The four mentors have different styles. To create drama, the show organizers have divided the mentors into different camps and factions, while also setting limits on the total number of team members for each camp and faction:

• The four mentors are divided into two camps:
  • Yazid and Little R form the Blue Camp, and the total number of members in their teams must not exceed $C_0$.
  • Zayid and Big R form the Red Camp, and the total number of members in their teams must not exceed $C_1$.
• The four mentors are divided into two factions:
  • Yazid and Zayid belong to the Duck Faction, and the total number of members in their teams must not exceed $D_0$.
  • Little R and Big R belong to the R Faction, and the total number of members in their teams must not exceed $D_1$.

Description

This season, "China's Best Coder" has invited student elites from across the country. They come from $n$ different schools in $c$ cities (cities are numbered from $1$ to $c$, and schools are numbered from $1$ to $n$). The $i$-th school belongs to city $b_i$ and has $s_i$ students participating.

In addition to the total number limits mentioned in the background, the mentor selection stage this season has the following extra rules:

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

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

Given the various rules and student preferences, as a loyal viewer of "China's Best Coder," you need to calculate how many possible team configurations exist after all students have made their choices.

• Two team configurations are considered different if and only if there exists a school where the students in that school joined different mentors' teams in the two configurations.
• Since the answer may be very large, you only need to output the result modulo $998,244,353$.

Input

The input is read from the file mentor.in.

Each test case contains multiple datasets. The first line contains a non-negative integer $T$ representing the number of datasets.

For each dataset: The first line contains two positive integers $n, c$, representing the number of schools and the number of cities, respectively. The second line contains four positive integers $C_0, C_1, D_0, D_1$, representing the four limits described in the problem. The next $n$ lines each contain two positive integers: The $i$-th line contains $b_i, s_i$, representing the city to which the $i$-th school belongs and the number of students in that school. It is guaranteed that $b_i \le c$ and $s_i \le \min\{M, 10\}$, where $M = \max\{C_0, C_1, D_0, D_1\}$. The next line contains a non-negative integer $k$, representing the number of schools where students have preferences. The next $k$ lines each contain two integers $i, p$, describing the preference of the students in school $i$: $p$ is an integer between $0$ and $3$, representing the mentor the students dislike: $0$ for Yazid, $1$ for Little R, $2$ for Zayid, and $3$ for Big R. * It is guaranteed that $1 \le i \le n$ and that the $i$ values in these lines are distinct.

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

Output

Output to the file mentor.out.

Output the answer for each dataset sequentially: * One integer per line, representing the number of possible configurations modulo $998,244,353$.

Examples

Input 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 3
3 1

Output 1

1
22

Note 1

For the first dataset: The only city, city 1, contains a total of 3 students, but the Red Camp's total limit is 2, which cannot accommodate these students, so they are forced to choose the Blue Camp. Based on this, since students from school 1 dislike mentor Yazid, they must join mentor Little R of the R Faction. Since the R Faction's total limit is 2, mentor Little R's team cannot accommodate the students from school 2, so they are forced to join mentor Yazid's team. In summary, there is only one possible configuration.

For the second dataset: It is a clear fact that all students in city 1 cannot join the Blue Camp because the total number of students in city 1 exceeds the Blue Camp's total limit, so they are forced to join the Red Camp. For the case where students from city 2 join the Blue Camp, a quick calculation shows there are 15 possible configurations. For the case where students from city 2 join the Red Camp, a quick calculation shows there are 7 possible configurations. In summary, the number of possible configurations is $15 + 7 = 22$.

Examples 2

See mentor/mentor2.in and mentor/mentor2.ans in the contestant directory.

Examples 3

See mentor/mentor3.in and mentor/mentor3.ans in the contestant directory.

Subtasks

Where $M = \max\{C_0, C_1, D_0, D_1\}$. For all test cases, it is guaranteed that $T \le 5$. For every dataset in all test cases, it is guaranteed that $c \le n \le 1000$, $k \le 30$, $M \le 2500$, and $1 \le s_i \le \min\{M, 10\}$. Additionally, please note that the data does not guarantee that all $c$ cities have participating schools.