[Wannafly冬令营2018Day5]Division(困难版)

内存限制：256 MB 时间限制：5000 ms

你有一个数列 $a_1, a_2, \dots, a_n$。你可以进行这样的一次操作，每次选择数列中其中一个数然后将其除 $2$ 下取整，也就是选择一个数 $a_i$，变成 $\lfloor a_i/2 \rfloor$。

一共有 $q$ 个询问，每次你考虑数列中 $[l,r]$ 这段数，即 $a_l, a_{l+1}, a_{l+2}, \dots, a_r$，对这些数字进行不超过 $k$ 次操作，这些数字的总和最小值可能是多少。

第一行两个整数 $n, q(1\leq n\leq 10^5, 1\leq q\leq 5*10^5)$，表示数字个数和询问个数。

接下来 $n$ 行，一共 $n$ 个整数 $a_1,a_2,\dots, a_n$，保证 $1\leq a_i \leq 10^9$。

接下来 $q$ 行，每行三个正整数 $l, r, k$ 表示每个询问是 $[l,r]$，然后一共操作不超过 $k$ 次，保证 $1\leq l\leq r\leq n, 0\leq k\leq 10^9$。

一共 $q$ 行，每行一个数字表示答案。

C1679 [Wannafly冬令营2018Day5]Division(困难版)