Sizga butun sonlardan iborat bo’lgan bir o’lchamli massiv va m ta so’rov berilgan.

Har bir so’rovda l , r juftliklar berilgan. Sizdan [l , r] qism massiv uchun quyidagi ifodani hisoblash talab etiladi.

Kiruvchi ma’lumotlar: Birinchi satrda n , m (1 ≤ n ,m ≤ 10⁵ ) butun sonlar. Ikkinchi satrda n ta son (1 ≤ a[i] ≤ 10⁶). Keyingi m ta qatorda l , r (1 ≤ l ≤ r ≤ n) juftliklari.

Chiquvchi ma’lumotlar: Yagona satrda masala yechimini chiqaring . Javob 2⁶³ – 1 dan oshmasligi kafolatlanadi.