波利卡普正在飞机上飞行。终于,到了他最喜欢的时间——午餐时间。 BerAvia公司的空姐正从第1位到最后一位依次给所有乘客送餐。波利卡普坐在 m 座位上,这意味着他将是第 m 个拿到食物的人。
航班菜单共有 k 道菜,当 Polycarp 登机时,他有时间数飞机上每道菜的份数。因此,他知道值 a1、a2、...、ak,其中 ai 是第 i 道菜的份数。
空姐已经给m-1位乘客提供了食物,给波利卡普一个礼貌的微笑,并问他想要什么。就在那时,波利卡普意识到他们可能已经用完了一些菜肴。对于他前面的一些 m - 1 乘客,他注意到他们提供的菜肴是什么。此外,他还听到前面的一些 m-1 乘客发出一些奇怪的咕哝声,类似于“我很失望”之类的短语。事情发生的时候,一名乘客要了一些菜,但空姐礼貌地微笑着说,那道菜已经用完了。在这种情况下,乘客需要选择其他可用的菜肴。如果波利卡普不再听到乘客的声音,就意味着该乘客第一次尝试就选择了他的菜。
帮助 Polycarp 找出每道菜:在 Polyarp 上菜时他们是否可能已经用完这道菜,或者该菜肯定有。
输入
此问题中的每个测试都包含一个或多个输入集。首先是一个字符串,其中包含单个整数 t (1 ≤ t ≤ 100 000) — 测试中输入数据集的数量。然后是集合,每个集合前面都有一个空行。
每组输入的第一行包含整数 m, k (2 ≤ m ≤ 100 000, 1 ≤ k ≤ 100 000) — 分别是 Polycarp 的座位数和菜肴数。
第二行包含 k 个整数 a1, a2, ..., ak (1 ≤ ai ≤ 100 000) 的序列,其中 ai 是第 i 道菜的初始份数。
接下来是 m - 1 行,每行包含 Polycarp 对坐在他前面的乘客提供食物的观察的描述:第 j 行包含一对整数 tj, rj (0 ≤ tj ≤ k, 0 ≤ rj ≤ 1),其中 tj 是提供给第 j 个乘客的菜肴编号(或者 0,如果 Polycarp 没有注意到什么菜肴)给了乘客),rj — 1 或 0,分别取决于第 j 个乘客是否失望。
我们知道 ai 之和至少等于 m,也就是说,Polycarp 肯定会得到一些菜,即使这是他最不想要的东西。保证数据的一致性。
所有输入集的总和 m 不超过 100 000。所有输入集的总和 k 不超过 100 000。
输出
对于每个输入集,将答案打印为一行。打印 k 个字母“Y”或“N”的字符串。如果在空姐开始为波利卡普提供服务时他们可能已经用完第 i 道菜,则应在位置 i 打印字母“Y”。
示例
输入 #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
注意
在第一个输入集中,根据第二位乘客的选择,情况可能会以不同的方式发展:
- 如果他选择了第一道菜,那么当空姐到达波利卡普时,他们将用完第一道菜;
- 如果他选择了第四道菜,那么当空姐到达波利卡普时,他们将用完第四道菜;
- 否则,波利卡普将能够从四种菜肴中选择任何一种。
因此,答案是“YNNY”。
在第二输入集中,例如存在以下可能的场景。首先,第一位乘客拿走唯一的第三道菜,然后第二位乘客拿走第二道菜。然后,第三位乘客要了第三道菜,但没有,他失望地嘟囔着,最后还是点了第二道菜。然后第四位乘客拿走了第四道菜,波利卡普最终在第一、第四和第五道菜之间做出选择。
同样,另一种可能的情况是,当空姐到达波利卡普时,他们将用完第一道菜或第五道菜(如果其中一个菜被第二位乘客拿走,则可能会发生这种情况)。很容易看出第四道菜已经足够了,所以波利卡普总是可以信赖它。因此,答案是“YYYNY”。