给定一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$，以及整数 $k$ 和 $m$。对数组执行 $m$ 次以下操作：

• 选择 $i_1, i_2, \dots, i_k$ —— 数组 $a$ 中 $k$ 个最大元素的位置。如果两个元素相等，则在数组中出现较早的元素被视为较大。
• 将 $a_{i_1}, a_{i_2}, \dots, a_{i_k}$ 减 1。

对于 $x$ 从 $1$ 到 $n$，令 $F_{m,k}(x)$ 表示在对数组 $a$ 应用 $m$ 次参数为 $k$ 的操作后，数组中第 $x$ 小的顺序统计量的值。对于数组 $a_1, a_2, \dots, a_n$，第 $x$ 小的顺序统计量是指将数组 $a$ 按非递减顺序排序后，处于第 $x$ 个位置的元素。

对于所有满足 $1 \le l \le r \le n$ 的 $l, r$，令 $S_{m,k}(l, r)$ 表示 $F_{m,k}(x)$ 对于所有从 $l$ 到 $r$ 的整数 $x$ 的和。更正式地： $$S_{m,k}(l, r) = \sum_{x=l}^{r} F_{m,k}(x)$$

给定整数 $m_0$ 和 $k_0$。你需要计算所有 $x$ 从 $1$ 到 $n$ 的 $F_{m_0,k_0}(x)$ 的值。之后，你需要处理 $q$ 个查询。第 $j$ 个查询 ($1 \le j \le q$) 可以是以下三种类型之一：

1. 计算 $F_{m_j,k_j}(x_j)$ 的值。
2. 将 $a_{p_j}$ 的值修改为 $v_j$。
3. 计算 $S_{m_j,k_j}(l_j, r_j)$ 的值。

函数 $F$ 和 $S$ 的所有计算每次都是独立进行的，不会改变数组。第二类查询对数组的修改会保留在后续查询中。

输入格式

第一行包含四个整数 $n, m_0, k_0$ 和 $q$ ($1 \le n \le 200\,000, 0 \le m_0 \le 10^9, 1 \le k_0 \le n, 0 \le q \le 200\,000$) —— 数组 $a$ 的长度；操作次数；每次操作中减少的最大元素个数；以及查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9, 1 \le i \le n$) —— 数组 $a$ 的元素。

接下来的 $q$ 行包含查询。在第 $j$ 个查询中，第一个数字是 $t_j$ ($1 \le t_j \le 3$) —— 第 $j$ 个查询的类型。

• 如果 $t_j = 1$，则下一行包含三个整数 $m_j, k_j$ 和 $x_j$ ($0 \le m_j \le 10^9, 1 \le k_j, x_j \le n$) —— 第一类查询的参数。
• 如果 $t_j = 2$，则下一行包含两个整数 $p_j$ 和 $v_j$ ($1 \le p_j \le n, -10^9 \le v_j \le 10^9$) —— 第二类查询的参数。
• 如果 $t_j = 3$，则下一行包含四个整数 $m_j, k_j, l_j$ 和 $r_j$ ($0 \le m_j \le 10^9, 1 \le k_j, l_j, r_j \le n, l_j \le r_j$) —— 第三类查询的参数。

输出格式

第一行输出 $n$ 个整数 $F_{m_0,k_0}(1), F_{m_0,k_0}(2), \dots, F_{m_0,k_0}(n)$。

然后，对于每个第一类查询，在单独的一行中输出 $F_{m_j,k_j}(x_j)$ 的值；对于每个第三类查询，输出 $S_{m_j,k_j}(l_j, r_j)$ 的值 —— 即第 $j$ 个查询的答案。

子任务

样例

输入 1

8 3 2 16
3 1 2 -1 0 2 -1 4
3 3 2 2 6
1 3 2 4
3 4 5 3 5
1 4 5 6
2 5 -1
2 6 3
1 3 2 1
1 3 2 3
1 3 2 4
1 3 2 8
1 0 5 6
2 1 5
3 1 3 7 8
3 2 3 5 8
3 3 3 4 7
3 4 3 4 7

输出 1

-1 -1 0 1 1 1 1 2
2
1
-4
-1
-1
-1
1
2
3
7
8
4
2