C. Тахиа юу, Загас уу?

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Поликарп онгоцоор нисч явна. Ингэж нэг түүний хүсч хүлээсэн өдрийн хоолны цаг боллоо. БэрАвиа компаний онгоцны үйлчлэгч $1$-р суудлаас сүүлийн суудал хүртэлх дарааллаар хоол өгч байна. Поликарп $m$-р суудалд сууж яваа бөгөөд энэ нь тэрээр хоолоо авах $m$-р хүн гэсэн үг юм.

Нислэгийн цэсэнд нийтдээ $k$ төрлийн хоол байгаа бөгөөд Поликарп онгоцонд сууснаасаа хойш түүнд төрөл бүрээс хэдий хэмжээтэй хоол байгааг мэдэхэд хангалттай хугацаа байв. Тиймээс тэрээр $a_{1}, a_{2}, ..., a_{k}$ утгуудыг мэдэж байв. Энд $a_{i}$ нь $i$-р хоолны хэмжээ юм.

Онгоцны үйлчлэгч $m-1$ зорчигчдод аль хэдийн хоол өгсөн ба Поликарп руу эелдгээр инээмсэглээд түүнийг юу идмээр байгааг асуулаа. Тэгэхэд Поликарп зарим төрлийн хоол дууссан болохыг ойлгов. Түүнээс өмнөх $m-1$ зорчигчдоос заримд нь ямар төрлийн хоол өгснийг тэр ажиглалаа. Түүнээс гадна тэр $m-1$ зорчигчдын зарим нь аль нэг хоолыг асуусанд онгоцны үйлчлэг түүн рүү эелдэг инээмсэглэн, тэр хоол дууссан болохыг хэлэхэд "Урам хугарлаа" гэсэн шиг амандаа үглэж байхыг сонсжээ. Энэ тохиолдолд зорчигч боломжтой байгаагаас сонголт хийх шаардлагатай болно. Хэрэв Поликарп зорчигчдоос иймэрхүү чимээ сонсохгүй байвал энэ нь уг зорчигч эхнийхээ оролдлогоор хоолоо сонгосон гэсэн үг юм.

Хоол тус бүрийн хувьд дууссан, эсвэл байгаа эсэхийг мэдэхэд нь туслаарай.

Оролт

Энэ бодлогын өгөгдөл нь олон тестээс бүрдэнэ. Эхний мөрөнд нийт тестийн тоог харуулах нэг бүхэл тоо $t$ ($1≤t≤100 000$)-г агуулах тэмдэгт мөр байна. Тест бүрийн эхэнд нэг хоосон мөр байна.

Тест бүрийн эхний мөр нь харгалзан Поликарпын суудлын дугаар болон хоолны төрлийн тоог харуулах $m$, $k$ ($2≤m≤100000$, $1≤k≤100000$) бүхэл тоонуудыг агуулна.

Тестийн хоёр дахь мөр нь $a_{1}, a_{2}, ..., a_{k}$ ($1≤a_{i}≤100000$) гэсэн $k$ ширхэг бүхэл тоонуудын дарааллыг агуулна. Энд $a_{i}$ бол $i$-р хоол анх хичнээн ширхэг байсныг илтгэх тоо.

Дараагийн $m-1$ мөрүүдэд мөр тус бүрд өөрөөс нь өмнө сууж буй зорчигчдын хоол авахад тохиолдсон зүйлийн талаарх Поликарпын ажиглалтын мэдээллийг агуулна. Үүнд $j$-р мөр нь $t_{j}, r_{j}$ ($0≤t_{j}≤k, 0≤r_{j}≤1$) 2 бүхэл тоог агуулна. Энд $t_{j}$ нь $j$-р зорчигчид өгсөн хоолны дугаар (эсвэл хэрэв Поликарп зорчигчид ямар хоол өгснийг анзаараагүй бол 0 байна), $r_{j}$ нь $j$-р зорчигч урам хугарсан эсвэл үгүй эсэхээс шалтгаалан харгалзан $1$ эсвэл $0$ байна.

Өгөгдөлд $a_{i}$ тоонуудын нийлбэр хамгийн багадаа $m$-тэй тэнцүү байхаар өгөгдөнө. Энэ нь Поликарп үргэлж ямар нэг хоол авах боломжтой байна гэсэн үг юм.

Бүх тестийн $m$-үүдийн нийлбэр нь $100000$-аас хэтрэхгүй. Мөн бүх тестийн $k$-үүдийн нийлбэр $100000$-аас хэтрэхгүй.

Гаралт

Тест бүрт хариултыг нэг мөрөнд хэвлээрэй. "Y" эсвэл "N" үсгүүдээс бүрдсэн $k$ тэмдэгт мөрийг хэвлээрэй. Хэрэв Поликарпад онгоцны үйлчлэгч хоол өгөх үед $i$-р хоол дууссан байвал $i$ байрлалд "$Y$" хэвлэгдэнэ.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
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

Тэмдэглэл

Эхний тест дээр $2$ дахь зорчигчийн сонголтоос шалтгаалж эхний тестийн хариу дараах байдлаар үүсч болно:

  • Хэрэв тэр $1$-р хоолыг сонговол Поликарпад онгоцны үйлчлэгч хүрэх үед $1$-р хоол дууссан байна.
  • Хэрэв тэр $4$-р хоолыг сонговол Поликарпад онгоцны үйлчлэгч хүрэх үед $4$-р хоол дууссан байна.
  • Өөр тохиолдолд Поликарп $4$ төрлийн хоолноос алийг нь ч сонгох боломжтой.

Тиймээс хариулт нь "YNNY" байна.

Хоёр дахь тест дээр, жишээлбэл, дараах боломжит хувилбар байна. Нэгдүгээрт, эхний зорчигч зөвхөн $3$-р хоолыг, дараа нь $2$ дахь зорчигч $2$-р хоолноос авна. Дараа нь $3$ дахь зорчигч $3$ дахь хоолыг асуухад дууссан тул тэрээр амандаа бувтнан $2$-р хоолыг сонгоно. Дараа нь $4$ дэх зорчигч $4$-р хоолноос авах ба Поликарпад $1$-р, $4$-р, $5$-р хоолноос сонгох сонголт үлдэнэ.

Үүний нэгэн адилаар өөр нэг боломжит хувилбар бол онгоцны үйлчлэгч Поликарпад хүрч очих үед $1$-р болон $5$-р хоолны аль нэг нь дууссан байна (хэрэв $2$ дахь зорчигч эдгээр хоолны аль нэгийг авсан бол энэ нөхцөл үүснэ). Эндээс $4$-р хоолноос хангалттай их байгааг харж болох тул Поликарп үүнийг ямагт сонгох боломжтой байна. Тиймээс хариулт нь "YYYNY" байна.

Сэтгэгдлүүдийг ачааллаж байна...