E. Фурукава Нагисагийн мод

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

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

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

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

Нэгэн удаа Фурукава Нагисагийн төрсөн өдрөөр Оказаки Томояа мод бэлэглэж гэнэ. Мод ихэд онцгой бөгөөд орой бүр дээр нь тоо байдаг. $i$ дугаарын орой дээр $v_{i}$ тоо байгаа гэе. Фурукава Нагиса болон Оказаки Томояа нар энэхүү модоор тоглохыг хүсчээ.

$(s, e)$ гэдгээр $s$ оройгоос $e$ орой хүрэх замыг тэмдэглэе. Мөн $(s, e)$ замд тааралдах тоон дарааллыг $S(s, e)$ гэж тэмдэглэе. $G(S(s, e))$ гэдгээр дараахь утгыг илэрхийлнэ: $S(s, e)$ нь $z_{0}, z_{1}...z_{l - 1}$ гэсэн дараалал байг. Тэгвэл $G(S(s, e)) = z_{0} × k^{0} + z_{1} × k^{1} + ... + z_{l - 1} × k^{l - 1}$ гэж тодорхойлно. Хэрэв $(s, e)$ зам нөхцөлийг хангаж байвал $(s, e)$ зам нь Фурукава Нагисагийн зам болох ба бусад тохиолдолд Оказаки Томояагийн зам болно.

Хэн нь илүү олон зам цуглуулсан болохыг тооцоолох их хялбар тул тэд арай өөрөөр тоглох болов. Фурукава Нагиса хэрэв $(p_{1}, p_{2})$ ба $(p_{2}, p_{3})$ замууд түүнийх бол $(p_{1}, p_{3})$ зам мөн түүнийх гэж бодож байгаа. Мөн тэрээр $(p_{1}, p_{2})$ ба $(p_{2}, p_{3})$ замууд Оказаки Томояагийн зам бол $(p_{1}, p_{3})$ мөн Оказаки Томояагийн зам гэж бодож байгаа. Гэвч энэхүү бодол нь үргэлж зөв байсангүй. Тиймээс Фурукава Нагиса хэчнээн $(p_{1}, p_{2}, p_{3})$ гурвалын хувьд дээрх өгүүлбэр үнэн болохыг мэдэхийг хүсэв. Энэхүү даалгаврыг гүйцэтгэнэ үү.

Оролт

Эхний мөрөнд $n$, $y$, $k$ ба $x$  $(1 ≤ n ≤ 10^{5}; 2 ≤ y ≤ 10^{9}; 1 ≤ k < y; 0 ≤ x < y)$ гэсэн дөрвөн бүхэл тоо байна. $n$ нь модны оройн тоо. $y$ анхны тоо байна.

Хоёр дахь мөрөнд $n$ бүхэл тоо байх ба $i$ дэх нь $v_{i} (0 ≤ v_{i} < y)$ байна.

Дараагийн $n - 1$ мөр бүрт холбогдсон оройн дугааруудыг илэрхийлэх хоёр бүхэл тоо байна. Оройнууд 1-ээс $n$ хүртэл дугаарлагдсан байна.

Гаралт

Фурукава Нагисагийн бодож байгааг хангах гурвалын тоог хэвлэ.

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

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

Оролт
1 2 1 0
1
Гаралт
1
Оролт
3 5 2 1
4 3 1
1 2
2 3
Гаралт
14
Оролт
8 13 8 12
0 12 7 4 12 0 8 12
1 8
8 4
4 6
6 2
2 3
8 5
2 7
Гаралт
341
Сэтгэгдлүүдийг ачааллаж байна...