【题目背景】

有 $n$ 个宝石，标号为 $1 \sim n$ 。第 $i$ 个宝石的颜色是 $c_i$，价值是 $v_i$ 。

你需要支持两种操作：

• $1$ $x$ $c$ $v$ ，将 $x$ 这个宝石的颜色和价值换成 $c$ 和 $v$

• $2$ $s$ $k$ ，从 $s$ 位置开始取宝石，每次可以取或跳过这个宝石，然后继续考虑下一个或者结束。要求跳过的宝石不能超过 $k$ 个，并且取的宝石颜色两两不同，并且价值最大。

【输入格式】

输入的第一行为 $n, m$ 。

接下来 $n$ 行，每行两个整数 $c_i$ , $v_i$ $(1 \le c_i \le n, 1 \le v_i \le 10^{9} )$。

接下来 $m$ 行，每行一个上述操作，保证 $1 \le x, c, s \le n, 1 \le v \le 10^{9}$ 。

【输出格式】

对于每个查询操作输出答案。

【样例】

见选手目录下的 $\rm gem1/gem2.in$ 与 $\rm gem1/gem2.ans$。

【数据范围】

本题不采用子任务评测。

对于 $15\%$ 的数据，有 $n, m \le 100$。

对于 $30\%$ 的数据，有 $n, m \le 1000$。

对于 $55\%$ 的数据，有 $n, m \le 50000$。

另有 $15\%$ 的数据，有 $k = 0$。

对于 $100\%$ 的数据，有 $1 \le n, m \le 2 \times 10^{5} , 0 \le k \le 10$。

请注意常数因子带来的影响。