A. Баавгай ба үзэгдэх найзууд

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

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

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

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

Лимак бол туйлын жижиг баавгай. Тэрээр сошиал сүлжээгээр бусад баавгайнуудтай холбогдох дуртай. Түүнд $n$ найз байдаг ба тэдгээрийн $i$-дахь найзтайгаа харилцах түүний харилцаа нь ер бусын бүхэл тоо $t_{i}$-аар дүрслэгдэх юм. Энэ утга нь том байх тусмаа илүү сайн нөхөрлөл байх юм. Ямар ч 2 найз нь ижил $t_{i}$ утгатай байхгүй.

Баавгайнуудын хувьд хавар бол эхлэл ба өвлийн унталтын төгсгөл байдаг. Лимак саяхан сэрсэн ба сошиал сүлжээнд нэвтэрч оржээ. Түүний бүх найзууд нь унтсаар байгаа ба иймд тэдгээрийн нэг нь ч онлайн биш байгаа. Тэдгээрийн хэсэг (магадгүй бүгд) нь дараагийн цагуудад онлайн болох ба ямар нэг цагт нэг нь онлайн болно.

Систем онлайн байгаа найзуудыг үзүүлнэ. Дэлгэцэн дээр хамгийн ихдээ $k$ найзуудыг үзүүлэх хоосон зай байна. Хэрэв $k$-аас олон тооны найз онлайн байвал систем тэдгээрийн зөвхөн хамгийн сайн $k$-ын үзүүлнэ -- энэ нь хамгийн том $t_{i}$-тай нь байх юм.

Таны даалгавар бол 2 төрлийн асуултуудыг шийдэх:

  • "$1 id$" -- $id$-дахь найз онлайн болно гэсэн үг. Мөн тэр найз нь өмнө нь онлайн байгаагүй байна.
  • "$2 id$" -- систем $id$-дахь найзыг үзүүлэх эсэхийг шалгана. Салангид мөрөнд "YES" эсвэл "NO" гэж хэвлэнэ үү.

Та Лимак-д туслан бүх 2-дахь төрлийн асуултуудад хариулж чадах уу?

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $k$ болон $q$ ($1 ≤ n, q ≤ 150 000, 1 ≤ k ≤ min(6, n)$) өгөгдөнө -- эдгээр нь харгалзан найзуудын тоо, систем үзүүлэх онлайн найзуудын дээд тоо болон асуултуудын тоог илэрхийлнэ.

2-дахь мөрөнд $n$ бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($1 ≤ t_{i} ≤ 10^{9}$)-ууд өгөгдөх ба энд $t_{i}$ нь Лимак $i$-дахь найзтайгаа хэр сайн харилцаатайг илэрхийлнэ.

Дараагийн $q$ мөрийн $i$-дахь мөрөнд 2 бүхэл тоо $type_{i}$ болон $id_{i}$ ($1 ≤ type_{i} ≤ 2, 1 ≤ id_{i} ≤ n$) өгөгдөнө -- эдгээр нь $i$-дахь асуултыг илэрхийлнэ. Хэрэв $type_{i} = 1$ байвал $id_{i}$-дахь найз нь онлайн болно. Хэрэв $type_{i} = 2$ байвал та $id_{i}$-дахь найзыг систем үзүүлсэн эсэхийг шалгана.

Эхний төрлийн ямар ч 2 асуултууд нь ижил $id_{i}$-тай байхгүй учир нь нэг найз нь 2 удаа онлайн болж чадахгүй. Мөн, дор хаяж нэг асуулт нь 2-дахь төрлийн байна иймд гаралт нь хоосон байхгүй юм.

Гаралт

2-дахь төрлийн асуулт бүрийн хувьд хариулттай нэг мөрийг хэвлэнэ -- Хэрэв өгөгдсөн найзыг систем үзүүлэх бол "YES" (хашилтгүйгээр) ба бусад тохиолдолд "NO" (хашилтгүйгээр) гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
4 2 8
300 950 500 200
1 3
2 4
2 3
1 1
1 2
2 1
2 2
2 3
Гаралт
NO
YES
NO
YES
YES
Оролт
6 3 9
50 20 51 17 99 24
1 3
1 4
1 5
1 2
2 4
2 2
1 1
2 4
2 3
Гаралт
NO
YES
NO
YES

Тэмдэглэл

Эхний жишээнд, Лимак бүгд анхандаа унтаж байгаа $4$ найзтай байна. Эхлээд, систем хэнийг ч үзүүлэхгүй учир нь хэн ч онлайн биш байна. Дараах $8$ асуултууд байна:

  1. "$1 3$" -- $3$-дахь найз онлайн болно.
  2. "$2 4$" -- Бид $4$-дэх найзыг систем үзүүлэх эсэхийг шалгана. Тэрээр онлайн биш тул бид "NO" гэж хэвлэнэ.
  3. "$2 3$" -- Бид $3$-дэх найзыг систем үзүүлсэн эсэхийг шалгана. Одоо тэрээр цорын ганц онлайн байгаа найз ба систем түүнийг үзүүлнэ. Иймд бид "YES" гэж хэвлэх ёстой.
  4. "$1 1$" -- $1$-дэх найз онлайн болно. Систем одоо $1$ болон $3$-дахь найзуудыг 2-ууланг нь үзүүлнэ.
  5. "$1 2$" -- $2$-дахь найз онлайн болно. Одоо $3$ найз онлайн байх боловч бидэнд $k = 2$ гэж өгөгдсөн иймд систем зөвхөн 2 найз-ыг үзүүлнэ. Лимак $1$-дэх найзтайгаа бусад 2 онлайн байгаа найзуудаасаа муу харилцаатай тул систем $1$-дэх найзыг үзүүлэхгүй.
  6. "$2 1$" -- "NO" гэж хэвлэнэ.
  7. "$2 2$" -- "YES" гэж хэвлэнэ.
  8. "$2 3$" -- "YES" гэж хэвлэнэ.
Сэтгэгдлүүдийг ачааллаж байна...