Яаш эцэст нь хамгийн урт Фибоначчи-иш дарааллын уртыг тооцохоос залхжээ.Тэрээр одоо илүү төвөгтэй зүйл сонирхож байгаа бөгөөд тухайлбал Фибоначчи-иш чадлын талаар сонирхож байгаа юм.

$a_{i}$ цувааны Фибоначчи-иш чадал гэдэг нь дараах байдлаар бодогдоно:

1. Хэрэв $a_{i} = a_{j}$ байх $i < j$-ууд оршин байвал бүх $j$ элементүүдийг цуваанаас хасна.
2. Тэгээд үлдсэн элементүүдийг өсөх дарааллаар байрлуулна, өөрөөр хэлбэл $a_{1} < a_{2} < ... < a_{n}$.
3. Чадлыг бодохдоо $P(a) = a_{1}*F_{1} + a_{2}*F_{2} + ... + a_{n}*F_{n}$ томьёогоор бодох ба энд $F_{i}$-аар $i$-дахь Фибоначчийн тоог тэмдэглэв(тодруулах үүднээс тэмдэглэлийг үзнэ үү).

Танд $n$ урт бүхий $a_{i}$ цуваа болон $l_{j}$-аас $r_{j}$-ын хооронд байх $q$ ширхэг завсар өгөгдөнө.$j$ завсар бүрийн хувьд та $a_{i}$-ын $l_{j}$-аас $r_{j}$-ын хооронд байх элементүүдийг дээрх зааврын дагуу хассан цуваа болох $b_{i}$-ын Фибоначчи-иш чадлыг олох юм.Тус утгыг $m$ модул-аар бодож олно уу.

Оролт

Эхний мөрөнд харгалзан анхны цувааны урт болон модул-ыг илэрхийлэх бүхэл тоонууд $n$ болон $m$ ($1 ≤ n, m ≤ 30 000$) өгөгдөнө.

Дараагийн мөрөнд цувааны элементүүд болох $n$ ширхэг бүхэл тоонууд $a_{i}$ ($0 ≤ a_{i} ≤ 10^{9}$) өгөгдөнө.

Дараа нь завсрын тоо болох $q$ ($1 ≤ q ≤ 30 000$) өгөгдөнө.

Сүүлийн $q$ ширхэг мөрөнд Фибоначчи-иш чадлыг нь олох ёстой завсруудыг илэрхийлэх хос бүхэл тоо $l_{i}$ болон $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) өгөгдөнө.

Гаралт

$q$ ширхэг мөрөнд хэвлэх ба $i$-дахь мөрөнд $i$-дахь завсрын Фибоначчи-иш чадлыг $m$ модул-аар бодсон утгыг хэвлэнэ.

Фибоначчийн тоонууд гэдэг нь дараах байдлаар тодорхойлогдоно:

1. $F_{1} = F_{2} = 1$.
2. Бүх $n > 2$-ын хувьд $F_{n} = F_{n - 1} + F_{n - 2}$ байна.

Эхний даалгавар дээр, дэд цуваа [1,2,1] нь үйлдлийн дагуу {1,2} цуваа болно. Түүнчлэн, энэ дэд цувааны чадал нь 1*1+2*1=3 байна.