{"raw_statement":[{"iden":"statement","content":"R 国的历史非常悠久。\n\nR 国有 $n$ 个城市，国内有 $C$ 个党派，分别记为 $1,2,\\dots,C$。由于 R 国的版图非常长，这 $n$ 个城市的位置可以近似为坐标轴上的 $n$ 个点。在历史的最初，记载了第 $i$ 个城市归属党派 $c_i$，城中有数量为 $a_i$ 的军队。\n\nR 国的历史上，经常发生以下三种事件：\n\n1. 党派 $y$ 进行了一次游说，使城市 $l$ 到城市 $r$ 的所有归属党派 $x$ 的城市全部归属了 $y$。\n\n2. 党派 $x$ 进行了一次征兵，使城市 $l$ 到城市 $r$ 的所有归属党派 $x$ 的城市中的军队数量增加了 $v$。\n\n3. 城市 $l$ 到城市 $r$ 之间的所有城市爆发了战争。这场战争的规模可以描述为两地之间的所有城市中的军队数量之和。注意战争不一定发生在不同党派之间，归属同一个党派的一些城市内部也可能发生内战。由于 R 国的医护系统足够先进，战争不会造成军队数量的减少。\n\n小 N 是一个喜欢历史的女孩子，最近她想整理一下 R 国的战争史，特别是每场战争的规模。但是由于 R 国的历史实在太长了，她用纸和笔进行运算实在力不从心。于是她找到了你，希望你写一个程序，统计出 R 国历史上所有战争的规模。"},{"iden":"input","content":"输入的第一行是三个正整数 $n,q,C$，分别表示城市的个数，事件的个数，和 R 国国内党派的个数。\n\n接下来一行有 $n$ 个正整数 $a_1,a_2,\\dots,a_n$，表示每个城市内初始的军队数。\n\n接下来一行有 $n$ 个正整数 $c_1,c_2,\\dots,c_n$，表示每个城市初始归属的党派。\n\n接下来 $q$ 行，每行 $3$ 到 $5$ 个正整数，表示一次事件：\n\n第一个正整数 $\\mathit{op}$ 表示事件的类型。$\\mathit{op}=1,2,3$ 分别表示【题目描述】中所述的游说，征兵和战争事件。\n\n对于每个游说事件，接下来有 $4$ 个正整数 $l,r,x,y$，意义见【题目描述】。\n\n对于每个征兵事件，接下来有 $4$ 个正整数 $l,r,x,v$，意义见【题目描述】。\n\n对于每个战争事件，接下来有 $2$ 个正整数 $l,r$，意义见【题目描述】。"},{"iden":"output","content":"对于每个战争事件，输出一行一个整数，表示此次战争的规模。"},{"iden":"note","content":"**【样例 1 解释】**\n\n最初，五个城市的军队数量分别为 $1, 2, 4, 8, 16$，归属的党派分别为 $1, 2, 3, 2, 3$。\n\n发生的事件依次为：\n- 党派 $2$ 尝试在城市 $2, 3, 4$ 征兵，归属党派 $2$ 的城市 $2, 4$ 各增加了 $32$ 军队。\n- 城市 $1$ 和 $4$ 之间的所有城市爆发了战争，规模为 $1 + 34 + 4 + 40 = 79$。\n- 党派 $1$ 在城市 $1, 2, 3, 4, 5$ 进行了一次游说，使得原本归属党派 $3$ 的城市 $3, 5$ 归属了党派 $1$。\n- 党派 $1$ 尝试在城市 $2, 3, 4, 5$ 征兵，归属党派 $1$ 的城市 $3, 5$ 各增加了 $64$ 军队。\n- 城市 $2$ 和 $4$ 之间的所有城市爆发了战争，规模为 $34 + 68 + 40 = 142$。\n- 党派 $3$ 尝试在城市 $1, 2, 3$ 征兵，但是党派 $3$ 现在不拥有任何城市，因此并没有成功征兵。\n- 城市 $3$ 和 $5$ 之间的所有城市爆发了战争，规模为 $68 + 40 + 80 = 188$。\n\n因此你的程序应该依次输出 $79, 142, 188$。\n\n**【数据规模与约定】**\n\n对于全部数据，$1 \\leq n, q\\leq 2.5 \\times 10^5$，$1 \\leq a_i, v \\leq 10^8$，$1 \\leq c_i, x, y \\leq C$。\n\n具体的数据规模与约定见下表。\n\n| 测试点编号 |    $n,q\\leq $     |     $C\\leq $      |               特殊约定               |\n| :--------: | :---------------: | :---------------: | :----------------------------------: |\n|    $1$     |       $20$        |       $20$        |                                      |\n|    $2$     |       $50$        |       $50$        |                                      |\n|    $3$     |       $300$       |       $300$       |                                      |\n|    $4$     |      $5000$       |      $5000$       |                                      |\n|    $5$     |      $10^5$       |       $10$        |                                      |\n|    $6$     | $1.5 \\times 10^5$ |       $10$        |                                      |\n|    $7$     |  $2 \\times 10^5$  |       $10$        |                                      |\n|    $8$     | $2.5 \\times 10^5$ |       $10$        |                                      |\n|    $9$     | $1.5 \\times 10^5$ | $1.5 \\times 10^5$ |    对于所有操作，保证 $l=1,r=n$。    |\n|    $10$    | $2.5 \\times 10^5$ | $2.5 \\times 10^5$ |    对于所有操作，保证 $l=1,r=n$。    |\n|    $11$    | $1.5 \\times 10^5$ | $1.5 \\times 10^5$ | 对于所有操作 $1,2$，保证 $l=1,r=n$。 |\n|    $12$    |  $2 \\times 10^5$  |  $2 \\times 10^5$  | 对于所有操作 $1,2$，保证 $l=1,r=n$。 |\n|    $13$    | $2.5 \\times 10^5$ | $2.5 \\times 10^5$ | 对于所有操作 $1,2$，保证 $l=1,r=n$。 |\n|    $14$    | $1.5 \\times 10^5$ | $1.5 \\times 10^5$ |         保证不存在操作 $1$。         |\n|    $15$    | $2.5 \\times 10^5$ | $2.5 \\times 10^5$ |         保证不存在操作 $1$。         |\n|    $16$    |      $10^5$       |      $10^5$       |                                      |\n|    $17$    | $1.5 \\times 10^5$ | $1.5 \\times 10^5$ |                                      |\n|    $18$    |  $2 \\times 10^5$  |  $2\\times 10^5$   |                                      |\n|    $19$    | $2.5 \\times 10^5$ | $2.5 \\times 10^5$ |                                      |\n|    $20$    | $2.5 \\times 10^5$ | $2.5 \\times 10^5$ |                                      |"}],"translated_statement":null,"sample_group":[["5 7 3\n1 2 4 8 16\n1 2 3 2 3\n2 2 4 2 32\n3 1 4\n1 1 5 3 1\n2 2 5 1 64\n3 2 4\n2 1 3 3 128\n3 3 5\n","79\n142\n188\n"],["样例 2 见附件 military2.in\n本组数据满足测试点 4 的限制。","样例 2 见附件 military2.ans"],["样例 3 见附件 military3.in\n本组数据满足测试点 14 的限制。","样例 3 见附件 military3.ans"],["样例 4 见附件 military4.in\n本组数据满足测试点 18 的限制。","样例 4 见附件 military4.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}