302689: CF522C. Chicken or Fish?
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Chicken or Fish?
题目描述
Polycarp is flying in the airplane. Finally, it is his favorite time — the lunchtime. The BerAvia company stewardess is giving food consecutively to all the passengers from the $ 1 $ -th one to the last one. Polycarp is sitting on seat $ m $ , that means, he will be the $ m $ -th person to get food. The flight menu has $ k $ dishes in total and when Polycarp boarded the flight, he had time to count the number of portions of each dish on board. Thus, he knows values $ a_{1},a_{2},...,a_{k} $ , where $ a_{i} $ is the number of portions of the $ i $ -th dish. The stewardess has already given food to $ m-1 $ passengers, gave Polycarp a polite smile and asked him what he would prefer. That's when Polycarp realized that they might have run out of some dishes by that moment. For some of the $ m-1 $ passengers ahead of him, he noticed what dishes they were given. Besides, he's heard some strange mumbling from some of the $ m-1 $ passengers ahead of him, similar to phrase 'I'm disappointed'. That happened when a passenger asked for some dish but the stewardess gave him a polite smile and said that they had run out of that dish. In that case the passenger needed to choose some other dish that was available. If Polycarp heard no more sounds from a passenger, that meant that the passenger chose his dish at the first try. Help Polycarp to find out for each dish: whether they could have run out of the dish by the moment Polyarp was served or that dish was definitely available.输入输出格式
输入格式
Each test in this problem consists of one or more input sets. First goes a string that contains a single integer $ t $ ( $ 1<=t<=100000 $ ) — the number of input data sets in the test. Then the sets follow, each set is preceded by an empty line. The first line of each set of the input contains integers $ m $ , $ k $ ( $ 2<=m<=100000 $ , $ 1<=k<=100000 $ ) — the number of Polycarp's seat and the number of dishes, respectively. The second line contains a sequence of $ k $ integers $ a_{1},a_{2},...,a_{k} $ ( $ 1<=a_{i}<=100000 $ ), where $ a_{i} $ is the initial number of portions of the $ i $ -th dish. Then $ m-1 $ lines follow, each line contains the description of Polycarp's observations about giving food to a passenger sitting in front of him: the $ j $ -th line contains a pair of integers $ t_{j},r_{j} $ ( $ 0<=t_{j}<=k,0<=r_{j}<=1 $ ), where $ t_{j} $ is the number of the dish that was given to the $ j $ -th passenger (or 0, if Polycarp didn't notice what dish was given to the passenger), and $ r_{j} $ — a 1 or a 0, depending on whether the $ j $ -th passenger was or wasn't disappointed, respectively. We know that sum $ a_{i} $ equals at least $ m $ , that is,Polycarp will definitely get some dish, even if it is the last thing he wanted. It is guaranteed that the data is consistent. Sum $ m $ for all input sets doesn't exceed $ 100000 $ . Sum $ k $ for all input sets doesn't exceed $ 100000 $ .
输出格式
For each input set print the answer as a single line. Print a string of $ k $ letters "Y" or "N". Letter "Y" in position $ i $ should be printed if they could have run out of the $ i $ -th dish by the time the stewardess started serving Polycarp.
输入输出样例
输入样例 #1
2
3 4
2 3 2 1
1 0
0 0
5 5
1 2 1 3 1
3 0
0 0
2 1
4 0
输出样例 #1
YNNY
YYYNY