南希（Nancy）曾以其新艺术运动街区、朗姆巴巴蛋糕和波兰废王斯坦尼斯瓦夫·莱什琴斯基（Stanislas Leszczynski）而闻名，正是这位国王在18世纪为这座城市留下了华丽精致的建筑瑰宝。

但在2013年，南希重新发现了其文艺复兴时期的历史，整个夏天城中举办了各类活动和展览，从美术馆到温泉浴场，再到植物园。现在，是时候让我去探索老城的文艺复兴遗迹以及查理三世公爵（Duke Charles III）的乌托邦城市规划方案了，那段时期南希曾是欧洲南北十字路口一个强大独立公国的首都。

如今，新旧城区已无缝连接。1588年规划的新城（Ville Neuve）依然是城市的商业中心，遍布着商店和银行，在原计划作为大教堂的广场附近的街道上，覆盖着各类食品市场。

今年秋天，我有幸在新城度过了一个长达数月的假期。每天早餐后，我总会伴着香甜顺滑的法棍面包进行日常思考。让法棍变得更美味的不是“笑牛”（La vache qui rit）奶酪，而是我购买它的地方。但为什么编程的人会如此关心街道上的食品市场数量呢？我将街道上供应法棍的食品市场从 $1$ 到 $n$ 进行了编号。

在每个微光初现的黎明，我都会带着几枚一欧元的硬币，计划去参观几个连续的食品市场。无论风雨，每个食品市场总是以固定价格提供固定数量的法棍。两个不同的食品市场可能有所不同：它们每日供应的法棍数量和价格各不相同。

早起的鸟儿有虫吃。由于无需担心其他顾客，只要钱足够，我可以自由选择买下某个食品市场的所有法棍，或者视而不见直接前往下一个市场。

但为什么像你们这样的人会如此关心我购买法棍的不同方式的数量呢？你们甚至向我反复确认，我可能一分钱不花而挨饿，也可能花掉我拥有的任何金额。正如理论家在处理类似背包问题时所说，如果我在某些市场购买的法棍数量不同，那么购买法棍的方式就被视为不同。

像你们这样追求高效率的人，在确认了我携带的金额和每天的参观计划后，试图告诉我我拥有的购买方式数量。像我这样随性的人，虽然已经为所有日子制定了长长的计划，但一旦收到你们关于某一天的回复，我就会为第二天制定新的计划。我用 $lastans$ 来表示你们回复中的数字，并在我在新城的第一天之前将其设为零。

在某一天，我查看我最初制定的计划，设 $l'$ 和 $r'$ 分别为我决定参观的第一个和最后一个食品市场的编号，设 $c$ 为我决定携带的一欧元硬币数量。通过如下加密般的转换：

$$l = \min\{((l' + lastans) \pmod n) + 1, ((r' + lastans) \pmod n) + 1\}$$

以及

$$r = \max\{((l' + lastans) \pmod n) + 1, ((r' + lastans) \pmod n) + 1\}$$

我得到了一个新的计划，其中 $\min\{x, y\}$ 和 $\max\{x, y\}$ 分别对应 $x$ 和 $y$ 的最小值和最大值，这就是我今天早上执行的计划。你需要告诉我你为这一天计算出的数字，我将把 $lastans$ 设置为你的回复，并对 $(10^9 + 7)$ 取模。

输入格式

输入包含多个测试用例，第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $1000$。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，分别表示街道上的食品市场数量和我计划在新城度过的总天数，其中 $1 \le n, m \le 10000$。

接下来的 $n$ 行，每行描述一个食品市场。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 个食品市场提供的法棍数量及其单价（欧元），其中 $1 \le a_i, b_i \le 1000$。

接下来的 $m$ 行，每行包含三个整数 $l', r'$ 和 $c$，描述我为某一天制定的原始计划，其中 $1 \le l' \le r' \le n$ 且 $1 \le c \le 1000$。

我们保证满足 $n > 100$ 或 $m > 100$ 的测试用例不超过 $10$ 个。

输出格式

对于每个测试用例，首先输出一行 “Case #x:”，其中 $x$ 是从 $1$ 开始的测试用例编号。

然后对于每一天，输出一行一个整数，表示当天购买法棍的不同方式数量，结果对质数 $(10^9 + 7)$ 取模。

样例

样例输入 1

1
3 3
1 1
1 2
1 3
1 3 1
1 3 2
1 3 3

样例输出 1

Case #1:
2
3
4

说明

在样例中，第一天我参观了第一个和第二个市场，只带了一枚硬币。因此，我可以什么都不买，或者在第一家店买一个法棍。第二天，我参观了所有市场并携带了两枚硬币，所以我可以什么都不买，或者在前两个市场中的任意一个买一个法棍。最后一天，我再次参观了前两个市场，但随身携带了三枚硬币。此时我有四种不同的购买法棍方式，但在三天的购物之后，我已经太累了，无法一一列举。