F. Баавгай ба Хими

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

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

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

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

Лимак бол хими, урвал болон элементүүдийн хувирлыг сонирхон шохоорхдог ухаант хүрэн баавгай.

Лимакийн нутаг Бийрландад $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг элемент байдаг. Мөн элементүүдийг хувирган өөрчлөх чадалтай төхөөрөмж ч мөн бий. Төхөөрөмж бүр хоёр элементийг(өөр байх албагүй) илтгэх $a_{i}, b_{i}$ тоонуудаар тодорхойлогдоно. Өөрөөр хэлбэл энэ төхөөрөмжөөр $a_{i}$-г $b_{i}$ эсвэл $b_{i}$-г $a_{i}$ болгон өөрчлөх боломжтой. Бийрланд дах төхөөрөмжүүд тийм ч чанартай биш тул ихдээ нэг удаа л ашиглаж болохоор байдаг. $a_{i} = b_{i}$ байх боломжтой ба өөр төхөөрөмжүүд адил $a_{i}, b_{i}$ хосоор ч илэрхийлэгдэх боломжтой.

Рэйдвүүш нь Лимакийн хамгийн том дайсан бас өрсөлдөгч юм. Тэр Лимакийн химийн мэдлэгийг сорихыг хүсч байгаа аж. Тэд маргааш уулзах ба өөрсдийн бүх төхөөрөмжүүдээ авчирна. Лимакт $m$ төхөөрөмж бий, харин дайсандаа хэдий хэрийн юм байгааг түүнд гадарлах зүйл үгүй. Рэйдвүүш $x$ ба $y$ хоёр өөр элемент сонгоно. Лимак өөрийн болон Рэйдвүүшийн бүх төхөөрөмжийг хэрэглэх боломжтой. Тэр хэдэн ч төхөөрөмж ашиглаж болох ба тус бүрийг нь нэгээс олон удаа хэрэглэх боломжгүй. Лимак $x$ элементээс эхлэх ба эхлээд $y$ гаргаж авах ба буцаад түүнийг $x$ болгосон тохиолдолд даалгавар амжилттай гүйцэтгэгдсэн гэж үзнэ. Ингэвэл Рэйдвүүш Лимакийн химийн мэдлэгийг хүлээн зөвшөөрч зайгаа тавьж өгөх гэнэ.

Рэйдвүүшт өөрийн өөрийн дуртай хэсэг элементүүдийн хоосон бус олонлог байдаг ба тэр $x, y$ элементүүдээ энэ олонлогоос сонгоно. Олонлогт ямар элементүүд байдаг болон Рэйдвүүшт ямар төхөөрөмж байгаа талаар Лимак юу ч мэдэхгүй. Лимак тэр талаар $q$ ширхэг цуурхал (дараалал - queries) сонссон ба тэд тус бүрдээ Рэйдвүүшийн төхөөрөмж болоод дуртай элементүүдээс бүрдэнэ. Цуурхал бүрийн боломжит $x, y$ хосын хувьд даалгаврыг амжилттай гүйцэтгэж чадах эсэхээ Лимак мэдэхийг хүсч буй аж. Хэрэв тийм бол "YES" гэж хэвлэнэ үү. Харин Лимак гүйцэлдүүлж эс чадах $(x, y)$ хос өгөгдсөн олонлогоос олддог бол "NO" гэж хэвлэнэ.

Оролт

Эхний мөрөнд $n$, $m$, $q$ ($1 \le n, q \le 300 000, 0 \le m \le 300 000$) тоонууд өгөгдөнө, харгалзан элементүүдийн тоо, Лимакийн төхөөрөмжийн тоо, цуурхлын тоог илэрхийлнэ.

Дараагийн $m$ мөр тус бүр Лимакийн төхөөрөмжийг тодорхойлох $a_{i}$, $b_{i}$ ($1 \le a_{i}, b_{i} \le n$) тоонууд өгөгдөнө.

Цаашлаад $q$ цуурхлууд дараах байдлаар өгөгдөнө:

$i$-р цуурхлын эхний мөр $n_{i}$, $m_{i}$ ($1 \le n_{i} \le 300 000, 0 \le  m_{i} \le 300 000$) хоёр тоо агуулна. Хоёр дах мөрөнд Рэйдвүүшийн дуртай элементүүдийг илтгэх $n_{i}$ ширхэг $x_{i, 1}, x_{i, 2}, ..., x_{i, n_{i}}$ ($1 \le x_{i, j} \le n$) ялгаатай бүхэл тоо өгөгдөнө. $n_{i} = 1$ байх боломжтойг тэмдэглэе, энэ тохиолдолд ялгаатай элементийн хослол үгүй тул хариулт үргэлж "YES" буюу Лимак шууд ялна. Дараагийн $m_{i}$ мөрүүд тус бүрдээ $i$-р цуурхал дах Рэйдвүүшийн төхөөрөмжийг тодорхойлох $a_{i, j}, b_{i, j}$ ($1 \le a_{i, j}, b_{i, j}$) хос тоо өгөгдөнө.

