8490: Slayers Come

Kayzin has recently become addicted to a game called Slayers Come. The game opens with
monsters standing in a line, with the i-th monster having an attack power of (the amount of damage
the monster deals when it launches an attack) and a defense power of (the amount of damage the
monster can mitigate when it takes an attack).
Kayzin has skills to learn, with the i-th skill allowing Kayzin to directly defeat a monster with
subscript . This skill has a death rattle effect, i.e., if monster x is defeated and there is a monster
to its left (subscripted ), will launch an attack with damage against monsterx −1
; if there is a monster to its right (subscripted ), then monster x also fires an
attack with damage at monsterx+1).
If the damage dealt (Damage value - current monster defense) to the monster by one attack is greater
than or equal to 0, the monster is defeated , conversely the attack is invalid. It should be noted that
when a monster dies, the death rattle causes a chain reaction, meaning that the monster defeated by
the death rattle will then attack the monsters on either side of it.Namely,
When Kayzin defeats monsterj with the -th skill (by direct attack or deathrattle), if and
, then this skill also defeats monsterj −1
When Kayzin defeats monsterj  with the -th skill (by direct attack or deathrattle), if and
, then this skill also defeats monsterj +1
All monsters, including the defeated monsters, always keep their subscripts constant. The defeated
monster will re-generate after the effects of all attacks caused by the current skill end, and the re-
generated monster keeps its original attack and defense power unchanged.
Kayzin would like to know how many options for learning skills that make it possible to defeat every
monster at least once after releasing all the learned skills. The answer modulo 998244353.

The first line contains an integer . Then test cases follow. For one case,
The first line contains two integer and , denotes the total number of
monsters, and the subscripts of monsters from left to right are 1~n. denotes the type of skills that
kayzin can learn.
The next lines lists the attack and defense power of the monsters. The -th line has two numbers,
and , denotes the attack power of the , denotes the defense
power of the .
The next lines lists the target of the skill's attack and the effects of its death rattle. The -th line has
three numbers, , and , denotes the attack target
of the -th skill, denotes how much the monster defeated by this skill weakens the attack power of
the monster to its left, the same way.
It is guaranteed that the sum of over all test cases doesn't exceed and the sum of over all
test cases doesn't exceed .

Print an integer for each case, indicating the number of options for learning skills that make it possible
to defeat all the monsters at least once after releasing all the learned skills, the answer modulo
998244353.

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

4