E. Ваня ба хөлөг

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

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

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

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

Ваня $n×n$ нүднүүд бүхий хэмжээтэй хөлөг дээгүүр алхахаар шийджээ. Хөлөг нь $m$ алимны модтой. $i$-р алимны мод нь $(x_{i}, y_{i})$ координаттай нүдэнд байрлана. Ваня $(dx, dy)$ векторын дагуу нүүлээ. Өөрөөр хэлбэл, хэрвээ Ваня одоо $(x, y)$ дээрх нүд дээр байгаа бол $((x + dx)\ mod\ n, (y + dy)\ mod\ n)$ нүдэнд очно гэсэн үг юм. Вектор нь дараах нөхцөлийг хангана: $gcd(n,dx) = gcd(n,dy) = 1$, Энд $gcd(a,b)$ нь $a$ ба $b$ тоонуудын хамгийн их ерөнхий хуваагч. Ваня өмнө очсон нүдэндээ дахиж очиход тэр замаа дуусгана.

Ваня аль болох их алимны модоор дайрахын тулд хөлгийн аль нүднээс замаа эхлүүлэх хэрэгтэйг бодож байна.

Оролт

Эхний мөрөнд хөлгийн хэмжээ, алимны модны тоо, Ванягийн хөдөлгөөний векторыг харуулах $n, m, dx, dy$ ($1≤n≤10^{6}$, $1≤m≤10^{5}$, $1≤dx, dy≤n$) бүхэл тоонуудыг агуулна. Дараагийн $m$ мөрүүд алимны моднуудын координатуудыг харуулах $x_{i}, y_{i}$ ($0≤x_{i}, y_{i}≤n-1$) бүхэл тоонуудыг агуулна. Нэг нүдэнд олон алимны мод байж болно.

Гаралт

Замаа эхлүүлэхэд тохиромжтой нүдний координатыг харуулах, зайгаар тусгаарлагдсан хоёр тоог хэвлээрэй. Олон хариулт байвал алийг нь ч хэвлэж болно.

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

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

Оролт
5 5 2 3
0 0
1 2
1 3
2 4
3 1
Гаралт
1 3
Оролт
2 3 1 1
0 0
0 1
1 1
Гаралт
0 0

Тэмдэглэл

Эхний жишээнд Ванягийн зам $(1, 3)-(3, 1)-(0, 4)-(2, 2)-(4, 0)-(1, 3)$ байна.

Хоёр дахь жишээнд $(0, 0)-(1, 1)-(0, 0)$ байна.

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