T168376 [AC6-M13] The Liberation Of Gracemeria

『Garuda 队，到现在为止 　一切都还没完呢。』 …… 「这家伙是谁？」 『真正的战争才刚刚开始。』 「你是谁？你到底在说什么？！」 『贫瘠的土地和迂腐的政府 　不再值得我们去保护。』 『唯一值得我们保护的…… 　……只有，未来。』 「那是一架战机…… 　……而且很快！」 「确认高速导弹来袭！导弹数量巨大 快规避！」 …… 『这是 Ulysses 所带来的必然的命运。』 『现在是时候让我恶的一面来控制一切了。』 $$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 13} \\\Large\text{The Liberation Of Gracemeria}\\\tiny -\ Wings\ Triumphant\ -$$ 

对于任意一个 $\geq 2$ 的整数 $x$，如果 $x$ 满足序列 $g_i=\gcd(x,i)(1\le i< x)$ 是回文的，则称 $x$ 是 GCD Palindrome Number。 现在给定一个序列 $a_{[1,n]}$，初始都是 $2$，和 $m$ 次操作。 操作分为 $10$ 种： | 编号 | 操作 | | :-----------: | :-----------: | | $1\ l\ r$ | 求 $a_{[l,r]}$ 中有多少个 GCD Palindrome Number | | $2\ l\ r\ v$ | 对所有 $l\leq i\leq r$，将 $a_i$ 修改为 $a_i^v$ | | $3\ l\ r\ v$ | 对所有 $l\leq i\leq r$，将 $a_i$ 修改为 $\lceil \sqrt[v]{a_i}\rceil$ | | $4\ l\ r\ v$ | 将区间 $[l,r]$ 的所有数加 $v$ | | $5\ l\ r\ v$ | 将区间 $[l,r]$ 的所有数乘 $v$ | | $6\ l\ r\ v$ | 将区间 $[l,r]$ 的所有数对 $v$ 取 $\min$ | | $7\ l\ r\ v$ | 将区间 $[l,r]$ 的所有数对 $v$ 取 $\max$ | | $8\ l\ r\ v$ | 将区间 $[l,r]$ 的所有 $>v+1$ 的数减 $v$ | | $9\ l\ r\ v$ | 将区间 $[l,r]$ 的所有 $>v$ 且被 $v$ 整除的数除 $v$ | | $10\ l\ r\ v$ | 对所有 $l\leq i\leq r$，将 $a_i$ 修改为 $i^va_i$ |

第一行两个整数，表示 $n,m$。 接下来 $m$ 行，每行第一个整数 $o$ 代表操作编号。 如果 $o$ 是 $1$，接下来 $2$ 个整数，表示操作的 $l,r$。 否则，接下来 $3$ 个整数，表示操作的 $l,r,v$。

每行一个整数，表示对应的查询操作的答案。

- Subtask 1（10 pts）：保证只有 $1,4$ 操作，且 $n\leq 10, m\leq 10,v\leq 10$。 - Subtask 2（90 pts）：无特殊限制。 对于 $100\%$ 的数据，$1\leq n\leq 10^{9}$，$0\leq m\leq 10^5$，$1\leq l\leq r\leq n$，$3\leq v\leq 10^{9}$。 注意 $a_i$ 不取模。 --- 『Strigon 队撤离了战斗空域。』 『我们赢了……』 「确认敌机被摧毁！」 「全部搞定了！战争结束了！」 …… 「Talisman！」 「所有的威胁都已解除，我们的人民重新站起来了！」