Ice Skates

Byteasar runs a skating club. Its members meet regularly to train together, and they always use the club's ice skates. Skate sizes are numbered from $1$ to $n$.

Each member has a foot size, but that alone does not determine which skates they can wear: a skater has a size tolerance $d$, so a skater whose foot size is $r$ can wear any skate of size from $r$ to $r + d$. A skater always wears a single pair of skates of the same size, never two different sizes at once.

To stock the club, Byteasar bought $k$ pairs of skates of every size, that is $k$ pairs for each size from $1$ to $n$. Over time some people join the club while others leave, and Byteasar worries whether he will always have enough skates of a suitable size for every current member.

At the start the club has no members. You are given a sequence of $m$ events. Each event means that $x$ members with foot size $r$ have just joined the club (when $x \ge 0$) or just left it (when $x < 0$). Immediately after every event, decide whether Byteasar has skates of a suitable size for every member of the club at that moment.

The first line contains four integers $n$, $m$, $k$, and $d$ ($1 \le n \le 200\,000$, $1 \le m \le 500\,000$, $1 \le k \le 10^9$, $0 \le d < n$), separated by single spaces: the largest skate size, the number of events, the number of skate pairs bought of each size, and the size tolerance.

Each of the next $m$ lines describes one event with two integers $r_i$ and $x_i$ ($1 \le r_i \le n - d$, $-10^9 \le x_i \le 10^9$), separated by a single space. If $x_i \ge 0$, then $x_i$ new members with foot size $r_i$ have just joined the club; if $x_i < 0$, then $|x_i|$ members with foot size $r_i$ have just left it. The sequence is always consistent: a member who never joined can never leave.

Print $m$ lines. The $i$-th line must contain TAK (Polish for yes) if, right after the $i$-th event, Byteasar has skates of a suitable size for every club member, or NIE (Polish for no) otherwise.

To see how a full assignment can work, suppose that at some moment three members can wear skates of size $1$ or $2$, two members can wear size $2$ or $3$, and three members can wear size $3$ or $4$. Two pairs of skates of each of the sizes $1$, $2$, $3$, and $4$ are then enough for everyone:

• two members take skates of size $1$;
• the size-$2$ skates go to one member who can wear size $1$ or $2$ and one who can wear size $2$ or $3$;
• the size-$3$ skates go to one member who can wear size $2$ or $3$ and one who can wear size $3$ or $4$;
• the remaining two members take skates of size $4$.