\(n\) бүтін саннан тұратын \(a\) жиымы берілген. \((x,y)\) параметрларымен келесідей операцияларды шексіз жасауға болады:

• Екі индекс \(i\), \(j\) \((1 \leq i, j \leq n, i \neq j)\) және бір нақты сан \(t\) таңдау.

• \(a_i\) санының мәнінен \(x \cdot t\) азайту және \(a_j\) санының мәнінен \(y \cdot t\) азайту.

Осы операцияның бағасы \(t\) болады. Сізге \(m\) сұрау берілген. Әр сұраудың екі түрі болады:

• \(1\) \(\text{pos} \ v\) — \(a_{\text{pos}}\) мәнін \(\text{v}\) қылу.

• \(2\) \(l \ r \ x \ y\) — \((x,y)\) параметрларымен \(a_{l}, a_{l + 1}, ..., a_{r}\) сандарының мәндерін нөл немесе нөлден төмен қылу үшін ең аз қанша баға кетіру керек екенін есептеу.

Input

Бірінші жолда \(n\) \((2 \leq n \leq 2 \cdot 10^5)\) және \(m\) \((1 \leq m \leq 2 \cdot 10^5)\) бүтін сандары — жиымдағы сандардың саны және сұраулардың саны берілген.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) — \(a\) жиымының элементтері берілген.

Келесі \(m\) жолдың әрқайсысы екі түрдің біреуі болатын сұрауларды сипаттайды:

• Түрі \(1\) болатын сұрау үшін: жолдың пішімі \(1\) \(pos\) \(v\) \((1 \leq pos \leq n)\), \((1 \leq v \leq 10^9)\) болады.

• Түрі \(2\) болатын сұрау үшін: жолдың пішімі \(2\) \(l\) \(r\) \(x\) \(y\) \((1 \leq l < r \leq n)\), \((1 \leq x, y \leq 10^9)\) болады.

Output

Екінші түрлі әр сұрау үшін сандардың мәндерін нөл немесе нөлден төмен қылу үшін ең аз қанша баға кетіру керек екенін шығарыңыз. Сіздің жауабыңыз дұрыс болып қабылданады, егер оның абсолютті немесе қатысты қателігі \(10^{-9}\) мәнінен аспаса.

Ресми түрде, сіздің жауабыңыз \(e\), ал қазылардың жауабы \(f\) дейік. Сіздің жауабыңыз дұрыс деп саналады, тек егер \(\frac{|e-f|}{max(1, |f|)} \le 10^{-9}\) орындалса.

Sample Input 1

10 8
3 22 22 13 13 13 1 10 5 1
2 7 9 3 17
2 6 7 30 28
2 5 8 14 30
1 6 67
2 5 8 14 30
2 6 9 788946788 12
2 5 10 8 8
2 7 10 1 25

Sample Output 1

0.800000000000
0.433333333333
0.840909090909
2.233333333333
0.000000105204
8.375000000000
0.653846153846