CF431E.Chemistry Experiment

One day two students, Grisha and Diana, found themselves in the university chemistry lab. In the lab the students found n test tubes with mercury numbered from 1 to n and decided to conduct an experiment.

The experiment consists of q steps. On each step, one of the following actions occurs:

1. Diana pours all the contents from tube number p__i and then pours there exactly x__i liters of mercury.
2. Let's consider all the ways to add v__i liters of water into the tubes; for each way let's count the volume of liquid (water and mercury) in the tube with water with maximum amount of liquid; finally let's find the minimum among counted maximums. That is the number the students want to count. At that, the students don't actually pour the mercury. They perform calculations without changing the contents of the tubes.

Unfortunately, the calculations proved to be too complex and the students asked you to help them. Help them conduct the described experiment.

一天，两名学生格里沙和黛安娜在大学化学实验室里相遇。在实验室中，他们发现了 $n$ 支装有水银的试管，编号从 $1$ 到 $n$，并决定进行一项实验。

该实验共包含 $q$ 个步骤。在每个步骤中，会发生以下两种操作之一：

1. 黛安娜将编号为 $p_i$ 的试管中的全部液体倒出，然后向其中恰好倒入 $x_i$ 升水银；
2. 考虑所有将 $v_i$ 升水加入这些试管的方式；对每一种加水方式，计算含水试管中液体（水与水银）体积的最大值；最后，在所有这些最大值中找出最小的那个值。这个最小值即为学生们希望计算的结果。注意：在此步骤中，学生们并不会实际倾倒水银，而仅通过计算得出结果，且不改变各试管中液体的实际含量。

不幸的是，这些计算过于复杂，学生们请求你协助完成。请帮助他们完成上述实验。

The first line contains two integers n and q (1 ≤ n, q ≤ 105) — the number of tubes ans the number of experiment steps. The next line contains n space-separated integers: _h_1, _h_2, ..., h__n (0 ≤ h__i ≤ 109), where h__i is the volume of mercury in the і-th tube at the beginning of the experiment.

The next q lines contain the game actions in the following format:

• A line of form "1 p__i x__i" means an action of the first type (1 ≤ p__i ≤ n; 0 ≤ x__i ≤ 109).
• A line of form "2 v__i" means an action of the second type (1 ≤ v__i ≤ 1015).

It is guaranteed that there is at least one action of the second type. It is guaranteed that all numbers that describe the experiment are integers.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$）—— 分别表示试管的数量和实验步骤的数量。
下一行包含 $n$ 个用空格分隔的整数：$h_1,\ h_2,\ \dots,\ h_n$（$0 \leq h_i \leq 10^9$），其中 $h_i$ 表示实验开始时第 $i$ 根试管中水银的体积。

接下来的 $q$ 行描述实验操作，格式如下：

• 形如 1 p_i x_i 的行表示第一类操作（$1 \leq p_i \leq n$；$0 \leq x_i \leq 10^9$）。
• 形如 2 v_i 的行表示第二类操作（$1 \leq v_i \leq 10^{15}$）。

保证至少存在一个第二类操作。保证所有描述该实验的数值均为整数。

For each action of the second type print the calculated value. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

对于每个第二类操作，输出计算得到的值。若答案的相对误差或绝对误差不超过 $10^{-4}$，则视为正确。