[POI2009]LYZ-Ice Skates

题意翻译

滑冰俱乐部初始有 1..n 号码溜冰鞋各 k 双,已知 x 号脚的人可以穿 x..x + d 号码的鞋子。现在有 m 次操作,每次两个数 r、x,表示 r 号脚的人来了 x 个,x 为负表示离开。对于每次操作,输出溜冰鞋是否足够。 题面保证r<=n-d 数据范围:$n,k,m\leq5*10^5, k\leq10^9$

题目描述

Byteasar runs a skate club. Its members meet on a regular basis and train together, and they always use the club's ice-skates. The skate sizes are (by convention) numbered from ![](http://main.edu.pl/images/OI16/lyz-en-tex.1.png) to ![](http://main.edu.pl/images/OI16/lyz-en-tex.2.png). Naturally, each club member has some foot size, but that is not all to it! Skaters have skate size tolerance factor ![](http://main.edu.pl/images/OI16/lyz-en-tex.3.png): a skater with foot size ![](http://main.edu.pl/images/OI16/lyz-en-tex.4.png) can wear skates with sizes from ![](http://main.edu.pl/images/OI16/lyz-en-tex.5.png) up to ![](http://main.edu.pl/images/OI16/lyz-en-tex.6.png). It should be noted, though, that no skater ever wears two skates of different size simultaneously. To supply the club, Byteasar bought ![](http://main.edu.pl/images/OI16/lyz-en-tex.7.png) pairs of ice-skates of each size, i.e. from ![](http://main.edu.pl/images/OI16/lyz-en-tex.8.png) to ![](http://main.edu.pl/images/OI16/lyz-en-tex.9.png). As time passes, some people join the club, just as some established members leave it. Byteasar worries if he will have enough skates of appropriate size for every member at each training. We assume that initially the club has no members at all. Byteasar will give you a sequence of ![](http://main.edu.pl/images/OI16/lyz-en-tex.10.png) events of the following form: ![](http://main.edu.pl/images/OI16/lyz-en-tex.11.png) (new) members with foot size ![](http://main.edu.pl/images/OI16/lyz-en-tex.12.png) have joined/left the club. Right after each such event Byteasar wants to know whether he has enough skates of appropriate size for every club member. He asks you to write a programme that will check it for him.

输入输出格式

输入格式


The first line of the standard input contains four integers ![](http://main.edu.pl/images/OI16/lyz-en-tex.13.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.14.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.15.png) and ![](http://main.edu.pl/images/OI16/lyz-en-tex.16.png) (![](http://main.edu.pl/images/OI16/lyz-en-tex.17.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.18.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.19.png), ![](http://main.edu.pl/images/OI16/lyz-en-tex.20.png)), separated by single spaces, that denote, respectively: maximum skate size, number of events, number of skate pairs of each size Byteasar initially bought, and the skate size tolerance factor. The following ![](http://main.edu.pl/images/OI16/lyz-en-tex.21.png) lines contain the sequence of ![](http://main.edu.pl/images/OI16/lyz-en-tex.22.png) events, one per line. The ![](http://main.edu.pl/images/OI16/lyz-en-tex.23.png)-th line (for ![](http://main.edu.pl…

输出格式


Your programme should print out ![](http://main.edu.pl/images/OI16/lyz-en-tex.35.png) lines to the standard output. The ![](http://main.edu.pl/images/OI16/lyz-en-tex.36.png)-th line (for ![](http://main.edu.pl/images/OI16/lyz-en-tex.37.png)) should either contain the word TAK (Polish for yes), or the word NIE (Polish for no), depending on whether Byteasar has the skates of appropriate size for every club member right after the ![](http://main.edu.pl/images/OI16/lyz-en-tex.38.png)-th event.

输入输出样例

输入样例 #1

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

输出样例 #1

TAK
TAK
NIE
TAK