rt /kel/kel/kel

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAXN = 6e5 + 10;

mt19937 eng(time(0));

uniform_int_distribution<int> dist;

struct node {
	ll val, sum;
	int w, s, l, r;
} t[MAXN]; int cnt, rt;

inline 
int create(ll val) {
	return t[++cnt] = { val, val, dist(eng), 1 }, cnt;
}

inline 
void pushup(int p) {
	t[p].s = t[t[p].l].s + t[t[p].r].s + 1;
	t[p].sum = t[t[p].l].sum + t[t[p].r].sum + t[p].val;
}

void split(int p, ll val, int &x, int &y) {
	if (!p) return x = y = 0, void();
	if (t[p].val >= val) x = p, split(t[p].r, val, t[p].r, y);
	else y = p, split(t[p].l, val, x, t[p].l); pushup(p);
}

void split_k(int p, int k, int &x, int &y) {
	if (!p) return x = y = 0, void();
	if (t[t[p].l].s < k) x = p, split_k(t[p].r, k - t[t[p].l].s - 1, t[p].r, y);
	else y = p, split_k(t[p].l, k, x, t[p].l); pushup(p);
}

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (t[x].w < t[y].w) return t[y].l = merge(x, t[y].l), pushup(y), y;
	else return t[x].r = merge(t[x].r, y), pushup(x), x;
}

inline 
void insert(ll val) {
	int l, r; split(rt, val, l, r);
	rt = merge(merge(l, create(val)), r);
}

inline 
void erase(ll val) {
	int l, p, r; split(rt, val, l, r), split(l, val + 1, l, p);
	rt = merge(merge(l, merge(t[p].l, t[p].r)), r);
}

inline 
ll query(int k) {
	int l, r; split_k(rt, k, l, r); ll res = t[l].sum;
	return rt = merge(l, r), res;
}

int n, m, h, k, ans[MAXN];

ll sum, p[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &h);
    for (int i = 1; i <= m; i++) insert(0);
    for (int i = 1, x, y; i <= n; i++) {
    	scanf("%d%d", &x, &y), sum += x;
    	erase(p[y]), insert(p[y] += x);
    	for (; query(k) + h < sum && k <= m; k++, ans[k] = ans[k - 1]);
    	ans[k] = i;
	}
	for (k++; k <= m; k++) ans[k] = ans[k - 1];
	for (int i = 0; i <= m; i++) printf("%d ", ans[i]);
}