Problem: Input

The input is given from Standard Input in the following format:


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Input

The input is given from Standard Input in the following format:


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Examples

Input

9 3
5 11
8 4
4 7


Output

4
4
4
4
2
2
1
1
0


Input

6 6
3 5
6 11
1 6
4 7
5 2
2 5


Output

10
10
5
5
4
2


Input

5 6
1 1
2 1
3 1
1 1
5 1
3 1


Output

2
2
1
1
0


Input

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100


Output

223
123
77
50
33
21
12
7
3
1

Solution (in CPP):

Solution:
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "functional"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

struct RRange {
	int l, r;
	long long int num;
	RRange(const int a, const int b, const long long int c) {
		l = a, r = b, num = c;
		return;
	}
	bool operator<(const RRange& rr)const {
		return r < rr.r;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> K;
	set<RRange>sr;
	sr.insert(RRange(1, N, 0));
	for (int i = 0; i < K; i++) {
		cin >> L >> R;
		auto bag = sr.lower_bound(RRange(1, L, 0));
		if (bag->r != L) {
			int l = bag->l;
			int r = bag->r;
			long long int num = bag->num;
			sr.erase(bag);
			sr.insert(RRange(l, L, num));
			sr.insert(RRange(L + 1, r, num));
		}
		while (R) {
			auto box = sr.lower_bound(RRange(1, L, 0));
			if (box == sr.begin()) {
				int l = box->l;
				int r = box->r;
				long long int num = box->num;
				sr.erase(box);
				if (R%r) {
					sr.insert(RRange(l, l + (R%r) - 1, num + R / r + 1));
					sr.insert(RRange(l + (R%r), r, num + R / r));
				}
				else {
					num += R / r;
					sr.insert(RRange(l, r, num));
				}
				R = 0;
			}
			else {
				//cout << "Hi";
				auto bag = prev(box);
				int l = box->l;
				int r = box->r;
				long long int num = box->num;
				sr.erase(box);
				long long int dif = (bag->num) - num;
				dif *= r - l + 1;
				//cout <<"dif "<< dif << endl;
				if (dif-(r-l+1) >= R) {
					if (R%(r-l+1)) {
						sr.insert(RRange(l, l + (R%(r-l+1)) - 1, num + R / (r-l+1) + 1));
						sr.insert(RRange(l + (R%(r-l+1)), r, num + R / (r-l+1)));
					}
					else {
						num += R / (r-l+1);
						sr.insert(RRange(l, r, num));
					}
					R = 0;
				}
				else if (dif <= R) {
					int ll = bag->l;
					long long int nnum = bag->num;
					sr.erase(bag);
					sr.insert(RRange(ll, r, nnum));
					R -= dif;
				}
				else {
					int m = R % (r - l + 1);
					int ll = bag->l;
					int rr = bag->r;
					long long int nnum = bag->num;
					sr.erase(bag);
					sr.insert(RRange(ll, rr + m, nnum));
					sr.insert(RRange(rr + m + 1, r, nnum - 1));
					R = 0;
				}
			}
			//cout << "R " << R << endl;

		}
	}
	for (auto i : sr) {
		for (int j = i.l; j <= i.r; j++) {
			cout << i.num << endl;
		}
		//cout << i.l << " " << i.r << " " << i.num << endl;
	}
}