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
#include <bits/stdc++.h>
#define REP(a,b) for(int a=0; a<(b); ++a)
#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define FWDS(a,b,c,d) for(int a=(b); a<(c); a+=d)
#define BCK(a,b,c) for(int a=(b); a>(c); --a)
#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) ((int)(a).size())
#define VAR(x) #x ": " << x << " "
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define gcd __gcd
#define x first
#define y second
#define st first
#define nd second
#define pb push_back

using namespace std;

template<typename T> ostream& operator<<(ostream &out, const vector<T> &v){ out << "{"; for(const T &a : v) out << a << ", "; out << "}"; return out; }
template<typename S, typename T> ostream& operator<<(ostream &out, const pair<S,T> &p){ out << "(" << p.st << ", " << p.nd << ")"; return out; }

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef long double K;
typedef vector<int> VI;

const int dx[] = {0,0,-1,1}; //1,1,-1,1};
const int dy[] = {-1,1,0,0}; //1,-1,1,-1};

const int MAXN = 1000010;

struct node {
	int rank;
	node *left, *right;
	int k, m;
	LL val, mv;
	void push(){
		if(m){
			k += m;
			if(left) left->m += m;
			if(right) right->m += m;
			m = 0;
		}
		if(mv){
			val += mv;
			if(left) left->mv += mv;
			if(right) right->mv += mv;
			mv = 0;
		}
	}
};

node *insert(node *u, LL a, LL b, int nk){
	if(u == NULL){
		node *v = new node();
		v->rank = rand();
		v->left = v->right = NULL;
		v->k = nk;
		v->m = 0;
		v->val = a*nk+b;
		v->mv = 0;
		return v;
	}
	u->push();
	if(u->k * a + b > u->val){
		u->left = insert(u->left, a, b, u->k);
		u->k += 1;
		u->val += a;
		if(u->right){
			u->right->m += 1;
			u->right->mv += a;
		}
		if(u->left->rank < u->rank){
			node *v = u->left;
			u->left = v->right;
			v->right = u;
			return v;
		}
	}else{
		u->right = insert(u->right, a, b, u->k+1);
		if(u->right->rank < u->rank){
			node *v = u->right;
			u->right = v->left;
			v->left = u;
			return v;
		}
	}
	return u;
}

vector<int> ord;
LL sp;
void wypisz(node* u){
	u->push();
	if(u->left) wypisz(u->left);
	sp += u->val;
	printf("%lld\n", sp);
	if(u->right) wypisz(u->right);
}

int n;
PLL G[MAXN];

node* root;

int main(){
	scanf("%d", &n);
	FWD(i,0,n) scanf("%lld %lld", &G[i].st, &G[i].nd);
	sort(G, G+n);
	root = NULL;
	FWD(i,0,n) root = insert(root, G[i].st, G[i].nd, 0);
	wypisz(root);
	return 0;
}