C. Xor sequence

A₁ = 1

A₂ = 1

Aᵢ = |Aᵢ₋₁ − Aᵢ₋₂| ⊕ (Aᵢ₋₁ + Aᵢ₋₂) agar i > 2

Bu yerda ⊕ bitwise xor amalini anglatadi.

Shu shartlar asosida qurilgan A ketma-ketlik mavjud.

Sizning vazifangiz berilgan L, R va M sonlari uchun (A_L + A_(L+1) + A_(L+2) + … + A_R) mod M ning qiymatini, ya'ni ketma-ketlikning L - tartibdan R - tartibgacha bo'lgan elementlari yig'indisini M ga bo'lgandagi qoldiqni aniqlashdan iborat.

Kirish ma’lumotlari

Kirish faylining dastlabki satrida bitta butun son, T (1 ≤ T ≤ 2 × 10⁵) testlar soni kiritiladi.

Keyingi T ta satrda uchtadan butun son, L (1 ≤ L ≤ 10⁹), R (L ≤ R ≤ 10⁹) va M (1 ≤ M ≤ 10⁹) sonlari kiritiladi.

Kiritilgan M tub son ekanligi kafolatlanadi.

Chiqish ma’lumotlari

Har bir test uchun alohida qatorda bitta butun son, masala shartida so'ralgan qiymatni chop eting.