Masala #0668

Ikki do’st Hoshimjon va Orif ta’tilning keyingi n kuni davomida gilos terishmoqchi. Ammo do’stlar har doim ham o’zlari xohlaganchalik giloslarni tera olishmaydi va shunga qarab ularning kayfiyati o’zgarishi mumkin. Boshqacha qilib aytkanda do’stlar \(i\)-kuni gilos tersa Hoshimjonni kayfiyatiga \(a_i\), Orifnikiga esa \(b_i\) qo’shiladi \((-10^6 ≤ a_i, b_i ≤ 10^6)\).

Sizga \(l\) va \(r\) ko’rinishidagi \(q\) ta so’rov beriladi. Agar do’stlar \([l..r]\) oralig’idagi kunlarning har birida gilos teradigan bo’lsa, shu oraliqdagi do’stlarning umumiy xursandchilik koeffitsientini toping. Umumiy xursandchilik koeffitsienti quyidagicha hisoblanadi:

• Dastlab, \(l\)-kundan oldin, har bir bolaning kayfiyati 0 ga teng bo’ladi
• \(i\) - kuni \((l ≤ i ≤ r)\) Hoshimjonning kayfiyati \(a_i\) ga, Orifni kayfiyati \(b_i\) ga o’zgaradi
• \(i\) - kun \((l ≤ i ≤ r)\) uchun do’stlarning xursandchilik koeffitsienti Hoshimjon va Orifni shu kundagi kayfiyatlarini kattasiga teng bo’ladi
• umumiy xursandchilik koeffitsienti barcha \(r - l + 1\) kunlardagi xursandchilik koeffitsientlari yig’indisiga teng.

To’liqroq tushunish uchun quyida keltirilgan misolga qarang.

Birinchi qatorda kunlar soni \(n\) va so’rovlar soni \(q\) kiritiladi \((1 ≤ n, q ≤ 10^5)\). Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, ..., a_n\) va 3-qatorda ham \(n\) ta butun son \(b_1, b_2, ..., b_n\) kiritiladi \((-10^6 ≤ a_i, b_i ≤ 10^6)\).

Keyingi \(q\) ta qatorda so’rovlar \(l\) va \(r\) butun sonlari ko’rinishida beriladi \((1 ≤ l ≤ r ≤ n)\).

1-subtask(9 ball): \(n, q ≤ 1000\).
2-subtask(7 ball): \(a_i = 1, b_i = 0, n, q ≤ 10^5\)
3-subtask(13 ball): \(a_i ≥ 0, b_i = 0, n, q ≤ 10^5\)
4-subtask(29 ball): \(b_i = 0, n, q ≤ 10^5\)
5-subtask(42 ball): \(n, q ≤ 10^5\)

Har bir so’rov uchun umumiy xursandchilik koeffitsientini chiqaring.