题目描述

题目译自 XVI OI Olimpiada Informatyczna – II etap Łyżwy

Bajtazar 经营一家滑冰俱乐部，成员定期聚会训练，统一使用俱乐部提供的冰鞋。冰鞋尺寸从 $1$ 到 $n$ 编号。每位成员的脚型对应特定尺寸 $r$，但可接受尺寸范围为 $r$ 到 $r+d$（容差 $d$）。需注意，成员不可同时穿不同尺寸的冰鞋。

Bajtazar 为俱乐部购置了每种尺寸（$1$ 到 $n$）各 $k$ 副冰鞋。随着时间推移，新成员加入，部分成员退出。Bajtazar 担心每次训练时是否能为所有成员提供合适尺寸的冰鞋。

初始时俱乐部无成员。Bajtazar 提供了一组 $m$ 个事件序列，每事件形如：新增或减少 $x$ 名脚型尺寸为 $r$ 的成员。他希望在每个事件后确认是否能为所有成员分配合适冰鞋。请编写程序，协助他进行判断。

输入格式

第一行包含四个整数 $n, m, k, d$ $(1 \leq n \leq 200000, 1 \leq m \leq 500000, 1 \leq k \leq 10^9, 0 \leq d < n)$，分别表示最大冰鞋尺寸、事件数、每种尺寸的冰鞋副数和脚型尺寸容差。

接下来的 $m$ 行描述事件，第 $i+1$ $(1 \leq i \leq m)$ 行包含两个整数 $r_i, x_i$ $(1 \leq r_i \leq n-d, -10^9 \leq x_i \leq 10^9)$。若 $x_i \geq 0$，表示新增 $x_i$ 名脚型尺寸为 $r_i$ 的成员；若 $x_i < 0$，表示 $-x_i$ 名脚型尺寸为 $r_i$ 的成员退出。保证事件序列合法，即不会退出未加入的成员。

输出格式

输出 $m$ 行，第 $i$ $(1 \leq i \leq m)$ 行包含 TAK 或 NIE，表示第 $i$ 个事件后，Bajtazar 是否能为所有成员分配合适尺寸的冰鞋。

4 4 2 1
1 3
2 3
3 3
2 -1

TAK
TAK
NIE
TAK

所有事件发生后，俱乐部有三名成员可穿尺寸 $1$ 或 $2$ 的冰鞋，两名成员可穿尺寸 $2$ 或 $3$ 的冰鞋，三名成员可穿尺寸 $3$ 或 $4$ 的冰鞋。在此成员构成下，每种尺寸各两副冰鞋足够分配：

• 两名成员使用尺寸 $1$ 的冰鞋；
• 一名可穿尺寸 $1$ 或 $2$ 的成员和一名可穿尺寸 $2$ 或 $3$ 的成员使用尺寸 $2$ 的冰鞋；
• 一名可穿尺寸 $2$ 或 $3$ 的成员和一名可穿尺寸 $3$ 或 $4$ 的成员使用尺寸 $3$ 的冰鞋；
• 剩余两名成员使用尺寸 $4$ 的冰鞋。