Курияма тошлари

Куриямада $n$ та тош бор, $i$-тошнинг нархи $v_i$. У икки турдаги савол беради:

1. 1 l r — $v_l + v_{l+1} + \ldots + v_r$ йиғиндиси.

Ҳар бир саволга жавоб беринг.

Биринчи қаторда $n$ ($1 \le n \le 10^5$). Иккинчи қаторда $n$ та бутун сон $v_i$ (). Учинчи қаторда (). Кейинги та қаторда , , (, ).

Ҳар бир савол учун алоҳида қаторда битта сон.

Иккита префикс массиви тузинг: бири асл массив учун, иккинчиси сараланган нусха учун. Ҳар бир савол — тегишли массивда $p_r - p_{l-1}$. Ҳар бир саволда қайта саралаш $O(m \cdot n \log n)$ — жуда секин.