面包工坊每天都会接到成千上万的订单，每天都会需要一些面点师来制作面包。
面包工坊的订单会放在一条流水线上，流水线上有 $N$ 个位置可以放订单。
每天会发生一些操作，将流水线上的一段连续位置放进新的订单，覆盖原有的订单，或是将流水线上的一段连续位置的订单交给某位面点师。
具体来说是以下两种操作：
$1\ l\ r\ p\ q$ : 流水线上第 $l$ 个位置到第 $r$ 个位置会放置新的订单，原有订单会被移除，对应位置的订单所需成品数量分别为 $p \bmod q,$ $(2 p) \bmod q,$ $\cdots,$ $((r - l + 1) p) \bmod q$ 。
$2\ l\ r$ : 流水线上第 $l$ 个位置到第 $r$ 个位置的订单将交给一位面点师，对应位置的订单会被清除。
这一天面包工坊遇到了 $M$ 个操作，面点师们面对着成千上万的订单快要崩溃了，所以他们找到了你，希望你能帮他们计算一下他们每次被分配工作所需要完成的成品数量分别是多少。
第一行包含一个正整数 $T$ ，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
第一行包含两个空格隔开的正整数 $N$ 和 $M$ 。
接下来 $M$ 行，每行表示一个操作，操作格式如上所述。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。
保证不超过 5 组数据满足 $M > 1000$ 。
$1 \leq T \leq 15,$ $1 \leq N \leq 10^9,$ $1 \leq M \leq 50000,$ $1 \leq l, r \leq n,$ $1 \leq p, q \leq 10^9$
输出包含多行，每行对应一个分配订单操作所需的成品数量。
2
3 5
2 1 3
1 1 3 5 7
2 2 3
1 1 2 3 4
2 1 3
1000000000 2
1 1 1000000000 3 998244353
2 1 10000000000
4
5
498250517096288512对于第一组数据
0 个成品。5, 3, 1 ，所以第二个分配操作需要 3 + 1 = 4 个成品。3, 2, 0 ，所以第三个分配操作需要 3 + 2 + 0 = 5 个成品。