题目描述

2026 丙午马年，某马术俱乐部有 \(n\) 匹马排成一排，编号 \(1, 2, \ldots, n\)。俱乐部设有 \(m\) 个饲料槽，编号 \(1, 2, \ldots, m\)。初始时，第 \(i\) 匹马被分配到第 \(a_i\) 号饲料槽（\(a_i = 0\) 表示该马暂未分配）。每个饲料槽有一个投喂量计数 \(b_i\)，初始均为 \(0\)。

你需要依次执行 \(q\) 次操作，操作有两种类型：

• ① 给定 \(l, r, x\)，将编号在 \([l, r]\) 内的所有马重新分配到第 \(x\) 号饲料槽。
• ② 给定 \(l, r, x\)，对编号在 \([l, r]\) 内的每匹马，若该马已分配饲料槽（即 \(a_i \neq 0\)），则向其饲料槽投喂 \(x\) 单位饲料（即 \(b_{a_i}\) 加上 \(x\)）。

请输出所有操作执行完毕后，每个饲料槽的总投喂量。

输入格式

本题有多组测试数据。第一行输入 \(T\ (1 \le T \le 5)\)，表示数据组数。

对于每组数据：

第一行输入三个正整数 \(n, m, q\ (1 \le n, m, q \le 2 \times 10^6)\)。

第二行输入 \(n\) 个非负整数 \(a_1, a_2, \ldots, a_n\ (0 \le a_i \le m)\)。

接下来 \(q\) 行，每行输入四个正整数 \(\text{opt}, l, r, x\ (\text{opt} \in \{1, 2\}, \ 1 \le l \le r \le n, \ 1 \le x \le m)\)，意义如题目描述所述。

保证所有数据的 \(n\) 的和不超过 \(2 \times 10^6\)， \(q\) 的和不超过 \(2 \times 10^6\)。

输出格式

对于每组数据，输出一行 \(m\) 个整数，第 \(i\) 个整数表示第 \(i\) 个饲料槽的总投喂量 \(b_i\)，相邻整数用空格隔开。

样例输入

1
6 4 5
1 0 3 2 4 1
2 1 4 3
1 2 5 1
2 1 6 2
1 3 4 4
2 2 5 4

样例输出

23 3 3 8