아이스 스케이트

Byteasar는 스케이트 클럽을 운영한다. 회원들은 정기적으로 모여 함께 훈련하며, 언제나 클럽이 보유한 스케이트를 신는다. 스케이트 사이즈는 $1$번부터 $n$번까지 번호가 매겨져 있다.

각 회원에게는 발 크기가 있지만, 신을 수 있는 스케이트가 그것만으로 정해지는 것은 아니다. 회원마다 사이즈 허용치 $d$가 있어서, 발 크기가 $r$인 회원은 $r$번부터 $r + d$번까지의 사이즈를 신을 수 있다. 다만 한 회원은 항상 같은 사이즈의 스케이트 한 켤레를 신으며, 서로 다른 사이즈를 동시에 신는 일은 없다.

Byteasar는 클럽을 위해 각 사이즈마다 $k$켤레씩, 즉 $1$번부터 $n$번까지 모든 사이즈에 대해 $k$켤레씩 사 두었다. 시간이 지나면서 새로 가입하는 사람도, 탈퇴하는 사람도 생기는데, Byteasar는 매 순간 모든 회원에게 알맞은 사이즈의 스케이트가 충분한지 걱정한다.

처음에 클럽에는 아무도 없다. 이제 $m$개의 사건이 순서대로 주어진다. 각 사건은 발 크기가 $r$인 회원 $x$명이 방금 가입했거나($x \ge 0$일 때) 방금 탈퇴했음($x < 0$일 때)을 뜻한다. 각 사건 직후에, 그 시점의 모든 회원에게 알맞은 사이즈의 스케이트가 충분한지 판정하여라.

첫째 줄에 네 정수 $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$). 각각 가장 큰 스케이트 사이즈, 사건의 수, 각 사이즈마다 사 둔 스케이트 켤레 수, 사이즈 허용치를 의미한다.

이어지는 $m$개의 줄에는 각 사건이 두 정수 $r_i$와 $x_i$로 주어진다 ($1 \le r_i \le n - d$, $-10^9 \le x_i \le 10^9$). $x_i \ge 0$이면 발 크기가 $r_i$인 회원 $x_i$명이 방금 가입한 것이고, $x_i < 0$이면 발 크기가 $r_i$인 회원 $|x_i|$명이 방금 탈퇴한 것이다. 주어지는 사건들은 항상 앞뒤가 맞는다. 즉, 가입한 적 없는 회원이 탈퇴하는 일은 없다.

$m$개의 줄을 출력한다. $i$번째 줄에는, $i$번째 사건 직후에 모든 회원에게 알맞은 사이즈의 스케이트가 충분하면 TAK(폴란드어로 '예')를, 그렇지 않으면 NIE(폴란드어로 '아니오')를 출력한다.

완전한 배정이 어떻게 가능한지 살펴보자. 어느 순간 사이즈 $1$ 또는 $2$를 신을 수 있는 회원이 세 명, 사이즈 $2$ 또는 $3$을 신을 수 있는 회원이 두 명, 사이즈 $3$ 또는 $4$를 신을 수 있는 회원이 세 명 있다고 하자. 이때 사이즈 $1$, $2$, $3$, $4$가 각각 두 켤레씩이면 모두에게 충분하다.

• 두 회원은 사이즈 $1$을 신는다.
• 사이즈 $2$는 사이즈 $1$ 또는 $2$를 신을 수 있는 회원 한 명과 사이즈 $2$ 또는 $3$을 신을 수 있는 회원 한 명에게 준다.
• 사이즈 $3$은 사이즈 $2$ 또는 $3$을 신을 수 있는 회원 한 명과 사이즈 $3$ 또는 $4$를 신을 수 있는 회원 한 명에게 준다.
• 남은 두 회원은 사이즈 $4$를 신는다.