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 > 0$ (for every $i \in [1, k]$) and $|cnt_i - cnt_j| \le$ (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$.

Input

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.

Output

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.

见题面 Input 部分

见题面 Output 部分