小苯的物理小球
题号：NC289439
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯位于一个无限大的二维坐标系中。
初始时，它位于 (sx,sy) 坐标处，而坐标平面内有一些和 x 轴平行的 n 条线段，第 i 条线段用 (l_i, r_i, y_i) 的三元组来表示。如下图所示：

（其中红色为第 i 条线段）

现在小苯会在他所在的位置落下一颗小球，会不断发生如下事件直至小球下落至地面：

\bullet 如果小球没有落在某条线段上，则其会受到重力的影响不断下落。
\bullet 反之如果小球落在了线段上，即其底部有线段支撑，则小球会随机地选择一个方向（左/右）不断移动，直至从线段的一端落下。
（换句话说，小球在线段上有 50\% 的概率不停向左移动，有 50\% 的概率不停向右移动。）

现在小苯提出了 q 次询问，每次他都会给出一个小球的初始坐标，表示将这颗小球从所在位置开始下落。当最终小球下落至地面时（y=0），小球的横坐标的期望是多少，请你帮他算一算吧。

但为了减少输出量，对于每组测试数据，你只需要输出所有查询中小球横坐标的期望之和即可。

需要注意的是：我们认为小球 (x,y) 落在了线段 j 上，当且仅当 l_j < x < r_j 且 y = y_j。
（如上图中，紫色为一种可能的小球运动轨迹，在此轨迹中，小球和最靠右的线段只是擦肩而过，并没有落在上面。）

输入描述:

本题有多组测试数据。
输入的第一行包含一个正整数 T\ (1 \leq T \leq 1000)，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行两个正整数 n, q\ (1 \leq n, q \leq 2 \times 10^5)，分别表示线段的个数和小苯的询问次数。
接下来 n 行，每行三个正整数 l_i, r_i, y_i\ (1 \leq l_i < r_i \leq 10^9, 1 \leq y_i \leq 10^9)，表示第 i 条线段的坐标。
接下来 q 行，每行两个正整数 x_j, y_j\ (1 \leq x_j, y_j \leq 10^9)，表示小苯第 j 次询问的小球的初始坐标。
（保证所有的线段不相交）
（保证所有测试数据中，n,m 的总和都不超过 2 \times 10^5。）

输出描述:

对于每组测试数据：
在单独的一行输出一个整数，表示所有小球最终落在地面上时，x 坐标的期望之和（对 998244353 取模的值）。
（可以证明答案是一个不可约分数 \lfloor\frac{p}{q}\rfloor。为了避免精度问题，请直接输出整数 p \cdot q^{-1}\ \rm{mod}\ M 作为答案，其中 M=998244353，q^{-1} 是满足 q \times q^{-1} ≡ 1\ (\rm{mod}\ M) 的整数。）
示例1

输入

复制 
2
3 2
1 3 1
4 6 1
2 5 2
3 3
7 1
1 1
2 4 1
2 10

输出

复制 
499122187
2

说明

对于第一组测试数据：
第一颗小球有相同的概率落在：(1,0), (3,0), (4,0), (6,0) 这四个点，因此答案为：\frac{1+3+4+6}{4}=\frac{7}{2}，对 998244353 取模的结果为：499122180。
第二颗小球一定会落在 (7,0) 点，因此期望为：7。
因此答案为：499122180+7=499122187。

对于第二组测试数据，唯一的一颗小球不会落在任何线段上，因此小球最终的落点固定为：(2,0)。