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*<sub class="lower-index">*i*</sub> and then pours there exactly *x*<sub class="lower-index">*i*</sub> liters of mercury. 1.  Let's consider all the ways to add *v*<sub class="lower-index">*i*</sub> 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.
The first line contains two integers *n* and *q* (1 ≤ *n*, *q* ≤ 10<sup class="upper-index">5</sup>) — the number of tubes ans the number of experiment steps. The next line contains *n* space-separated integers: *h*<sub class="lower-index">1</sub>, *h*<sub class="lower-index">2</sub>, ..., *h*<sub class="lower-index">*n*</sub> (0 ≤ *h*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), where *h*<sub class="lower-index">*i*</sub> 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*<sub class="lower-index">*i*</sub> *x*<sub class="lower-index">*i*</sub>" means an action of the first type (1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ *n*; 0 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). -  A line of form "2 *v*<sub class="lower-index">*i*</sub>" means an action of the second type (1 ≤ *v*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">15</sup>). 
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.
# LUOGU_RID: 123441055
class Node:
    def __init__(self, start, end, value):
        self.start = start
        self.end = end
        self.value = value
        self.left = None
        self.right = None


class WeightedSegmentTree:
    def __init__(self, nums):
        self.root = self.build_tree(nums, 0, len(nums) - 1)

    def build_tree(self, nums, start, end):
        if start == end:
            return Node(start, end, nums[start])
        mid = (start + end) // 2
        left = self.build_tree(nums, start, mid)
        right = self.build_tree(nums, mid + 1, end)
        root = Node(start, end, left.value + right.value)
        root.left = left
        root.right = right
        return root

    def query(self, start, end, node=None):
        if node is None:
            node = self.root
        if start > node.end or end < node.start:
            return 0
        if start <= node.start and end >= node.end:
            return node.value
        return self.query(start, end, node.left) + self.query(start, end, node.right)

    def update(self, index, value, node=None):
        if node is None:
            node = self.root
        if index < node.start or index > node.end:
            return
        if index == node.start and index == node.end:
            node.value = value
            return
        self.update(index, value, node.left)
        self.update(index, value, node.right)
        node.value = node.left.value + node.right.value





n,m = map(int,input().split())   #输入操作次数和试管数
data = input("请输入试管数据（以空格分隔）：").split()
numbers = [int(x) for x in data]
nums = sorted(numbers)

while(m>0):
    s = int(input("请输入选择的操作序号："))
    if s == 1:
        p=numbers
        exchange=int(input("请输入要替换的试管编号："))
        changed=int(input("请输入替换毫升数："))
        tree = WeightedSegmentTree(p)
        tree.update(exchange-1,changed)
        nums2=[]
        for j in range(n):
            h=tree.query(0, j)-tree.query(0, j-1)
            nums2.append(h)
        nums=sorted(nums2)

            
    if s == 2:
        tree = WeightedSegmentTree(nums)
        r = int(input("请输入要加入的水的体积："))
        result=[]
        for i in range(n):
            a=tree.query(0, i)
            b=int(nums[i])
            if ((r+a)/(i+1)) >= b:
                d=(r+a)/(i+1)
                result.append(d)
        result=sorted(result)      #对比较结果进行从小到大排序
        print('%.5f'% result[0])

        
    m-=1
