CF1476G.Minimum Difference

You are given an integer array $a$ of size $n$.

You have to perform $m$ queries. Each query has one of two types:

• "$1$ $l$ $r$ $k$" — calculate the minimum value $dif$ such that there are exist $k$ distinct integers $x_1, x_2, \dots, x_k$ such that $cnt_i \gt 0$ (for every $i \in [1, k]$) and $|cnt_i - cnt_j| \le dif$ (for every $i \in [1, k], j \in [1, k]$), where $cnt_i$ is the number of occurrences of $x_i$ in the subarray $a[l..r]$. If it is impossible to choose $k$ integers, report it;
• "$2$ $p$ $x$" — assign $a_{p} := x$.

给你一个长度为 $n$ 的整数数组 $a$。

你需要执行 $m$ 个查询。每个查询为以下两种类型之一：

• “$1$ $l$ $r$ $k$” —— 计算最小的值 $dif$，使得存在 $k$ 个互不相同的整数 $x_1, x_2, \dots, x_k$，满足：对每个 $i \in [1, k]$，$cnt_i > 0$；且对任意 $i, j \in [1, k]$，均有 $|cnt_i - cnt_j| \le dif$。其中 $cnt_i$ 表示 $x_i$ 在子数组 $a[l..r]$ 中的出现次数。若无法选出 $k$ 个这样的整数，则报告该情况；
• “$2$ $p$ $x$” —— 将 $a_{p}$ 赋值为 $x$。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the size of the array $a$ and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$).

Next $m$ lines contain queries (one per line). Each query has one of two types:

• "$1$ $l$ $r$ $k$" ($1 \le l \le r \le n; 1 \le k \le 10^5$)
• "$2$ $p$ $x$" ($1 \le p \le n; 1 \le x \le 10^5$).

It's guaranteed that there is at least one query of the first type.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^5$）——分别表示数组 $a$ 的大小和查询的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）。

接下来的 $m$ 行每行包含一个查询。每个查询为以下两种类型之一：

• “$1$ $l$ $r$ $k$”（$1 \le l \le r \le n$；$1 \le k \le 10^5$）
• “$2$ $p$ $x$”（$1 \le p \le n$；$1 \le x \le 10^5$）。

保证至少存在一个第一类查询。

For each query of the first type, print the minimum value of $dif$ that satisfies all required conditions, or $-1$ if it is impossible to choose $k$ distinct integers.

对于每个第一类查询，输出满足所有要求条件的 $dif$ 的最小值；如果无法选出 $k$ 个互不相同的整数，则输出 $-1$。