RT，fhq写的，死活过不了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[1000005];
struct fhq {
	int val[1000005], rd[1000005];
	int size[1000005], sum[1000005];
	int son[1000005][2];
	int f, x, y, z, s;
	void pushup(int k) {
		size[k] = size[son[k][0]] + size[son[k][1]] + 1;
		sum[k] = sum[son[k][0]] + sum[son[k][1]] + val[k];
	}
	int new_node(int v) {
		s++;
		val[s] = sum[s] = v; rd[s] = rand(); size[s] = 1;
		return s;
	}
	void split(int k, int v, int &x, int &y) {
		if (!k) {x = y = 0; return;}
		if (val[k] <= v) x = k, split(son[k][1], v, son[k][1], y);
		else y = k, split(son[k][0], v, x, son[k][0]);
		pushup(k);
	}
	int merge(int x, int y) {
		if (!x || !y) return x + y;
		if (rd[x] < rd[y]) {son[x][1] = merge(son[x][1], y); pushup(x); return x;}
		else {son[y][0] = merge(x, son[y][0]); pushup(y); return y;}
	}
	void insert(int v) {split(f, v, x, y); f = merge(merge(x, new_node(v)), y);}
	void del(int v) {
		split(f, v, x, z); split(x, v - 1, x, y);
		y = merge(son[y][0], son[y][1]); f = merge(merge(x, y), z);
	}
	int query(int s) {
		split(f, s, x, y);
		int ans = val[y] - s * size[y];
		// cout << ":::" << size[y] << ' ' << val[y] << endl;
		f = merge(x, y);
		return sum[f] - ans;
	}
} t;
inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
	return x * f;
}
signed main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		char p; int x, y; cin >> p; x = read(); y = read();
		if (p == 'U') {t.del(a[x]); t.insert(y); a[x] = y;}
		else {
			int k = t.query(y);
			if (k >= x * y) printf("TAK\n");
			else printf("NIE\n");
		}
	}
	return 0;
}