a[0] = 0;
bool have_even = 0;
for(int i = l; i <= r; i++)if (a[i] % 2 == 0 && a[i] > 0 ) have_even = 1;
if (have_even)
{
index = 0;
for(int i = l; i <= r; i++)
{
if (a[index] < a[i] && a[i] % 2 == 0) index = i;
}
a[index] /= 2;
}else
{
index = l;
for(int i = l; i <= r; i++)
{
if (a[index] < a[i]) index = i;
}
if (a[index] > 0) a[index] = (a[index] - 1) / 2;
}
You want to know the maximum value of interval [l, r][l, \ r][l, r] after kkk operations.The first line contains two positive integers n, qn, \ qn, q(1≤n≤104,1≤q≤1051\le n \le 10^4, 1\le q \le 10^51≤n≤104,1≤q≤105). The second line contains nnn integers a1, a2,…, ana_1, \ a_2, \dots, \ a_na1, a2,…, an(1≤ai≤1091 \le a_i \le 10^91≤ai≤109) .Each of the next qqq lines contains three integers l, r, kl,\ r,\ kl, r, k(1≤l≤r≤n,1≤k≤1091\le l\le r \le n, 1 \le k \le 10^91≤l≤r≤n,1≤k≤109) .
For each test case, output the maximum number.
3 2
1 2 3
1 2 1
1 3 31
1