1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll faster[1005*1005];
int i_faster;
struct Node {
	int size;
	ll rightmost;
	ll toPush;
	ll getRightmost() { return toPush + rightmost; }
	Node * left, * right;
	bool isLeaf() { return left == NULL; }
	bool mustImprove(int a, int b) {
		return max(a,b) > 3 * min(a, b) + 5;
	}
	void dfs() {
		if(isLeaf()) faster[i_faster++] = getRightmost();
		else {
			pushDown();
			left -> dfs();
			right -> dfs();
		}
	}
	void create(int low, int high) {
		if(low == high) *this = Node{1, faster[low], 0, NULL, NULL};
		else {
			int mid = (low + high) / 2;
			if(left == NULL) left = new Node{0,0,0,NULL,NULL};
			left -> create(low, mid);
			if(right == NULL) right = new Node{0,0,0,NULL,NULL};
			right -> create(mid + 1, high);
			upd();
		}
	}
	void pushDown() {
		if(isLeaf()) return;
		rightmost += toPush;
		left -> toPush += toPush;
		right -> toPush += toPush;
		toPush = 0;
	}
	void upd() {
		if(isLeaf()) return;
		toPush = 0;
		size = left -> size + right -> size;
		rightmost = right -> getRightmost();
		if(mustImprove(left -> size, right -> size)) {
			i_faster = 0;
			dfs();
			create(0, i_faster - 1);
		}
	}
	void add(ll a, ll b, int day) {
		pushDown();
		if(isLeaf()) {
			if(size == 0) { // it's an empty root
				// assert(day == 0);
				size = 1;
				rightmost = b;
				return;
			}
			if(a * day + b >= getRightmost()) {
				left = new Node{1, a * day + b, 0, NULL, NULL};
				right = new Node{1, getRightmost() + a, 0, NULL, NULL};
			}
			else {
				left = new Node{1, getRightmost(), 0, NULL, NULL};
				right = new Node{1, a * (day + 1) + b, 0, NULL, NULL};
			}
		}
		else {
			if(a * (day + left -> size - 1) + b >= left -> getRightmost()) {
				left -> add(a, b, day);
				right -> toPush += a;
			}
			else {
				right -> add(a, b, day + left -> size);
			}
		}
		upd();
	}
	void print(vector<ll> & ans) {
		pushDown();
		if(isLeaf()) ans.push_back(getRightmost());
		else {
			left -> print(ans);
			right -> print(ans);
		}
	}
};
long long read() {
	long long x = 0;
	char ch;
	while(true) {
		ch = getchar();
		if('0' <= ch && ch <= '9') x = 10 * x + (ch - '0');
		else break;
	}
	return x;
}
void te() {
	int n = read();
	vector<pair<ll,ll>> w(n);
	for(int i = 0; i < n; ++i) {
		w[i].first = read();
		w[i].second = read();
	}
	sort(w.begin(), w.end());
	Node tree{0,0,0,NULL,NULL};
	for(pair<ll,ll> p : w)
		tree.add(p.first, p.second, 0);
	vector<ll> ans;
	tree.print(ans);
	ll s = 0;
	for(ll x : ans) printf("%lld\n", s += x);
}
int main() {
	int T;
	T = 1; //scanf("%d", &T);
	while(T--) te();
}