E. Дразил ба түүний жаргалтай найзууд (хүнд)

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

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

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

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

Дразил их олон найзтай. Тэдгээрийн зарим нь жаргалтай харин зарим нь гунигтай байгаа. Дразил найзуудаа бүгдийг нь жаргалтай болгохыг хүсчээ. Тэгээд тэрээр дараах төлөвлөгөөг зохиожээ.

Түүний найзууд дунд $n$ хөвгүүн, $m$ охин байдаг. Тэдгээрийг харгалзан $0$-ээс $n-1$ хүртэл, $0$-ээс $m-1$ хүртэл дугаарлая. $i$ дэх өдөр Дразил $(i\ mod\ n)$ дугаарын хөвгүүн болон $(i\ mod\ m)$ дугаарын охиныг хоолонд урина. (Дразил програмист учир $i$ нь $0$-ээс эхлэнэ). Хэрэв уригдсан хоёр хүний нэг нь жаргалтай бол нөгөөх нь жаргалтай болно. Хоёулаа гунигтай бол өөрчлөлт орохгүй. Хэрэв нэгэнт жаргалтай болсон л бол үргэлж жаргалтай болно.

Дразил энэхүү төлөвлөгөөгөөрөө хамгийн хурданаар хэд дэхь өдөртөө бүх найзуудаа жаргалтай болгож чадахаа мэдэхийг хүсчээ.

Оролт

Эхний мөрөнд $n$ болон $m$ ($1 ≤ n, m ≤ 10^9$) бүхэл тоонууд байна.

Хоёр дахь мөрөнд жаргалтай хөвгүүдийн тоо болох $b$ $(0 ≤ b ≤ min(n, 10^5))$ болон тэдгээрийн дугаарууд болох $x_{1}, x_{2}, ..., x_{b}$ ($0 ≤ x_{i} < n$) байна.

Гурав дахь мөрөнд жаргалтай охидын тоо болох $g$ $(0 ≤ g ≤ min(m, 10^5))$ болон тэдгээрийн дугаар болох $y_{1}, y_{2}, ... , y_{g}$ ($0 ≤ y_{j} < m$) тоонууд байна.

Өгөгдөлд ядаж нэг хүн гунигтай байх болно.

Гаралт

Дразил энэхүү төлөвлөгөөг ашиглан хамгийн хурданаар хэддэх өдөр бүх найзуудаа жаргалтай болгож чадахыг хэвлэ. Хэрэв чадахгүй бол "-1" гэж хэвлэ.

Орчуулсан: gmunkhbaatarmn, Бат-Од

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

Оролт
2 3
0
1 0
Гаралт
4
Оролт
2 4
1 0
1 2
Гаралт
-1
Оролт
2 3
1 0
1 1
Гаралт
2
Оролт
99999 100000
2 514 415
2 50216 61205
Гаралт
4970100515

Тэмдэглэл

$(i\ mod\ k)$-аар $i$ тоог $k$ тоонд хуваахад гарах үлдэгдлийг тэмдэглэнэ.

Эхний жишээнд:

  • $0$ дэх өдөр Дразил $0$ дэх хөвгүүн ба $0$ дэх охиныг урина. $0$ дэх охин жаргалтай байгаа тул $0$ дэх хөвгүүн жаргалтай болно.
  • $1$ дэх өдөр Дразил $1$ дэх хөвгүүн ба $1$ дэх охиныг урина. Тэд хоёул гунигтай байгаа тул өөрчлөлт орохгүй.
  • $2$ дахь өдөр Дразил $0$ дэх хөвгүүн ба $2$ дахь охиныг урина. $0$ дэх хөвгүүн жаргалтай байгаа тул $2$ дахь охин жаргалтай болно.
  • $3$ дахь өдөр Дразил $1$ дэх хөвгүүн ба $0$ дэх охиныг урина. $0$ дэх охин жаргалтай байгаа тул $1$ дэх хөвгүүн жаргалтай болно.
  • $4$ дэх өдөр Дразил $0$ дэх хөвгүүн ба $1$ дэх охиныг урина. $0$ дэх хөвгүүн жаргалтай байгаа тул $1$ дэх охин мөн жаргалтай болно.

Ингээд Дразилын бүх найзууд жаргалтай болох юм.

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