Problem 134: investitie

După o lungă activitate în domeniul instalațiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acțiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acțiuni, în M zile consecutive.

În prima zi, suma de bani investită în compania i este s[1][i] = a[i], pentru orice $i = \overline{1, N}$ , unde valorile a[i] sunt date.

Numerele a[1], a[2], ..., a[N] reprezintă o permutare a numerelor 1, 2, ..., N.

În ziua a j-a el va investi în compania i o sumă de bani egală cu s[j][i] = s[j − 1][a[i]], pentru orice zi $j = \overline{2, M}$ ̧și orice companie $i = \overline {1, N}$ .

Cerință

După finalizarea planului de investiții, Dorel vrea să realizeze Q statistici referitoare la sumele investite.

Fiind date Q seturi de valori $z_i, z_f, c_l, c_r$ , el dorește să afle ce sumă a investit în perioada cuprinsă între zilele $z_i$ și $z_f$ (inclusiv acestea), la companiile cu numere de ordine cuprinse între $c_l$ ̧si $c_r$ (inclusiv acestea).

Date intrare

Pe prima linie a fișierului de intrare investitie.in se află numerele N si M, separate prin spațiu.
Pe a doua linie se află valorile a[1], a[2], ..., a[N], separate prin spațiu.
Pe a treia linie se află valoarea lui Q.
Pe următoarele Q linii se află câte patru valori, $z_i, z_f, c_l, c_r$ , separate prin spațiu.

Date ieșire

În fișierul de ieșire investitie.out se vor afișa, pe linii diferite, sumele investite corespunzătoare fiecăreia din cele Q statistici din fișierul de intrare.

Restricții

1 ≤ N, Q ≤ 100 000
1 ≤ M ≤ 1 000 000 000
$1 ≤ z_i ≤ z_f ≤ M$
$1 ≤ c_l ≤ c_r ≤ N$
$0 ≤ c_r − c_l ≤ 100$
Pentru 10 puncte: M = 1
Pentru alte 20 puncte: 1 ≤ N, M ≤ 100, 1 ≤ Q ≤ 1 000
Pentru alte 12 puncte: 101 ≤ N, M ≤ 3 000
Pentru alte 24 puncte: 1 ≤ N ≤ 50
Pentru alte 34 puncte: Fără alte restricții

Exemple

investitie.in

8 3
3 1 7 2 6 4 5 8
5
1 1 3 7
1 2 1 4
1 3 2 8
2 3 3 6
3 3 3 3

investitie.out

Explicație

Sumele investite în cele trei zile, în acțiuni ale celor opt companii, vor fi:

3 1 7 2 6 4 5 8
7 3 5 1 4 2 6 8
5 7 6 3 2 1 4 8

Prima statistică cere suma investită în prima zi în companiile cu numere de ordine de la 3 la 7. Suma este
7 + 2 + 6 + 4 + 5 = 24.

A doua statistică cere suma investită în primele două zile în companiile cu numerele de ordine de la 1 la 4. Suma este (3 + 1 + 7 + 2) + (7 + 3 + 5 + 1) = 29.
Similar se calculează celelalte statistici.

investitie