时空限制

1S/512M

题目描述

定义 $m$ 个数的序列 $a_1,a_2,\dots,a_m$ 的权值为 $\sum_{b=0}^{29}|\{\lfloor\dfrac{a_i}{2^b}\rfloor|1\le i\le m\}|$。

你需要在 $[0,2^{30})$ 范围内选择至多 $n$ 个不同的数（可不选任何数字）组成序列使得这个序列权值最大，并且会有 $q$ 次修改，每次修改会加入一个禁止区间，你不能选择任何一个禁止区间内的值，即你需要使得选择的数不在任何一个禁止区间内。你需要在每次修改后输出答案。

格式

输入格式

第一行两个整数 $n,q$ 分别表示至多选择的整数个数以及修改次数。

第 $2\sim q+1$ 行每行两个整数 $l,r$ 表示新加入的禁止区间为 $[l,r]$。

输出格式

输出 $q$ 行，表示每次修改后的答案。

样例

样例输入 #1

3 3
666 3999
1 1073741820
39666999 1073741822

样例输出 #1

89
62
60

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1\le q\le5\times10^5,0\le l\le r<2^{30},0\le n\le10^9$。