Byteasar 经营着一家滑冰俱乐部。会员们定期聚会并一起训练，他们总是使用俱乐部的公用冰鞋。冰鞋的尺码（按惯例）从 $1$ 到 $n$ 编号。当然，每位俱乐部成员都有自己的脚码，但这还不是全部！滑冰者有一个冰鞋尺码容差因子 $d$：脚码为 $r$ 的滑冰者可以穿尺码从 $r$ 到 $r+d$ 的冰鞋。需要注意的是，没有任何滑冰者会同时穿两只不同尺码的冰鞋。

为了供应俱乐部，Byteasar 为每个尺码（即从 $1$ 到 $n$）购买了 $k$ 双冰鞋。随着时间的推移，有些人加入俱乐部，也有一些老会员离开。Byteasar 担心在每次训练时，他是否都有足够尺码合适的冰鞋供每位成员使用。

假设俱乐部最初没有任何成员。Byteasar 将为你提供一个包含 $m$ 个事件的序列，每个事件的形式如下：$x$ 名脚码为 $r$ 的（新）成员加入或离开了俱乐部。在每次事件发生后，Byteasar 都想知道他是否拥有足够尺码合适的冰鞋供每位俱乐部成员使用。他请求你编写一个程序来为他进行检查。

输入格式

标准输入的第一行包含四个整数 $n$、$m$、$k$ 和 $d$（$1 \le n \le 200\,000$，$1 \le m \le 500\,000$，$1 \le k \le 10^9$，$0 \le d < n$），由空格分隔，分别表示：最大冰鞋尺码、事件数量、Byteasar 最初为每个尺码购买的冰鞋对数，以及冰鞋尺码容差因子。接下来的 $m$ 行包含 $m$ 个事件序列，每行一个事件。第 $(i+1)$ 行（对于 $1 \le i \le m$）包含两个整数：$r_i$ 和 $x_i$（$1 \le r_i \le n-d$，$-10^9 \le x_i \le 10^9$），由空格分隔。如果 $x_i \ge 0$，表示有 $x_i$ 名脚码为 $r_i$ 的新成员加入了俱乐部。如果 $x_i < 0$，表示有 $x_i$ 名脚码为 $r_i$ 的成员离开了俱乐部。你可以假设事件序列是合理的，即从未加入俱乐部的人不会离开。

输出格式

你的程序应向标准输出打印 $m$ 行。第 $i$ 行（对于 $1 \le i \le m$）应输出 TAK（波兰语，意为“是”）或 NIE（波兰语，意为“否”），取决于在第 $i$ 个事件发生后，Byteasar 是否有足够的尺码合适的冰鞋供每位俱乐部成员使用。

样例

输入 1

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

输出 1

TAK
TAK
NIE
TAK

说明 1

在输入序列中的所有事件发生后，有三名俱乐部成员可以穿 1 或 2 码的冰鞋，两名成员可以穿 2 或 3 码的冰鞋，三名成员可以穿 3 或 4 码的冰鞋。在这样的成员名单下，每个尺码（1、2、3 和 4）各两双冰鞋就足够了：

• 两名成员获得 1 码冰鞋；
• 2 码冰鞋分给一名可以穿 1 或 2 码的成员，以及一名可以穿 2 或 3 码的成员；
• 3 码冰鞋分给一名可以穿 2 或 3 码的成员，以及一名可以穿 3 或 4 码的成员；
• 其余两名成员获得 4 码冰鞋。