Kayzin 最近沉迷于一款名为“Slayers Come”的游戏。游戏开始时有 $n$ 只怪物排成一排，第 $i$ 只怪物的攻击力为 $a_i$（怪物发动攻击时造成的伤害量），防御力为 $b_i$（怪物受到攻击时可以抵消的伤害量）。

Kayzin 有 $m$ 种技能可以学习，第 $i$ 种技能允许 Kayzin 直接击败下标为 $x_i$ 的怪物。该技能具有“亡语”效果，即：如果 $monster_{x_i}$ 被击败，且其左侧存在怪物（下标为 $x_i - 1$），则 $monster_{x_i}$ 会对 $monster_{x_i-1}$ 发动攻击，伤害为 $a_{x_i} - L_i$；如果其右侧存在怪物（下标为 $x_i + 1$），则 $monster_{x_i}$ 也会对 $monster_{x_i+1}$ 发动攻击，伤害为 $a_{x_i} - R_i$。

如果一次攻击对怪物造成的伤害值（伤害值 - 当前怪物防御力）大于或等于 0，则怪物被击败，否则攻击无效。需要注意的是，当怪物死亡时，亡语会引发连锁反应，意味着被亡语击败的怪物随后会攻击其两侧的怪物。具体来说：

• 当 Kayzin 使用第 $i$ 种技能击败 $monster_j$（通过直接攻击或亡语）时，如果 $j > 1$ 且 $a_j - L_i \ge b_{j-1}$，则该技能也会击败 $monster_{j-1}$。
• 当 Kayzin 使用第 $i$ 种技能击败 $monster_j$（通过直接攻击或亡语）时，如果 $j < n$ 且 $a_j - R_i \ge b_{j+1}$，则该技能也会击败 $monster_{j+1}$。

所有怪物（包括被击败的怪物）的下标始终保持不变。被击败的怪物会在当前技能产生的所有攻击效果结束后重新生成，且重新生成的怪物保持其原始攻击力和防御力不变。

Kayzin 想知道，有多少种学习技能的方案，使得在释放所有已学习的技能后，能够至少击败每一只怪物一次。答案对 998244353 取模。

输入格式

第一行包含一个整数 $T (T \le 100)$。接下来是 $T$ 组测试数据。对于每组数据：

第一行包含两个整数 $n (n \le 10^5)$ 和 $m (m \le 10^5)$，$n$ 表示怪物总数，怪物从左到右的下标为 $1 \sim n$。$m$ 表示 Kayzin 可以学习的技能种类。

接下来的 $n$ 行列出了怪物的攻击力和防御力。第 $i$ 行包含两个数字 $a_i$ 和 $b_i (1 \le a_i, b_i \le 10^9)$，$a_i$ 表示 $monster_i$ 的攻击力，$b_i$ 表示 $monster_i$ 的防御力。

接下来的 $m$ 行列出了技能的攻击目标和亡语效果。第 $i$ 行包含三个数字 $x_i (1 \le x_i \le n)$，$L_i$ 和 $R_i (-10^9 \le L_i, R_i \le 10^9)$，$x_i$ 表示第 $i$ 种技能的攻击目标，$L_i$ 表示被该技能击败的怪物削弱其左侧怪物攻击力的数值，$R_i$ 同理。

保证所有测试数据的 $n$ 之和不超过 $10^5$，所有测试数据的 $m$ 之和不超过 $10^5$。

输出格式

对于每组数据，输出一个整数，表示使得在释放所有已学习的技能后，能够至少击败每一只怪物一次的学习技能方案数，答案对 998244353 取模。

样例

样例输入 1

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

样例输出 1

4