Бүх цуурхлуудын хувьд $n_{i}$-үүдийн нийлбэрийг авахад $300 000$-аас хэтрэхгүй. Мөн $m_{i}$-үүдийн нийлбэр ч $300 000$-аас үл халина.

Заавал унш: Цуурхлуудыг онлайнаар боловсруулах тул, Рэйдвүүшийн дуртай олонлог болон түүний төхөөрөмжүүд хувиргаж чадах элементүүдийг мэдэхийн тулд дараах функцийг ашиглана уу:

int rotate(int element)  
{  
   element=(element+R)%n;  

   if (element==0) {  
       element=n;  
   }  

   return element;  
}

Энд $R$ нь анхлан $0$ утгатай байх ба хариулт "YES" байх бүрд дарааллын (query) тоогоор өсөх юм. Дарааллууд (query) $1$-ээс эхлэн оролт дах эрэмбээрээ дугаарлагдсан болно.

Гаралт

$q$ ширхэг мөр хэвлэнэ. $i$-р цуурхлын $x$, $y$ хос бүрийн ($x_{i, 1}, x_{i, 2}, ..., x_{i, n_{i}}$ олонлог дотроос) хувьд Лимак амжилтанд хүрэх бол "YES", үгүй бол "NO" гэж хэвлэнэ үү.

Орчуулсан: Төрбат

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

Оролт
6 5 4
1 2
2 3
3 4
2 4
5 6
2 0
4 2
2 1
6 2
3 4
3 2
6 3 4
2 5
4 6
2 1
1 2
1 2
Гаралт
YES
NO
YES
YES
Оролт
7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
7 2
1 2 3 4 5 6 7
4 5
6 7
7 2
1 2 3 4 5 6 7
4 6
5 7
Гаралт
NO
YES

Тэмдэглэл

Эхний жишээ:

Эхний цуурхлын хувьд Рэйшвүүдийн дуртай олонлог ${4, 2}$ ба түүнд ямар ч төхөөрөмж байхгүй. Лимак $4$-г $2$-рүү хөрвүүлж чадах ба (даалгаврын эхний хагас нь гүйцэлдсэн гэсэн үг) цааш нь $2$-г $3$-руу, $3$-г $4$-рүү хувиргана. Хариу "YES", Иймд $R$ $1$-ээр өснө.

Хоёр дах цуурхлын хувьд олонлог нь ${6, 2}$ ба төхөөрөмж $(3, 4)$ юм, харин $R$ нэгтэй тэнцүү. Иймд олонлог ${1, 3}$ ба машин $(4, 5)$ гэсэн үг. Хариу "NO", Иймд $R$ өөрчлөгдөхгүй.

Гурав дах цуурхалд олонлог нь ${6, 4, 3}$ ба төхөөрөмжүүд $(2, 5)$ , $(4, 6)$ буюу ${1, 5, 4}$, $(3, 6)$ , $(5, 1)$ болно. ($R=1$ тул)

Рэйдвүүшийн сонголтуудыг авч үзвэл:

  • Хэрвээ тэр $1$, $5$ элементүүдийг сонговол Лимак $1$-г $5$ руу, тэгээд $6$-г $3$ руу, $3$-г $2$ руу, $2$-г $1$ рүү хувиргаж чадна.
  • Хэрвээ тэр $5$, $4$ элеметүүдийг сонговол, Лимак $5$-г $6$ руу, $6$-г $3$ руу, $3$-г $4$ (даалгаврын эхний хагас!), $4$-г $2$ руу, $2$-г $1$ рүү, $1$-г $5$ руу хөрвүүлж чадна.
  • Хэрвээ $1$, $4$ элементүүдийг сонговол Лимак $1$-г $2$ руу, $2$-г $4$ рүү, $4$-г $3$ руу, $3$-г $6$ руу, $6$-г $5$ руу $5$-г $1$ рүү хувиргана.

Иймд Лимак даалгаврыг биелүүлж чадна. Хариулт "YES", мөн $R$ нь $3$-өөр өсч $4$ болно.

Сүүлийн цуурхал $ { 1, 2 } $, $(1, 2)$ нь $R$-н утгаас хамаарч ${ 5, 6 } $ , $(5, 6)$ болно. Одоо $2$ ширхэг $(5, 6)$ төрлийн төхөөрөмж байгаа тул Лимак мөн л даалгаврыг гүйцэтгэх боломжтой.

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