CF522C.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.

波利卡普正在飞机上。终于，到了他最喜欢的时刻——午餐时间。BerAvia 航空公司的空乘人员正依次为所有乘客提供餐食，顺序从第 1 位乘客一直到末位乘客。波利卡普坐在第 $m$ 号座位，也就是说，他将是第 $m$ 个领到餐食的乘客。

本次航班的菜单共有 $k$ 道菜肴，波利卡普登机时曾有时间统计机上每道菜肴的份数。因此，他已知数值 $a_1,\,a_2,\,\dots,\,a_k$，其中 $a_i$ 表示第 $i$ 道菜肴的份数。

此时，空乘人员已为前 $m-1$ 位乘客提供了餐食，随后对波利卡普礼貌地微笑，并询问他想选择哪道菜。就在这一刻，波利卡普意识到：某些菜肴可能在此时已售罄。对于排在他前面的这 $m-1$ 位乘客中的部分人，他注意到了他们所选的菜肴；此外，他还听到其中一些乘客（同样属于这 $m-1$ 人）发出奇怪的咕哝声，类似“我太失望了”。这种情况发生在某位乘客点了一道菜，但空乘人员却报以礼貌的微笑，并告知该菜肴已售罄；此时，该乘客不得不改选另一道尚有余量的菜肴。若波利卡普未听到某位乘客发出任何声音，则表明该乘客在第一次尝试时就成功选到了自己想要的菜肴。

请帮助波利卡普判断：对每一道菜肴，当轮到他点餐时，该菜肴是否可能已经售罄，或者是否一定仍有余量。

Each test in this problem consists of one or more input sets. First goes a string that contains a single integer t (1 ≤ t ≤ 100 000) — 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 ≤ 100 000, 1 ≤ k ≤ 100 000) — 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 ≤ 100 000), 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 100 000. Sum k for all input sets doesn't exceed 100 000.

本题中的每个测试用例包含一个或多个输入数据集。首先是一行字符串，其中包含一个整数 $t$（$1 \leq t \leq 100\,000$），表示该测试用例中输入数据集的个数。随后是各数据集，每个数据集前均有一空行。

每个输入数据集的第一行包含两个整数 $m$、$k$（$2 \leq m \leq 100\,000$，$1 \leq k \leq 100\,000$），分别表示 Polycarp 所坐的座位号以及菜品种类数。

第二行包含 $k$ 个整数 $a_1,\,a_2,\,...,\,a_k$（$1 \leq a_i \leq 100\,000$），其中 $a_i$ 表示第 $i$ 种菜品的初始份数。

接下来是 $m-1$ 行，每行描述 Polycarp 对其前方乘客所获餐食的一次观察：第 $j$ 行包含一对整数 $t_j,\,r_j$（$0 \leq t_j \leq k$，$0 \leq r_j \leq 1$），其中 $t_j$ 表示分给第 $j$ 位乘客的菜品编号（若 Polycarp 未注意到所给菜品，则为 $0$）；$r_j$ 为 $1$ 或 $0$，分别表示第 $j$ 位乘客是否感到失望。

已知所有 $a_i$ 的总和至少为 $m$，即 Polycarp 必然能获得某道菜品（即使是他最不想要的那道）。数据保证自洽。

所有输入数据集中 $m$ 的总和不超过 $100\,000$；所有输入数据集中 $k$ 的总和不超过 $100\,000$。

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.

对每组输入，以单行形式输出答案。输出一个由 k 个字母“Y”或“N”组成的字符串。若乘务员开始为 Polycarp 上菜时，第 i 道菜已售罄，则第 i 个位置应输出字母“Y”。

In the first input set depending on the choice of the second passenger the situation could develop in different ways:

• If he chose the first dish, then by the moment the stewardess reaches Polycarp, they will have run out of the first dish;
• If he chose the fourth dish, then by the moment the stewardess reaches Polycarp, they will have run out of the fourth dish;
• Otherwise, Polycarp will be able to choose from any of the four dishes.

Thus, the answer is "YNNY".

In the second input set there is, for example, the following possible scenario. First, the first passenger takes the only third dish, then the second passenger takes the second dish. Then, the third passenger asks for the third dish, but it is not available, so he makes disappointed muttering and ends up with the second dish. Then the fourth passenger takes the fourth dish, and Polycarp ends up with the choice between the first, fourth and fifth dish.

Likewise, another possible scenario is when by the time the stewardess comes to Polycarp, they will have run out of either the first or the fifth dish (this can happen if one of these dishes is taken by the second passenger). It is easy to see that there is more than enough of the fourth dish, so Polycarp can always count on it. Thus, the answer is "YYYNY".

在第一组输入中，根据第二位乘客的选择，情况可能有不同发展：

• 如果他选择了第一道菜，那么当空乘人员到达波利卡普时，第一道菜将已售罄；
• 如果他选择了第四道菜，那么当空乘人员到达波利卡普时，第四道菜将已售罄；
• 否则，波利卡普将可以从四道菜中任选其一。

因此，答案为 "YNNY"。

在第二组输入中，存在如下一种可能情形：首先，第一位乘客取走了唯一的第三道菜；接着，第二位乘客取走了第二道菜；然后，第三位乘客索要第三道菜，但该菜品已无库存，于是他失望地嘟囔几句，最终选择了第二道菜；随后，第四位乘客取走了第四道菜；最终，波利卡普可在第一、第四与第五道菜中进行选择。

类似地，另一种可能情形是：当空乘人员到达波利卡普时，第一道或第五道菜已售罄（例如，其中一道被第二位乘客取走）。显然，第四道菜的库存十分充足，因此波利卡普总能确保选到它。因此，答案为 "YYYNY"。