$n$ тооноос бүрдсэн $a$ массив байна гэж үзье. Массивын элементүүд $1$-ээс $n$ хүртэл эрэмбэлэгдсэн байна. $тэгш$ нь $a$ ($even_{i} = a_{2i}$, $1 ≤ 2i ≤ n$)-ын дугаар нь тэгш байх тоонуудаас бүрдсэн массив бол, $сондгой$ нь $a$ ($odd_{i} = a_{2i - 1}$, $1 ≤ 2i - 1 ≤ n$)-ын дугаарууд нь сондгой байх тоонуудаас бүрдсэн массив юм. Ингээд дараах аргаар $F(a)$ массивын өөрчлөлтийг хийцгээе:

• Хэрэв $n > 1$, $F(a) = F(сондгой) + F(тэгш)$ бол, энд "$ + $" нь массивын тасралтгүй байдлыг илэрхийлж байна. (холбогдсон байна)

• Хэрэв $n = 1$, $F(a) = a$

$1, 2, 3, ..., n$ гэх мэт $n$ ширхэг тооноос бүрдсэн $a$ массив байна. $a$ ($b = F(a)$)-д массивд өөрчлөлт хийсний үр дүнд $b$ массив бий болсон. Танд $(l, r, u, v)$ хэлбэртэй $m$ ширхэг асуулга өгөгджээ. Та асуулга тус бүрт $b_{i}$, $l ≤ i ≤ r$, $u ≤ b_{i} ≤ v$ тоонуудын нийлбэрийг олох ёстой. Та асуулгын модуль хариу $mod$-г олох ёстой.

Оролт

Эхний мөрөнд $n$, $m$, $mod$ ($1 ≤ n ≤ 10^{18}, 1 ≤ m ≤ 10^{5}, 1 ≤ mod ≤ 10^{9}$) гэсэн гурваг бүхэл тоо агуулагдна. Дараагийн $m$ мөрүүд нь асуулгын тодорхойлно. Асуулга тус бүр нь $l$, $r$, $u$, $v$ ($1 ≤ l ≤ r ≤ n$, $1 ≤ u ≤ v ≤ 10^{18}$) гэсэн 4 бүхэл тоогоор тодорхойлогдоно.
C++ дахь 64 бит бүхэл тоог унших болох бичихдээ %lld нарийвчлал ашиглахгүйг анхаарна уу. Үүний оронд %I64d нарийчлал ашиглаж болно.

Гаралт

Тус бүр нь асуулгын үр дүнгийн үлдэгдэл модуль $mod$ болох бүхэл тоо агуулсан $m$ мөрүүд хэвлэнэ үү.

Эхний жишээг харцгаая: Эхлээд $b = F(a) = F([1, 2, 3, 4])$ гэсэн массив бүтээцгээе. * Алхам 1. $F([1, 2, 3, 4]) = F([1, 3]) + F([2, 4])$ * Алхам 2. $F([1, 3]) = F([1]) + F([3]) = [1] + [3] = [1, 3]$ * Алхам 3. $F([2, 4]) = F([2]) + F([4]) = [2] + [4] = [2, 4]$ * Алхам 4. $b = F([1, 2, 3, 4]) = F([1, 3]) + F([2, 4]) = [1, 3] + [2, 4] = [1, 3, 2, 4]$

Ингээд $b = [1, 3, 2, 4]$ байна. Эхлээд эхний асуулга $l = 2, r = 3, u = 4, v = 5$-г харцгаая. $b$ массивын хоёр болон гурав дахь байрлал нь $[4, 5]$ цуваанд тоо байхгүй байна. Тиймээс нийлбэр нь мэдээж 0-тэй тэнцүү байна.

Хоёр дахь асуулга $l = 2, r = 4, u = 1, v = 3$-г харцгаая. Хоёр болон гурав дахь байрлалд $[1, 3]$ цуваанд хамаарах хоёр тоо байгаа ба эдгээрийн нийлбэр 5-тай тэнцүү байна.