Source: Super League of Chinese College Students Algorithm Design 2022, Contest 2 by HDU.

Problem Description

Kayzin has recently become addicted to a game called Slayers Come. The game opens with $n$ monsters standing in a line, with the $i$-th monster having an attack power of $a_i$ (the amount of damage the monster deals when it launches an attack) and a defense power of $b_i$ (the amount of damage the monster can mitigate when it takes an attack).

Kayzin has $m$ skills to learn, with the $i$-th skill allowing Kayzin to directly defeat a monster with subscript $x_i$. This skill has a death rattle effect, i.e., if $monster_{x_i}$ is defeated and there is a monster to its left (subscripted $x_i-1$), $monster_{x_i}$ will launch an attack with damage $a_{x_i}-L_i$ against $monster_{x_i-1}$; if there is a monster to its right (subscripted $x_i+1$), then $monster_{x_i}$ also fires an attack with damage $a_{x_i}-R_i$ at $monster_{x_i+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 $monster_j$ with the $i$-th skill (by direct attack or deathrattle), if $j > 1$ and $a_j-L_i\ge b_{j-1}$, then this skill also defeats $monster_{j-1}$
• When Kayzin defeats $monster_j$ with the $i$-th skill (by direct attack or deathrattle), if $j < n$ and $a_j-R_i\ge b_{j+1}$, then this skill also defeats $monster_{j+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$.

Input

The first line contains an integer $T(T\le 100)$ . Then $T$ test cases follow. For one case,

The first line contains two integer $n$ $(n\le 10^5)$ and $m$ $(m\le 10^5)$ , $n$ denotes the total number of monsters, and the subscripts of monsters from left to right are $1\sim n$. $m$ denotes the type of skills that kayzin can learn.

The next $n$ lines lists the attack and defense power of the monsters. The $i$-th line has two numbers, $a_i$ and $b_i$ $(1\le a_i,b_i\le 10^9)$, $a_i$ denotes the attack power of the $monster_i$, $b_i$ denotes the defense power of the $monster_i$.

The next $m$ lines lists the target of the skill's attack and the effects of its death rattle. The $i$-th line has three numbers, $x_i$ $(1\le x_i\le n)$, $L_i$ and $R_i$ $(-10^9\le L_i,R_i\le 10^9)$, $x_i$ denotes the attack target of the $i$-th skill, $L_i$ denotes how much the monster defeated by this skill weakens the attack power of the monster to its left, $R_i$ the same way.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$ and the sum of $m$ over all test cases doesn't exceed $10^5$.

Output

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$.

Sample

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

4