U297943 III.追想
题目背景
外殻軌道の果て、永遠の終わり。
题目描述
Fery 子有 $n$ 个记忆碎片，每个碎片的追忆值为 $a_i$。
Fery 子会进行 $m$ 次操作。操作有四种类型。
每种操作给定区间 $[l,r]$。
操作 1：给定正整数 $k$，对于 $\forall i\in[l,r],a_i=\lfloor\log_k(a_i)\rfloor$。
若 $a_i=0$ ，请忽视对其的操作。
操作 2：给定正整数 $v$，对于 $\forall i\in[l,r],a_i=\min(a_i,v)$。
操作 3：给定正整数 $x$，对于 $\forall i\in[l,r],a_i=x$。
操作 4：输出 $\sum\limits_{i=l}^{r}a_i$。
输入格式
一行两个整数 $n,m$。
接下来读入 $n$ 个整数 $a_i$。
接下来读入 $m$ 行。
每行读入 $op,l,r$。
若 $op=1$，再读入 $k$。
若 $op=2$，再读入 $v$。
若 $op=3$，再读入 $x$。
输出格式
对于 $op=4$，输出 $\sum\limits_{i=l}^{r}a_i$。
说明/提示
对于 $10 \%$ 的数据，$1\leq n,m \leq 5000$。
另外对于 $10 \%$ 的数据：保证 $op=3$ 时，$l_i=r_i$。
对于 $100\%$ 的数据：
$1\leq n,m\leq 5\times 10^5$；
$0\leq a_i,v,x\leq 10^9$；
$2\leq k\leq 5$。