D. Бяцхан одой морь ба аялгуун элемент

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

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

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

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

Аялгуун Элемент гэдэг нь аялгуун бодит байдлыг дүрсэлсэн зургаан ер бусын бүтээл юм. Тэд бол маргаангүй Экүйстриагийн хамгийн хүчит зүйл юм. Аялгуун Элемент дотор 0-ээс $n - 1$ хүртэл дугаарлагдсан орой бүхий граф бий. Энд $n$ нь хоёрын ямар нэгэн зэрэгт байна. $n = 2^{m}$.

Аялгуун Элементийн энерги тогтмол хөдөлгөөнд байдаг. Эртний номон дээр $i$ хугацаан дахь $u$ оройн энергийн хэмжээ $(e_{i}[u])$ нь :

байна гэж байжээ.

Энд $b[]$ нь $m + 1$ урттай тоон дараалал бүхий хөрвүүлэлтийн коэффициент. $f(u, v)$ нь $(u xor v)$ тооны хоёртын бичлэг дэх нэгүүдийн тоо.

Хөрвүүлэлтийн коэффициентууд болон 0 хугацаан дахь энергийн тархалт $(e_{0}[])$ өгөгджээ. Твайлайт Спарклэд $t$ хугацаан дахь энергийн тархалт $(e_{t}[])$-г олоход туслаарай. Хариу том тоо байж болох тул $p$ тоонд хуваан үлдэгдлийг олно уу.

Оролт

Эхний мөрөнд $m$, $t$ ба $p$ ($1 ≤ m ≤ 20; 0 ≤ t ≤ 10^{18}; 2 ≤ p ≤ 10^{9}$) бүхэл тоонууд өгөгдөнө. Дараагийн мөрөнд $e_{0}[i]$ ($1 ≤ e_{0}[i] ≤ 10^{9}; 0 ≤ i < n$) гэсэн $n$ ($n = 2^{m}$) ширхэг тоонууд өгөгдөнө. Дараагийн мөрөнд $b[i]$ ($0 ≤ b[i] ≤ 10^{9}; 0 ≤ i ≤ m$) гэсэн $m + 1$ ширхэг бүхэл тоо өгөгдөнө.

Гаралт

Хариуг $n$ мөрөнд хэвлэ. $i$ дэх мөрөнд $e_{t}[i]$ тоог $p$ тоонд хуваан үлдэгдлийг хэвлэ.

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

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

Оролт
2 2 10000
4 1 2 3
0 1 0
Гаралт
14
6
6
14
Сэтгэгдлүүдийг ачааллаж байна...