3. 团子大家族

【题目背景】

在光坂高中的「团子大家族」社团记录系统中，每个社团成员（对应序列位置）有两个核心属性：心意值（代表对社团的投入程度）和所属社团标识（区分不同的校园社团）。系统需要实时维护成员的属性信息，并响应社团活动中特定的心意值加权求和查询。

【题目描述】

给定一个长度为 $n$ 的序列，每个位置 $i$ 对应一位光坂高中的学生，拥有两个属性：$a_i$（心意值）和 $f_i$（所属社团标识）。

定义 $cnt(k)$ 为整个序列中满足 $f_j = k$ 的下标 $j$ 的数量（即全校中属于社团 $k$ 的学生总数）。

你需要维护 $m$ 次操作，操作分为以下三类：

1. 区间心意值增量（1 l r x）：对于所有 $i \in [l, r]$，更新 $a_i \leftarrow a_i + x$（对应社团活动后，指定区间的学生心意值增加 $x$）。

2. 单点社团修改（2 p v）：更新 $f_p \leftarrow v$（对应编号为 $p$ 的学生从原社团转入编号为 $v$ 的社团）。

3. 社团心意加权求和（3 l r k）：计算并输出 $\displaystyle \text{Ans} = \sum_{i=l}^r [f_i = k] \cdot (a_i \cdot cnt(k))$，其中 $[f_i = k]$ 为艾弗森括号（若该学生属于社团 $k$ 则为 1，否则为 0）。该查询用于统计指定区间内某社团成员的心意值总和乘以该社团的总人数，是社团评优的核心计算依据。

【输入格式】

第一行输入两个整数 $n, m$，分别表示学生总数和操作次数。

第二行输入 $n$ 个整数，依次为 $a_1, a_2, \dots, a_n$，表示每位学生的初始心意值。

第三行输入 $n$ 个整数，依次为 $f_1, f_2, \dots, f_n$，表示每位学生的初始所属社团标识。

接下来 $m$ 行，每行描述一个操作：

- 若为区间心意值增量操作，格式为 `1 l r x`；

- 若为单点社团修改操作，格式为 `2 p v`；

- 若为社团心意加权求和操作，格式为 `3 l r k`。

【输出格式】

对于每个社团心意加权求和操作（操作 3），输出一行一个整数，表示对应的查询答案。

【样例输入】

5 5
1 2 3 4 5
1 2 1 2 1
1 1 5 1
2 3 2
3 1 5 1
3 1 5 2
3 2 4 2

【样例输出】

16
36
36

【数据规模与约定】

对于 $30 \%$ 的数据，保证 $1 \le n \le 1000$

$1 \le n, m \le 10^5$

$1 \le a_i, f_i, x, k, v \le n$，$1 \le l \le r \le n$，$1 \le p \le n$

$\textbf{注意，此题的内存限制为 32MB}$.

大样例

【来源】

To_Carpe_Diem