题目描述

初始时滑冰俱乐部有 $1$ 到 $n$ 号的溜冰鞋各 $k$ 双。已知 $x$ 号脚的人可以穿 $x$ 到 $x+d$ 的溜冰鞋。 有 $m$ 次操作，每次包含两个数 $r_i,x_i$ 代表来了 $x_i$ 个 $r_i$ 号脚的人。$x_i$ 为负，则代表走了这么多人。 对于每次操作，输出溜冰鞋是否足够。

输入格式

第一行四个整数 $n,m,k,d$。

接下来 $m$ 行，每行两个数 $r_i,x_i$。

输出格式

对于每个操作，输出一行，TAK 表示够，NIE 表示不够。

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

TAK
TAK
NIE
TAK

数据规模与约定

$ 1 \le n \le 2 \times 10^5 , 1 \le m \le 5 \times 10^5 , 1 \le k \le 10^9, 0 \le d \le n$

$1 \le i \le m, 1 \le r_i \le n-d , |x_i| \le 10^9$

提示

考虑我们什么时候是无解？

设 $[l,r]$ 为脚号码的范围，$sum_i$ 表示型号为 $i$ 的人数，则当且仅当 $sum(l,r)-k\times (r-l+1+d)>0$，就是人比鞋子多的意思；

移项，可得$\sum_l^r sum_i-k > k\times d$，我们只要用线段树维护区间最大子段和，然后和 $k\times d$ 比较即可