UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1135. [POI2009]Lyz

统计 下载数据

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≤10^9 , 0≤d≤n ) ri xi ( 1≤i≤m, 1≤ri≤n-d , |xi|≤10^9 )

Output

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

Sample Input

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

Sample Output

TAK
TAK
NIE
TAK

Hint

Source