[POI2009]Lyz

初始时滑冰俱乐部有 $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 r_i\le n-d$，$|x_i|\le 10^9$（$1\le i\le m$）。

来源与许可

本题为 POI 2009 试题「Lyz」，题面与测试数据整理自 BZOJ 1135。

样例 1

输入

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

输出

TAK
TAK
NIE
TAK