题目描述

关老师是一个办事能力特别强的老师，因此她平时会被安排去做很多事情，很少有休息的时间。这天，关老师难得有空，于是她来到 $ACM$ 实验室看望小王，并且和小王玩起了游戏。

游戏规则如下：关老师有 $n$ 个可以无限装水的桶，它们在刚开始的时候都是空的。关老师会随机给一些水桶加水，这期间也会有其他同学来用水桶的水。关老师会时不时告诉小王某些编号连在一起的水桶都有 $x(x \ge 1)$ 毫升水，或者告诉小王某个水桶现在有 $y(y \ge 1)$ 毫升水。小王需要做的就是记下当前每个水桶里有多少水，关老师会随机抽查让小王说出一些水桶一共有多少毫升水，或者让小王说出某个水桶有多少毫升水。

输入格式

第一行输入一个数 $n(1 \le n \le 2 \times 10^5)$，表示关老师一共有 $n$ 个空的水桶，从 $1 \sim n$ 分别为第 $1$ 个桶，第 $2$ 个桶 $\dots$ 第 $n$ 个桶；
第二行输入一个数 $t(1 \le t \le 2 \times 10^6)$，表示接下来输入 $t$ 行，每行第一个数表示你要进行的是第几个操作，这些操作分别是：

• $1$ $a$ $b$ $x_1$ $x_2$（$1 \le a \le b \le n$，$1 \le x_1 \le x_2 \le 10^6$，以空格分隔）表示要先求出 $x_1$ 到 $x_2$（包括 $x_1$ 和 $x_2$）之间素数的数量 $x$，然后重置第 $a$ 个桶到第 $b$ 个桶（包括第 $a$ 个桶和第 $b$ 个桶）之间的所有桶都有 $x$ 毫升水，关老师保证 $x \ge 1$。
• $2$ $c$ $y_1$ $y_2$（$1 \le c \le n$，$1 \le y_1 \le y_2 \le 10^6$，以空格分隔）表示要先求出 $y_1$ 到 $y_2$（包括 $y_1$ 和 $y_2$）之间素数的数量 $y$，然后重置第 $c$ 个桶有 $y$ 毫升水，关老师保证 $y \ge 1$。
• $3$ $d$ $e$（$1 \le d \le e \le n$，以空格分隔）表示关老师询问小王第 $d$ 个桶到第 $e$ 个桶（包括第 $d$ 个桶和第 $e$ 个桶）现在一共有多少毫升水；
• $4$ $f$（$1 \le f \le n$，以空格分隔）表示关老师询问小王第 $f$ 个桶现在有多少毫升水

输出格式

对于关老师每次的询问，输出一个整数表示小王的回答，每个回答占据一行。

样例

5
4
2 3 5 20
4 3
1 1 5 24 33
3 1 5

6
10

样例解释

一共有 $5$ 个桶，$4$ 次操作：

• 第一次操作，$5$ 到 $20$ 之间一共有 $6$ 个素数，因此第 $3$ 个桶里的水当前有 $6$ 毫升；
• 第二次操作，询问第 $3$ 个桶目前有多少毫升水，对应第一次输出 $6$；
• 第三次操作，$24$ 到 $33$ 一共有 $2$ 个素数，因此第 $1$ 个桶到第 $5$ 个桶当前各有 $2$ 毫升水；
• 第四次操作，询问第 $1$ 个桶到第 $5$ 个桶现在一共有多少毫升水，注意到第 $3$ 个桶的水在第三次操作的时候也变成了 $2$ 毫升，因此 $5$ 个桶一共有 $10$ 毫升水，对应第二次输出。