Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题面

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

有一个长度为$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

其余样例见下发文件。

WURHD.png