N. Stone Skipping
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are going to a stone skipping contest. The lake can be represented as a number line, with the shore being all negative integers, and the lake occupying all the nonnegative integers.

You may stand at any integer position on the shore and throw your stone with any integer power. If you throw with power $$$p$$$, the stone will move $$$p$$$ meters before bouncing. When the stone bounces, if it has power $$$p$$$, it will bounce again with power $$$\lfloor p/2 \rfloor$$$, and if the stone has power $$$0$$$, it will sink. Contest regulations state the stone must sink at position $$$N$$$ $$$(1 \le N \le 10^{18})$$$, and the score of the throw is the sum of $$$a_x$$$ for each position $$$x$$$ the stone bounces, for an zero-index array $$$a$$$ of length $$$N$$$.

The array $$$a$$$ initially begins at all $$$0$$$s, but there are $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ modifications which change $$$a_x = y$$$ where $$$0 \le x \lt N$$$ and $$$0 \le y \le 10^{15}$$$. Compute the maximum score after each modification.

Input

The first line contains two positive integers: $$$N$$$ $$$(1 \le N \le 10^{18})$$$, the final sink position, and $$$Q$$$ $$$(1 \le Q \le 10^5)$$$, the number of modifications.

The next $$$Q$$$ lines contain two integers each: $$$x$$$ $$$(0 \le x \lt N)$$$, the position of the change, and $$$y$$$ $$$(0 \le y \le 10^{15})$$$, the modified value.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy $$$N \leq 1000$$$, $$$Q \leq 1000$$$.

Tests $$$3-5$$$ satisfy $$$N \leq 10^6$$$, $$$Q \leq 2000$$$.

Tests $$$6-9$$$ satisfy $$$Q \leq 2000$$$.

Tests $$$10-20$$$ satisfy no additional constraints.

Output

Output $$$Q$$$ integers—the maximum score after each modification.

Example
Input
10 6
9 3
6 5
5 100
0 4
7 6
6 0
Output
3
8
8
12
12
9
Note

Problem Idea: achen

Problem Preparation: TheRowletOwlet

Occurrences: Advanced E