Фибоначчи-ийн дараалал гэдэг нь рекурсив хамаарлаар тодорхойлогдох бүхэл тооны рекурсив дараалал юм.

$F_{n} = s_{n - 1}*F_{n - 1} + s_{n - 2}*F_{n - 2}$ ба $F_{0} = 0, F_{1} = 1$

$s$ дараалал нь хязгааргүй бөгөөд $N$ урттай цикл бүхий бараг цикл-лэг дараалал юм. Хэрэв ($i ≥ N$) байх хязгаартай тооны $s_{i}$-ын утгыг тооцохгүйгээр $i ≥ N$ бүрийн хувьд байвал $s$ дарааллыг $N$ урттай цикл бүхий бараг цикл-лэг дараалал гэж нэрлэнэ.

Дараах жишээ нь 4 урттай цикл бүхий бараг цикл-лэг дараалал байна:

s = (5,3,8,11,5,3,7,11,5,3,8,11,…)

тэнцэтгэлийг хангахгүй байгаа $s$-ын цорын ганц утга нь $s_{6}$ ($s_{6} = 7$ болон $s_{2} = 8$) болохыг анхаарна уу. Танд $s_{0}, s_{1}, ...s_{N - 1}$ болон ($i ≥ N$) байх бүх $s$ дарааллын утгууд өгөгдөнө.

-г олно уу.

Оролт

Эхний мөрөнд 2 тоо $K$ болон $P$ өгөгдөнө. 2-дахь мөрөнд ганц тоо $N$ өгөгдөнө. 3-дахь мөрөнд зайгаар тусгаарлагдсан $N$ ширхэг тоо өгөгдөнө, эдгээр нь $s$ дарааллын эхний $N$ тоог илэрхийлнэ. 4-дэх мөрөнд ганц тоо $M$ өгөгдөх ба энэ нь $s$ дарааллын байх утгуудын тоог илэрхийлнэ. Дараагийн $M$ мөрийн мөр болгонд 2 тоо $j$ болон $v$ өгөгдөх ба эдгээр нь болон $s_{j} = v$ болохыг зааж байгаа юм. Бүх j-нууд нь ялгаатай байна.

• $1 ≤ N, M ≤ 50000$
• $0 ≤ K ≤ 10^{18}$
• $1 ≤ P ≤ 10^{9}$
• $1 ≤ s_{i} ≤ 10^{9}$, бүх $i = 0, 1, ...N - 1$ -ын хувьд
• $N ≤ j ≤ 10^{18}$
• $1 ≤ v ≤ 10^{9}$
• Бүх утгууд нь бүхэл тоо байна

Гаралт

-тай тэнцүү байх ганц бүхэл тоог хэвлэнэ үү.