Задан целочисленный массив \(a\) размера \(n\).
Вам предстоит выполнить \(m\) запросов. Каждый запрос имеет один из двух типов:
- «\(1\) \(l\) \(r\) \(k\)» — вычислите минимальное значение \(dif\) такое, что существуют \(k\) различных целых чисел \(x_1, x_2, \dots, x_k\) таких, что \(cnt_i > 0\) (для каждого \(i \in [1, k]\)) и \(|cnt_i - cnt_j| \le dif\) (для каждого \(i \in [1, k], j \in [1, k]\)), где \(cnt_i\) — это число вхождений \(x_i\) в подмассив \(a[l..r]\). Если невозможно выбрать \(k\) целых чисел, сообщите об этом;
- «\(2\) \(p\) \(x\)» — присвоить \(a_{p} := x\).
Выходные данные
Для каждого запроса первого типа выведите минимальное значение \(dif\), удовлетворяющее всем необходимым условиям, или \(-1\), если невозможно выбрать \(k\) различных целых чисел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12 11
2 1 1 2 1 1 3 2 1 1 3 3
1 2 10 3
1 2 11 3
2 7 2
1 3 9 2
1 1 12 1
1 1 12 4
2 12 4
1 1 12 4
2 1 5
1 3 12 2
1 1 4 3
|
5
4
1
0
-1
5
0
1
|