题面

奥林匹克竞赛，是懊人的。

有一个长度为$2^n$的序列a，编号从$0$到$2^n-1$。

有$Q$次操作，每次给定$x,v$，将所有满足$i$ $or$ $x$ $=$ $i$的$a_i\rightarrow a_i-v$。

要求输出每个位置第一次小于0是在哪个操作之后。如果到所有操作结束后没有小于0，则输出$Q+1$。

输入格式

第一行两个正整数$n,Q$。

第二行共$2^n$个非负整数，表示初始的$a_i$。

随后$Q$行，每行两个非负整数$x,v$，保证$0\leq x$<$2^n$ 。

输出格式

共$2^n$行，每行一个在$[1,Q+1]$范围内的正整数，代表第i个位置的答案。

样例

样例输入1

3 4
6 9 9 2 6 7 3 7
4 0
0 4
0 4
3 4

样例输出1

3
5
5
2
3
3
2
3

其余样例见下发文件。