Поликарп летит в самолете и, наконец, наступил его любимый момент — обед. Стюардесса авиакомпании БерАвиа разносит еду всем пассажирам последовательно от 1-го до последнего. Поликарп сидит на месте m, и, следовательно, получит еду m-м по очереди.
Всего в ассортименте есть k блюд, и, зайдя на борт, Поликарп успел посчитать сколько порций каждого вида из блюд есть на борту. Таким образом, известны величины a1, a2, ..., ak, где ai — количество порций i-го блюда.
Стюардесса уже раздала еду m - 1 пассажиру и с вежливой улыбкой спросила Поликарпа, что он предпочитает. В этот самый миг Поликарп осознал, что какие-то блюда уже могли закончиться к этому моменту. Для некоторых из m - 1 пассажиров впереди он заметил, какие блюда им дали. Кроме того от некоторых из m - 1 пассажиров впереди он слышал неразборчивое бормотание, эквивалентное фразе «я разочарован». Такое случалось, когда пассажир просил какое-то блюдо, но ему с вежливой улыбкой отвечали, что оно закончилось. В таком случае, ему было необходимо выбрать другое блюдо из тех, что есть в наличии. Если Поликарп не слышал от пассажира никаких звуков, то значит пассажир выбрал блюдо с первой попытки.
Помогите Поликарпу для каждого блюда выяснить: могло ли оно уже закончиться к моменту обслуживания Поликарпа, или оно обязательно в наличии есть.
Каждый тест в этой задаче состоит из одного или более набора входных данных. Сначала следует строка, содержащая единственное целое число t (1 ≤ t ≤ 100 000) — количество наборов входных данных в тесте. Далее следуют сами наборы, перед каждым из них содержится пустая строка.
В первой строке каждого набора входных данных записаны целые числа m, k (2 ≤ m ≤ 100 000, 1 ≤ k ≤ 100 000) — номер места Поликарпа и количество блюд соответственно.
Вторая строка содержит последовательность из k целых чисел a1, a2, ..., ak (1 ≤ ai ≤ 100 000), где ai — начальное количество порций i-го блюда.
Далее следует m - 1 строка, каждая из которых содержит описание наблюдений Поликарпа о выдаче еды впереди сидящему пассажиру: j-я из этих строк содержит пару целых чисел tj, rj (0 ≤ tj ≤ k, 0 ≤ rj ≤ 1), где tj — это номер блюда, что было выдано j-му пассажиру (или 0, если Поликарп не заметил, какое конкретно блюдо ему дали), а rj — это 1 или 0 в зависимости от того разочарован был j-й пассажир или нет соответственно.
Известно, что сумма ai не меньше m, то есть хотя бы какое-то блюдо Поликарпу точно достанется. Гарантируется, что данные непротиворечивы.
Сумма m по всем наборам входных данных не превосходит 100 000. Сумма k по всем наборам входных данных не превосходит 100 000.
Для каждого набора входных данных теста выведите ответ в виде отдельной строки. Выведите строку из k букв «Y» или «N». Букву «Y» в позиции i надо выводить, если i-е блюдо могло закончиться к моменту начала обслуживания Поликарпа.
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
YNNY
YYYNY
В первом наборе входных данных в зависимости от выбора второго пассажира ситуация могла развиваться по-разному:
Таким образом, ответ — «YNNY».
Во втором наборе входных данных возможен, например, следующий вариант развития событий. Сначала первый пассажир берёт единственное третье блюдо, затем второй пассажир берёт второе блюдо. Затем третий пассажир просит третье блюдо, но его не оказывается в наличии, поэтому он, разочарованно бормоча, вынужден также довольствоваться вторым блюдом. Затем четвёртый пассажир берёт четвёртое блюдо, и в итоге Поликарп оказывается перед выбором между первым, четвёртым и пятым блюдом.
Аналогичным образом может сложиться вариант развития событий, при котором в момент, когда стюардесса подходит к Поликарпу, не остаётся первого либо пятого блюда (такое может произойти, если одно из этих блюд окажется взятым вторым пассажиром). Нетрудно видеть, что четвёртого блюда хватает с запасом, поэтому Поликарп всегда может рассчитывать на него. Таким образом, ответ — «YYYNY».
| VK Cup 2015 - Квалификация 1 |
|---|
| Закончено |
