[POI2009]Lyz

Time Limit:10000MS  Memory Limit:165536K
Total Submit:56 Accepted:16
Case Time Limit:2000MS

Description

初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。

有m次操作，每次包含两个数ri，xi代表来了xi个ri号脚的人。xi为负，则代表走了这么多人。

对于每次操作，输出溜冰鞋是否足够。

Input

n m k d ( 1≤n≤200,000 ， 1≤m≤500,000 ， 1≤k≤109 ， 0≤d≤n )

ri xi （ 1≤i≤m， 1≤ri≤n-d ， |xi|≤109 ）

Output

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

Sample Input

4 4 2 1

1 3

2 3

3 3

2 -1

Sample Output

TAK

TAK

NIE

TAK

Source
额。。这个题目有二分图匹配的感觉。那么根据Hall定理，对于任何一个子集，他的临集的大小必须要大于它的大小。。
那么设ti为脚为i号的人数
对于ta到tb，它们临集的大小显然是(b-a+1+d)*k
那么需要知道是不是对任何一个连续子序列都满足这个。。
变形一下设t’a=ta-k
那么Sum(ta..b)<=(b-a+1+d)*k
<=>
Sum(t’a..b)<=d*k
。。。。可以发现只要维护t’的最大子序列和就OK了T_T。。
这显然是最简单的线段树。。
发代码也麻烦。。。我的马甲nimendongde的密码是123456.。。。
自己去看吧T_T。。