小明在研究二进制信号传输系统。在接收到一串由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的长度为 $$$n$$$ 的信号 $$$S$$$（下标从 $$$1$$$ 到 $$$n$$$）后，他需要将这段信号完整地分割成若干数据包，每个数据包都是 $$$S$$$ 的一段非空连续子串。
如果一个数据包中字符 $$$\mathtt{1}$$$ 的出现次数是一个质数$$$^{\text{∗}}$$$，则称该数据包是一个「好数据包」。
小明希望划分出的每个数据包都是「好数据包」。请你求出最多能划分出的数据包个数 $$$k$$$；如果不存在满足要求的划分，请输出 $$$-1$$$。
$$$^{\text{∗}}$$$质数是只有两个不同的正因数的自然数。例如 $$$2$$$、$$$3$$$、$$$5$$$、$$$7$$$、$$$11$$$ 都是质数，而 $$$0$$$、$$$1$$$、$$$4$$$、$$$6$$$、$$$8$$$、$$$9$$$ 都不是质数。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^5$$$），表示测试用例的数量。对于每组测试用例：
保证所有测试用例的 $$$n$$$ 的总和不超过 $$$2 \times 10^5$$$。
对于每组测试用例：输出一行，包含一个整数 $$$k$$$，表示最多能划分出的数据包个数；如果不存在满足要求的划分，则输出 $$$-1$$$。
461011013010811111111500000
2-14-1
对于第一组测试用例，$$$S = \mathtt{101101}$$$，共包含 $$$4$$$ 个 $$$\mathtt{1}$$$。一种最优的划分为 $$$\mathtt{101} \mid \mathtt{101}$$$，两个数据包各包含 $$$2$$$ 个 $$$\mathtt{1}$$$，而 $$$2$$$ 是质数，因此这两个数据包都是「好数据包」。可以证明，不存在划分为 $$$3$$$ 个或更多「好数据包」的方案，所以答案为 $$$2$$$。
对于第二组测试用例，$$$S = \mathtt{010}$$$，仅包含 $$$1$$$ 个 $$$\mathtt{1}$$$。由于 $$$1$$$ 不是质数，并且继续划分只能得到 $$$0$$$ 个 $$$\mathtt{1}$$$ 以及 $$$1$$$ 个 $$$\mathtt{1}$$$ 的数据包，因此不存在方案，输出 $$$-1$$$。
对于第三组测试用例，$$$S = \mathtt{11111111}$$$，共包含 $$$8$$$ 个 $$$\mathtt{1}$$$。一种最优的划分为 $$$\mathtt{11} \mid \mathtt{11} \mid \mathtt{11} \mid \mathtt{11}$$$，每个数据包各包含 $$$2$$$ 个 $$$\mathtt{1}$$$，可以证明不存在更优方案，所以答案为 $$$4$$$。
在类 Unix 操作系统（如 Linux、macOS）中，每个文件和目录都有一组权限，用于控制谁可以读取、写入或执行它。
普通权限分为三组：所有者（user）、所属组（group）和其他用户（other）。每组权限用三个字符表示，依次对应读（$$$\mathtt{\color{orange}{r}}$$$）、写（$$$\mathtt{\color{red}{w}}$$$）、执行（$$$\mathtt{\color{green}{x}}$$$）；若某项权限不存在，则对应位置显示为 -。将三组权限的字符依次拼接，即得到长度为 $$$9$$$ 的符号表示。
例如 $$$\mathtt{\color{orange}{r}}\mathtt{\color{red}{w}}\mathtt{\color{green}{x}}\mathtt{\color{orange}{r}}$$$-$$$\mathtt{\color{green}{x}}\mathtt{\color{orange}{r}}$$$-- 表示所有者可读、可写、可执行（$$$\mathtt{\color{orange}{r}}\mathtt{\color{red}{w}}\mathtt{\color{green}{x}}$$$），所属组可读、可执行（$$$\mathtt{\color{orange}{r}}$$$-$$$\mathtt{\color{green}{x}}$$$），其他用户只读（$$$\mathtt{\color{orange}{r}}$$$--）。
除三组普通权限外，还有三种特殊权限：setuid、setgid 和 sticky bit。
一个文件的完整权限可以用四位八进制数表示：从高到低四位依次为特殊权限位 $$$a$$$、所有者权限位 $$$b$$$、所属组权限位 $$$c$$$ 和其他用户权限位 $$$d$$$，每一位都是 $$$0 \sim 7$$$ 的数字。
普通权限位 $$$b$$$、$$$c$$$、$$$d$$$ 与符号表示中的三组字符一一对应：每一位的三个二进制位从高到低依次对应 r、w、x，对应位为 $$$1$$$ 表示具有该权限，为 $$$0$$$ 则没有。
例如 $$$7 = (111)_2$$$ 表示 $$$\mathtt{\color{orange}{r}}\mathtt{\color{red}{w}}\mathtt{\color{green}{x}}$$$，$$$5 = (101)_2$$$ 表示 $$$\mathtt{\color{orange}{r}}$$$-$$$\mathtt{\color{green}{x}}$$$，$$$4 = (100)_2$$$ 表示 $$$\mathtt{\color{orange}{r}}$$$--。
把后三位 $$$7$$$、$$$5$$$、$$$4$$$ 对应的字符依次拼接，$$$0754$$$ 的符号表示就是 $$$\mathtt{\color{orange}{r}}\mathtt{\color{red}{w}}\mathtt{\color{green}{x}}\mathtt{\color{orange}{r}}$$$-$$$\mathtt{\color{green}{x}}\mathtt{\color{orange}{r}}$$$--。
特殊权限位 $$$a$$$ 的三个二进制位从高到低依次对应 setuid、setgid、sticky bit。例如 $$$a = 5 = (101)_2$$$ 表示同时设置 setuid 和 sticky bit。三种特殊权限的含义如下：
特殊权限不会增加字符，而是替换符号表示中某个执行位上的字符：
替换规则为：若该位置原为 $$$\mathtt{\color{green}{x}}$$$，setuid 和 setgid 将其替换为小写字母 $$$\mathtt{\color{purple}{s}}$$$，sticky bit 将其替换为小写字母 $$$\mathtt{\color{purple}{t}}$$$；若该位置原为 -，则替换为对应的大写字母 $$$\mathtt{\color{purple}{S}}$$$ 或 $$$\mathtt{\color{purple}{T}}$$$。
例如 $$$4755$$$ 的符号表示为 $$$\mathtt{\color{orange}{r}}\mathtt{\color{red}{w}}\mathtt{\color{purple}{s}}\mathtt{\color{orange}{r}}$$$-$$$\mathtt{\color{green}{x}}\mathtt{\color{orange}{r}}$$$-$$$\mathtt{\color{green}{x}}$$$：setuid 生效，且所有者组的执行位原为 $$$\mathtt{\color{green}{x}}$$$，故替换为小写 $$$\mathtt{\color{purple}{s}}$$$。
给定一个用四位八进制数表示的权限，请你输出它对应的符号表示。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 4096$$$），表示测试用例的数量。对于每组测试用例：
对于每组测试用例：输出一行一个长度为 $$$9$$$ 的字符串，表示该权限对应的符号表示。
70755475546441777200077775070
rwxr-xr-xrwsr-xr-xrwSr--r--rwxrwxrwt-----S---rwsrwsrwt--Srwx--T
如果一个非负整数的二进制表示中 $$$1$$$ 的个数是一个质数$$$^{\text{∗}}$$$，则称这个非负整数是一个「好数」。例如，$$$3$$$（二进制为 $$$(11)_2$$$，包含 $$$2$$$ 个 $$$1$$$）和 $$$7$$$（二进制为 $$$(111)_2$$$，包含 $$$3$$$ 个 $$$1$$$）都是「好数」，而 $$$1$$$（包含 $$$1$$$ 个 $$$1$$$）和 $$$15$$$（二进制为 $$$(1111)_2$$$，包含 $$$4$$$ 个 $$$1$$$）都不是「好数」。
定义 $$$f(k) = 1 \oplus 2 \oplus \cdots \oplus k$$$，其中 $$$\oplus$$$ 表示按位异或运算$$$^{\text{†}}$$$。
给定一个正整数 $$$N$$$，请你求出小于 $$$N$$$ 的最大的正整数 $$$k$$$，使得 $$$f(k)$$$ 是一个「好数」。
$$$^{\text{∗}}$$$质数是只有两个不同的正因数的自然数。例如 $$$2$$$、$$$3$$$、$$$5$$$、$$$7$$$、$$$11$$$ 都是质数，而 $$$0$$$、$$$1$$$、$$$4$$$、$$$6$$$、$$$8$$$、$$$9$$$ 都不是质数。
$$$^{\text{†}}$$$按位异或是一种二进制位运算：将两个整数写成二进制后逐位比较，对应位不同则结果的该位为 $$$1$$$，相同则为 $$$0$$$。例如 $$$5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$$$。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \le T \le 10^5$$$），表示测试用例的数量。对于每组测试用例：
对于每组测试用例，输出一行，包含一个整数 $$$k$$$，表示小于 $$$N$$$ 且满足 $$$f(k)$$$ 是「好数」的最大正整数。
4351370368744177658
221270368744177656
对于第一组测试用例，$$$N = 3$$$，小于 $$$3$$$ 的正整数只有 $$$1$$$ 和 $$$2$$$。$$$f(1) = 1$$$，包含 $$$1$$$ 个 $$$1$$$，不是「好数」；$$$f(2) = 1 \oplus 2 = 3$$$，二进制为 $$$(11)_2$$$，包含 $$$2$$$ 个 $$$1$$$，是「好数」，因此答案为 $$$2$$$。
对于第二组测试用例，$$$N = 5$$$。从大到小依次检验：$$$f(4) = 4$$$，包含 $$$1$$$ 个 $$$1$$$；$$$f(3) = 0$$$，包含 $$$0$$$ 个 $$$1$$$，都不是「好数」；$$$f(2) = 3$$$，是「好数」，因此答案为 $$$2$$$。
对于第三组测试用例，$$$N = 13$$$。$$$12$$$ 是小于 $$$13$$$ 的最大正整数，且 $$$f(12) = 12$$$，二进制为 $$$(1100)_2$$$，包含 $$$2$$$ 个 $$$1$$$，是「好数」，因此答案为 $$$12$$$。
Kasumi 有一副神奇的扑克牌，共有 $$$n \times k$$$ 张牌：对于 $$$1$$$ 到 $$$n$$$ 的每种点数，都恰好有 $$$k$$$ 张该点数的牌。
并且，$$$k$$$ 恰好为 $$$\pi(n)$$$，即 $$$1$$$ 到 $$$n$$$ 中质数的个数。
对于一个整数序列 $$$a_1, a_2, \ldots, a_m$$$ 中的位置 $$$i$$$（$$$2 \le i \le m$$$），如果 $$$a_{i-1}$$$ 整除$$$^{\text{∗}}$$$ $$$a_i$$$ 或 $$$a_i$$$ 整除 $$$a_{i-1}$$$（即 $$$a_{i-1} \mid a_i$$$ 或 $$$a_i \mid a_{i-1}$$$），则称位置 $$$i$$$ 是「Kirakira」的；位置 $$$1$$$ 不是「Kirakira」的。
例如，在序列 $$$[2, 4, 5, 1, 2]$$$ 中，位置 $$$2$$$、$$$4$$$、$$$5$$$ 是「Kirakira」的，而位置 $$$1$$$、$$$3$$$ 不是。
Kasumi 想把这副扑克牌排成一个序列，使得「Kirakira」的位置尽可能多。请你帮她排出一个这样的序列并输出。
$$$^{\text{∗}}$$$对于整数 $$$a$$$ 和 $$$b$$$（$$$a \neq 0$$$），如果存在一个整数 $$$t$$$，使得 $$$b = a \cdot t$$$，则称 $$$a$$$ 整除 $$$b$$$，记作 $$$a \mid b$$$。例如 $$$2 \mid 4$$$，而 $$$4 \nmid 2$$$。
仅一行，包含两个整数 $$$n$$$ 和 $$$k$$$（$$$2 \le n \le 5000$$$，$$$k = \pi(n)$$$），分别表示扑克牌的最大点数和每种点数的牌的数量。
输出一行，包含 $$$n \times k$$$ 个整数，用空格分隔，表示你排成的序列。
要求 $$$1$$$ 到 $$$n$$$ 的每个整数在序列中恰好出现 $$$k$$$ 次，且「Kirakira」的位置尽可能多。如果存在多个满足要求的序列，你可以输出其中任意一个。
6 3
3 6 2 4 2 4 4 2 6 3 6 3 1 5 1 5 1 5
北部禁区曾长期被危险的侵蚀能量笼罩，如今已被成功收复。为了让区内的设施重新投入使用，庄方宜需要在禁区内铺设「天师桩阵列」，稳定裂隙周围残留的侵蚀能量。
重建队伍已经沿一条施工线路从左到右设置了 $$$m$$$ 个辅桩，编号为 $$$1$$$ 到 $$$m$$$。每个辅桩携带一种能量信号，分为「阴爻」和「阳爻」两类，分别用字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 表示，因此这 $$$m$$$ 个辅桩可以表示为一个长度为 $$$m$$$ 的 01 串 $$$S$$$。
队伍拥有数量不限的主桩。为了激活一个主桩，需要按照一个长度为 $$$n$$$ 的 01 串 $$$T$$$ 所规定的顺序连接并激活辅桩：从 $$$S$$$ 中选择 $$$n$$$ 个位置 $$$p_1 \lt p_2 \lt \cdots \lt p_n$$$，使得按从左到右的顺序读出这些位置上的字符恰好得到 $$$T$$$，即：
$$$$$$ S_{p_i} = T_i \quad (1 \le i \le n). $$$$$$
若同时激活多个主桩，它们之间的共振将相互干扰，因此必须完整激活一个主桩后，才能开始激活下一个主桩。形式化地，如果依次激活了 $$$k$$$ 个主桩，第 $$$j$$$ 个主桩选择的位置为 $$$p_{j,1} \lt p_{j,2} \lt \cdots \lt p_{j,n}$$$，那么需要满足：
$$$$$$ \begin{cases} S_{p_{j,i}} = T_i & (1 \le j \le k,\ 1 \le i \le n), \\ p_{j,n} \lt p_{j+1,1} & (1 \le j \lt k). \end{cases} $$$$$$
受地形和施工进度影响，重建队伍准备了 $$$q$$$ 种相互独立的施工方案，第 $$$i$$$ 种方案中只有编号位于区间 $$$[l_i, r_i]$$$ 内的辅桩可以使用。对于每种施工方案，请你求出该方案最多能够成功激活的主桩数量。
第一行三个整数 $$$n$$$、$$$m$$$、$$$q$$$（$$$1 \le n \le 100$$$，$$$n \le m \le 2 \times 10^5$$$，$$$1 \le q \le 2 \times 10^5$$$），分别表示 01 串 $$$T$$$ 的长度、辅桩的数量、施工方案的数量。
第二行一个长度为 $$$n$$$ 的 01 串 $$$T$$$（仅包含字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$），表示激活一个主桩所需的辅桩类型顺序。
第三行一个长度为 $$$m$$$ 的 01 串 $$$S$$$（仅包含字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$），表示从左到右每个辅桩的类型。
接下来 $$$q$$$ 行，其中第 $$$i$$$ 行两个整数 $$$l_i$$$ 和 $$$r_i$$$（$$$1 \le l_i \le r_i \le m$$$），表示第 $$$i$$$ 种施工方案只能使用编号位于区间 $$$[l_i, r_i]$$$ 内的辅桩。
对于每种施工方案，输出一行一个非负整数，表示该方案中最多能够成功激活的主桩数量。
3 10 311001011010101 101 63 9
2 1 1
样例中，对于第一种施工方案，我们可以使用区间 $$$[1, 10]$$$ 内的辅桩。我们用以下策略可以依次激活两个主桩：
可以证明，不存在激活更多主桩的方案，因此第一种施工方案的答案为 $$$2$$$。
对于正整数 $$$m$$$、$$$X$$$、$$$Y$$$，定义如下过程：
初始时，有 $$$m$$$ 个整数点 $$$P_1, P_2, \ldots, P_m$$$ 位于 $$$(0, 0)$$$，以及一个整数点 $$$P_{m + 1}$$$ 位于 $$$(X, Y)$$$。记点 $$$P_i$$$ 的坐标为 $$$(x_{P_i}, y_{P_i})$$$。
你可以进行若干次（包括零次）操作。每次操作选择一个整数 $$$k$$$（$$$2 \le k \le m$$$），将点 $$$P_k$$$ 向 $$$x$$$ 轴正方向或 $$$y$$$ 轴正方向移动 $$$1$$$ 个单位长度。每次操作后，必须满足：对于所有 $$$1 \le i \le j \le m + 1$$$，都有 $$$x_{P_i} \le x_{P_j}$$$ 且 $$$y_{P_i} \le y_{P_j}$$$。
定义这 $$$m + 1$$$ 个点的「价值」为下标相邻的两点的曼哈顿距离的最小值，即： $$$$$$ \min \limits_{1 \le i \le m} \left( \left| x_{P_{i + 1}} - x_{P_i} \right| + \left| y_{P_{i + 1}} - y_{P_i} \right| \right) $$$$$$
令 $$$F(m, X, Y)$$$ 表示经过若干次操作后能够得到的最大「价值」。
给定一个长度为 $$$n$$$ 的正整数序列 $$$a_1, a_2, \ldots, a_n$$$，请你求出 $$$\sum \limits_{1 \le j \le i \le n} F(i, a_i, a_j)$$$ 的值。
第一行一个整数 $$$n$$$（$$$1 \le n \le 10^5$$$），表示序列的长度。
第二行 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$（$$$1 \le a_i \le 10^5$$$），表示给定的序列。
仅一行，包含一个整数，表示你的答案。
61 1 4 5 1 4
19
样例中 $$$n = 6$$$，$$$a = [1, 1, 4, 5, 1, 4]$$$。
当 $$$i = 1$$$，$$$j = 2$$$ 时，求和项为 $$$F(2, 1, 1)$$$：初始时 $$$P_1 = P_2 = (0, 0)$$$，$$$P_3 = (1, 1)$$$；将 $$$P_2$$$ 向 $$$x$$$ 轴正方向移动 $$$1$$$ 个单位长度，此时 $$$P_2 = (1, 0)$$$，下标相邻的两点的曼哈顿距离分别为 $$$1$$$ 和 $$$1$$$，「价值」为 $$$1$$$。可以证明无法得到更大的「价值」，因此 $$$F(2, 1, 1) = 1$$$。
将所有求和项累加，可以证明答案是 $$$19$$$。
小 i 非常喜欢 utf8 string，因此他为你准备了一个与字节序列有关的挑战。
一个长度为 $$$k$$$ 的由字节$$$^{\text{∗}}$$$组成的序列 $$$[c_1, c_2, \ldots, c_k]$$$ 构成 UTF-8 编码字符，当且仅当它满足以下形式之一：
一个由字节组成的序列构成 utf8 string，当且仅当它可以被恰好完整地分成若干个 UTF-8 编码字符的拼接。
给定一个长度为 $$$n$$$ 的初始字节序列 $$$a_1, a_2, \ldots, a_n$$$。接下来，小 $$$i$$$ 将会对这个序列进行 $$$q$$$ 次操作，每次操作为以下两种类型之一：
$$$^{\text{∗}}$$$字节指的是介于 $$$0$$$ 到 $$$255$$$ 之间（包括两端）的整数。
第一行包含两个整数 $$$n$$$ 和 $$$q$$$（$$$1 \leq n,q \leq 5 \times 10^5$$$）。
第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$（$$$0 \leq a_i \leq 255$$$），表示初始序列。
接下来的 $$$q$$$ 行，每行表示一次操作：
对于每个类型为 2 的询问，输出一行：
7 765 194 128 240 128 128 1282 1 72 2 32 2 61 4 2482 1 71 4 2402 5 7
YES YES NO NO NO
4 4192 168 1 12 1 41 1 1912 1 22 3 4
YES NO YES
1 12552 1 1
NO
对于任意两个正偶数 $$$h$$$ 和 $$$w$$$，定义 $$$f(h, w)$$$ 如下。
考虑一个 $$$h$$$ 行 $$$w$$$ 列的方格矩形，将每个方格视为一个顶点；如果两个方格有一条公共边，就在对应的两个顶点之间连一条无向边。由此得到一张 $$$h \times w$$$ 的网格图。
现在选择一个「子矩形」（即连续若干行与连续若干列交叉形成的方格区域），要求它不等于整个网格，删除其中的所有方格，以及与这些方格相连的所有边。
如果删除后剩余的网格图中存在一条恰好经过每个剩余顶点各一次的路径（起点和终点可以任意选择），则称这次删除是「合法」的。
$$$f(h, w)$$$ 表示 $$$h \times w$$$ 的网格中「合法」的删除方案的数量。两个删除方案不同，当且仅当它们所属的网格尺寸不同，或者删除的「子矩形」不同。
给定两个正偶数 $$$n$$$ 和 $$$m$$$，请你计算：
$$$$$$ \sum_{\substack{2 \le h \le n \\ h \text{ 为偶数}}} \sum_{\substack{2 \le w \le m \\ w \text{ 为偶数}}} f(h, w) $$$$$$
由于答案可能很大，请输出答案对 $$$998 \, 244 \, 353$$$ 取模后的结果。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \le T \le 2 \times 10^5$$$），表示测试用例的数量。对于每组测试用例：
对于每组测试用例，输出一行，包含一个整数，表示答案对 $$$998 \, 244 \, 353$$$ 取模后的结果。
42 22 44 46 6
8341531069
对于第一组测试用例，需要统计的网格尺寸只有 $$$2 \times 2$$$ 一种。$$$2 \times 2$$$ 的网格共有 $$$9$$$ 个「子矩形」，其中删除整个网格不被允许；而其余 $$$8$$$ 种删除均「合法」——删除后剩余的方格要么是三个方格组成的 L 形，要么是两个相邻的方格，都存在满足条件的路径。因此 $$$f(2, 2) = 8$$$，答案为 $$$8$$$。
对于第二组测试用例，需要统计的网格尺寸为 $$$2 \times 2$$$ 和 $$$2 \times 4$$$，答案为：$$$f(2, 2) + f(2, 4) = 8 + 26 = 34$$$。
对于第三组测试用例，需要统计的网格尺寸为 $$$2 \times 2$$$、$$$2 \times 4$$$、$$$4 \times 2$$$、$$$4 \times 4$$$，答案为：$$$f(2, 2) + f(2, 4) + f(4, 2) + f(4, 4) = 8 + 26 + 26 + 93 = 153$$$。
对于第四组测试用例，在第三组测试用例的基础上还需要统计 $$$2 \times 6$$$、$$$4 \times 6$$$、$$$6 \times 2$$$、$$$6 \times 4$$$、$$$6 \times 6$$$ 这五种尺寸，答案为：$$$153 + f(2, 6) + f(4, 6) + f(6, 2) + f(6, 4) + f(6, 6) = 153 + 52 + 196 + 52 + 196 + 420 = 1069$$$。
猪猪学院的魔法师小猪们正在研究一种全新的防御法阵，为小猪提供防御力。
共有 $$$n$$$ 只小猪排成一排，从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 只小猪的魔力值为 $$$a_i$$$。
对于区间 $$$[l, r]$$$（$$$1 \le l \le r \le n$$$）：
这个防御法阵有如下效果：如果第 $$$i$$$ 只小猪身处 $$$k$$$ 个互不相同$$$^{\text{∗}}$$$的「和谐区间」内，那么它能提供 $$$k$$$ 点防御力。
整个队列的防御力定义为所有小猪提供的防御力之和。
为了找到最佳阵型，魔法师小猪们想要尝试不同的队列，使防御力尽可能大。
给定一组小猪队列，请你计算它的防御力。
$$$^{\text{∗}}$$$两个区间 $$$[l_1,r_1]$$$ 和 $$$[l_2,r_2]$$$ 被认为互不相同，当且仅当 $$$l_1\ne l_2$$$ 或 $$$r_1\ne r_2$$$。
本题的输入包含多组测试用例。
第一行一个整数 $$$T$$$（$$$1 \leq T \leq 100$$$），表示测试用例的数量。对于每组测试用例：
保证所有测试用例的 $$$n$$$ 的总和不超过 $$$10^5$$$。
对于每组测试用例，输出一行，包含一个整数，表示该队列的防御力。
可以证明，在本题数据范围下，答案可以用 64 位有符号整数表示。
431 1 241 2 3 486 7 12 6 18 3 9 151212 1 18 6 30 5 10 15 3 21 14 28
101686147
对于第一组测试用例，小猪的魔力值依次为 $$$[1, 1, 2]$$$。第 $$$1$$$ 只小猪身处 $$$3$$$ 个「和谐区间」$$$[1, 1]$$$、$$$[1, 2]$$$、$$$[1, 3]$$$ 中，提供 $$$3$$$ 点防御力；第 $$$2$$$ 只小猪身处 $$$4$$$ 个「和谐区间」$$$[1, 2]$$$、$$$[1, 3]$$$、$$$[2, 2]$$$、$$$[2, 3]$$$ 中，提供 $$$4$$$ 点防御力；第 $$$3$$$ 只小猪身处 $$$3$$$ 个「和谐区间」$$$[1, 3]$$$、$$$[2, 3]$$$、$$$[3, 3]$$$ 中，提供 $$$3$$$ 点防御力。总防御力为 $$$3 + 4 + 3 = 10$$$。
对于第二组测试用例，小猪的魔力值依次为 $$$[1, 2, 3, 4]$$$。第 $$$1$$$ 只小猪身处 $$$4$$$ 个「和谐区间」$$$[1, 1]$$$、$$$[1, 2]$$$、$$$[1, 3]$$$、$$$[1, 4]$$$ 中，提供 $$$4$$$ 点防御力；第 $$$2$$$ 只小猪身处 $$$5$$$ 个「和谐区间」$$$[1, 2]$$$、$$$[1, 3]$$$、$$$[1, 4]$$$、$$$[2, 2]$$$、$$$[2, 4]$$$ 中，提供 $$$5$$$ 点防御力；第 $$$3$$$ 只小猪身处 $$$4$$$ 个「和谐区间」$$$[1, 3]$$$、$$$[1, 4]$$$、$$$[2, 4]$$$、$$$[3, 3]$$$ 中，提供 $$$4$$$ 点防御力；第 $$$4$$$ 只小猪身处 $$$3$$$ 个「和谐区间」$$$[1, 4]$$$、$$$[2, 4]$$$、$$$[4, 4]$$$ 中，提供 $$$3$$$ 点防御力。总防御力为 $$$4 + 5 + 4 + 3 = 16$$$。
对于第三组测试用例，第 $$$1$$$ 至第 $$$8$$$ 只小猪身处的「和谐区间」数量依次为 $$$7$$$、$$$7$$$、$$$12$$$、$$$15$$$、$$$15$$$、$$$14$$$、$$$10$$$、$$$6$$$，总防御力为 $$$7 + 7 + 12 + 15 + 15 + 14 + 10 + 6 = 86$$$。
对于第四组测试用例，第 $$$1$$$ 至第 $$$12$$$ 只小猪身处的「和谐区间」数量依次为 $$$3$$$、$$$13$$$、$$$16$$$、$$$18$$$、$$$19$$$、$$$18$$$、$$$15$$$、$$$15$$$、$$$14$$$、$$$9$$$、$$$4$$$、$$$3$$$，总防御力为 $$$3 + 13 + 16 + 18 + 19 + 18 + 15 + 15 + 14 + 9 + 4 + 3 = 147$$$。
有 $$$n$$$ 种材料，分别编号为 $$$1$$$ 到 $$$n$$$。材料 $$$i$$$ 的价格为 $$$c_i$$$。
材料之间的依赖关系构成一棵以材料 $$$1$$$ 为根的有根树：对于每个材料 $$$i$$$（$$$2 \le i \le n$$$），它恰有一个「下游材料」$$$f_i$$$（$$$1 \le f_i \lt i$$$）。如果 $$$f_y = x$$$，则称材料 $$$y$$$ 是材料 $$$x$$$ 的「上游材料」。
你需要依次处理 $$$q$$$ 次事件，事件分为以下两种：
「价格更新」会对此后的所有事件产生影响；每次「合成询问」相互独立：询问开始时你没有任何材料，询问过程中获得的材料不会保留到之后的事件中。
对于每次「合成询问」，输出获得一份材料 $$$u$$$ 的最小总花费。
第一行两个整数 $$$n$$$ 和 $$$q$$$（$$$2 \le n, q \le 10^{6}$$$），分别表示材料的种类数和事件的数量。
第二行 $$$n$$$ 个整数 $$$c_1, c_2, \ldots, c_n$$$（$$$0 \le c_i \le 10^{18}$$$），表示每种材料的初始价格。
第三行 $$$n - 1$$$ 个整数 $$$f_2, f_3, \ldots, f_n$$$（$$$1 \le f_i \lt i$$$），其中 $$$f_i$$$ 表示材料 $$$i$$$ 的「下游材料」。
接下来 $$$q$$$ 行，每行描述一个事件，格式为以下两种之一：
对于每次「合成询问」，输出一行，包含一个整数，表示该次询问的答案。
可以证明，答案不超过 $$$10^{18}$$$。
6 112 1 0 6 0 91 1 3 3 32 11 6 61 5 12 62 31 3 91 4 71 2 62 31 1 52 1
1 6 0 7 5
样例中，材料 $$$2$$$、$$$3$$$ 的「下游材料」均为材料 $$$1$$$，材料 $$$4$$$、$$$5$$$、$$$6$$$ 的「下游材料」均为材料 $$$3$$$。
对于第一次「合成询问」，可以直接花费 $$$c_1 = 2$$$ 购买材料 $$$1$$$；也可以花费 $$$1$$$ 购买材料 $$$2$$$、花费 $$$0$$$ 购买材料 $$$3$$$，随后将二者免费合成为材料 $$$1$$$。后者总花费为 $$$1 + 0 = 1$$$，因此答案为 $$$1$$$。
对于第二次「合成询问」，此前的两次「价格更新」已将 $$$c_6$$$、$$$c_5$$$ 分别修改为 $$$6$$$、$$$1$$$。材料 $$$6$$$ 没有「上游材料」，无法通过「合成」获得，只能花费 $$$6$$$ 直接购买，因此答案为 $$$6$$$。
对于第三次「合成询问」，直接花费 $$$c_3 = 0$$$ 购买材料 $$$3$$$ 即可，因此答案为 $$$0$$$。
对于第四次「合成询问」，此时 $$$c_3 = 9$$$、$$$c_4 = 7$$$、$$$c_5 = 1$$$、$$$c_6 = 6$$$。最优方案是花费 $$$1$$$ 购买材料 $$$5$$$、花费 $$$6$$$ 购买材料 $$$6$$$，再将二者免费合成为材料 $$$3$$$，总花费 $$$1 + 6 = 7$$$，小于直接购买的 $$$9$$$。可以证明不存在总花费更小的方案，因此答案为 $$$7$$$。
对于第五次「合成询问」，此时 $$$c_1 = 5$$$；若通过「合成」获得材料 $$$1$$$，需要一份材料 $$$2$$$ 和一份材料 $$$3$$$，至少花费 $$$6 + 7 = 13$$$，大于直接购买的 $$$5$$$，因此答案为 $$$5$$$。