B. 独 (unique)

天依和阿绫有一个长度为 的整数序列 ，将序列中的数从左到右编号为 。
现在她们要从中选出一个独特的数，天依希望这个数尽可能大，阿绫希望这个数尽可能小。
2 个人的要求不能同时满足，于是她们约定按照以下规则选数：

2 个人轮流操作，天依先操作。
每次操作，将序列左右分成长度相等的两部分，选择一部分保留。
形式化的说，假设当前序列长度为 ，则将序列分为 和 两部分，并选择一部分保留，操作后序列长度变为 。

最后剩下的数即为选出的数。

请你回答，假如天依和阿绫都按照最优策略（即尽可能满足自己的要求），那么最后剩下的数是多少。

此外，有 次修改操作，每次给出 ，将 加上 。
你还需要回答每次修改后的结果。

从文件 unique.in 中读入。

第一行输入 2 个数，。
第二行输入 个数，表示 。
接下来 行，每行 3 个数 。

输出到文件 unique.out 中。

输出 行，表示初始答案和每次修改后的答案。

样例输入 1

2 1
2 5 3 4
0 0 2

样例输出 1

3
4

样例解释 1

初始时，序列为 ，天依操作时，分成了 和 两部分，假设天依选了 ，那么阿绫会把 留下，因此天依选择 ，阿绫把 留下。

修改后，序列为 ，天依选择 ，阿绫选择 。

样例输入 2

3 5
2 3 4 1 2 5 4 2
2 3 4
1 5 -3
0 3 2
3 6 -1
1 6 -4

样例输出 2

4
4
2
4
4
3

样例 3

见附加文件，该样例满足测试点 的限制。

样例 4

见附加文件，该样例满足测试点 的限制。

对于 的数据，，，，。