NE的挑战Ⅴ

内存限制：256 MB 时间限制：8000 ms

NE 爸爸喜欢研究数据结构，有一天他给你一个长度为 $n$ 的序列，初始都为 $0$，并实现如下三个功能：

$1 \ l\ r\ x$ 先输出$[l,r]$内的所有元素的和，由于答案可能很大，请将答案对$10^9+7$取模后输出，然后再把整个区间内的元素全部修改为$x$。

$2\ l\ r$ 将$[l,r]$区间内所有的元素都变为不包括自身的最大因子，特别地，如果这个元素是素数，则变为 $1$。如果该元素是 $1$，则不变，然后输出修改后$[l,r]$区间的最大值。

$3\ pos$ 输出此时序列中下标为 $pos$ 的元素的权值。

结果 NE 连数据范围都来不及说，鸡尾酒就躺下睡觉了。

NE 叹了口气——他觉得没有人懂他。你能帮他解决这道题吗？

第一行输入一个正整数 $𝑇(𝑇 \leq 100)$，表示数据组数

接下来对于每一组数据，其第一行为两个正整数 $n,m$,表示序列长度和操作次数$ (1 \leq n ≤ 10^{18} ,1 \leq m ≤ 10^5)$接下来 $m$ 行，每行表示一个操作，格式如题面所示，输入保证涉及到的下标和区间端点满足 $(1 \leq l ,r,pos \leq n)$，且对于操作 $1$，满足 $1 ≤ x ≤ 10^{12}$

对于所有测试数据，保证$\sum m ≤ 10^5$,

对于每组测试数据,输出 $𝑛$ 行答案

即对于每个操作输出一行,表示该次操作的答案

样例输入 1

2
10 5
1 9 10 676
1 4 10 536
1 6 10 175
1 9 9 337
2 9 9
17 5
1 13 16 325
1 7 11 681
2 14 15
3 10
1 16 16 822

样例输出 1

C1956 NE的挑战Ⅴ

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示