该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

雨

(rain.cpp 1s/512MB)

题目背景

LTF 卷的速度 Faster Than Light。

题目描述

机房里有 $2^n$ 个人，每个人有一个幸福指数 $a_i$，保证 $a_i$ 是自然数。

外面正下着大雨，没有人离开机房。LTF 打算掀起一场卷王狂潮！卷王狂潮总共会持续 $n$ 轮，每一轮开始时，所有未被淘汰的人会按原本的顺序重新编号，然后第 $2i-1$ 个和第 $2i$ 个人开始相互竞争，幸福指数更小的人会被淘汰（如果幸福指数相同编号大的人被淘汰），胜出的人的幸福指数会减去被淘汰的人的幸福指数，然后进入下一轮的角逐。

最终胜出的人会加冕为“卷怪”。LTF 是第一个人，他有金手指，每使用一次金手指就可以增加一点幸福指数。LTF 想成为卷怪，为此他已经偷偷地打开了完全隐私保护，但他又不想使用过多次金手指。你能告诉他他最少使用多少次金手指就能加冕为“卷怪”吗？

当然，每个人的幸福指数不是一成不变的。在接下来的 $m$ 天，机房众人的幸福指数会有所变化。具体地，第 $i$ 天开始时，编号处于 $[l_i,r_i]$ 中的人的幸福指数会增加 $x_i$。对于每个 $i$，你都需要告诉 LTF，如果他想在第 $i$ 天掀起卷王狂潮并加冕为“卷怪”，他当天最少需要使用多少次金手指。注意，LTF 只是在做计划，并没有真的掀起卷王狂潮让众人的幸福指数因为卷而改变。

输入格式

第一行包含两个整数 $n,m$，表示机房里总共有 $2^n$ 个人，

第二行共有 $2^n$ 个整数，表示每个人的幸福指数。其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个人的幸福指数。LTF 是第一个人。

接下来 $m$ 行，第 $i$ 行包含三个整数，依次为 $l_i,r_i,x_i$。

输出格式

共 $m$ 行，每行包含一个整数，表示这天 LTF 最少使用多少次金手指。

输入输出样例 #1

输入 #1

2 3
4 5 3 2
1 4 0
2 2 9
4 4 1

输出 #1

2
11
10

输入输出样例 #2

输入 #2

4 2
2 4 7 9 5 9 1 3 8 6 2 2 9 8 2 6
1 1 0
3 4 1

输出 #2

7
7

说明/提示

由于输入量较大，请选手使用较快的读入方式。

如下代码能够较为快速地读入 $n,m$ 以及 $a$ 数组，您可以在此代码的基础上实现此题：

#include<bits/stdc++.h>
using namespace std;
int read();

signed main(){
	n=read();m=read();
	for(int i=1;i<=(1<<n);++i) a[i]=read(); //1<<n 等于2的n次方 
	//至此 n 和 a 数组均已读入完毕（a 数组下标从 1 开始） 
	
	return 0;
}

int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		ch=getchar();
		if(ch=='-') f=-1;
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}

对于第一组样例的第一天，LTF 可以使用 $2$ 次金手指使他的幸福指数变为 $6$。

第一轮开始时：$(6,5),(3,2)$，第二个人和第四个人被淘汰。

第二轮开始时：$(1,1)$，由于 LTF 的编号比另一个人小，所以 LTF 胜出。

数据范围

对于 $10\%$ 的数据， $n=0$。

对于 $30\%$ 的数据，$a_i\le 42,n\le 8,m\le 10$。

另有 $40\%$ 的数据，$n\le 17,m=1$。

对于 $100\%$ 的数据，$0\le n\le 20,0\le a_i,x_i\le 10^{9},m\le 10^5$。