3D Sums

Time limit: 1.5s Memory limit: 512MB Input: Output:

După seara de revelion, Armando și prietenii săi merg în pădure să se plimbe și ajung într-o zonă unde se fac săpături după minereuri. Ei decid să pună următorul pariu: cel care sapă zona cu cele mai multe minereuri primește toate minereurile pe care le găsesc ei în acea dimineață. Armando, fiind un băiat care umblă cu șiretlicuri, se gândește să vă ceară ajutorul, motiv pentru care vă spune următoarele informații despre zona în care vrea să facă săpături:

  • Zona are forma unui paralelipiped cu lățimea ll, lungimea LL și înălțimea HH și este împărțită în lLHl\cdot L\cdot H cuburi de 1 m31 \text{ m}^3;
  • Inițial, ei consideră că fiecare cub de 1 m31 \text{ m}^3 are 00 minereuri în el, după care efectuează Q1Q_1 teste și află, pe rând, noi informații despre numărul de minereuri dintr-o subzonă paralelipipedică analizată. Mai exact, în urma unei analize, numărul cunoscut de minereuri din fiecare cub din subzona respectivă crește cu o valoare vv.

Cerință

Armando are Q2Q_2 subzone despre care se întreabă dacă merită să fie săpate, deci vrea să știe câte minereuri ar obține din fiecare. O subzonă este (unic) determinată de două colțuri (x1,y1,z1)(x_1, y_1, z_1), (x2,y2,z2)(x_2, y_2, z_2) diagonal opuse, cu x1x2x_1 \leq x_2, y1y2y_1 \leq y_2 și z1z2z_1 \leq z_2.

Date de intrare

Pe prima linie se găsesc cinci numere naturale, ll, LL, HH, Q1Q_1 și Q2Q_2 (cu semnificațiile din enunț). Pe următoarele Q1Q_1 linii se află câte șapte numere naturale, x1x_1, y1y_1, z1z_1, x2x_2, y2y_2, z2z_2, vv care reprezintă subzona și valoarea cu care crește numărul de minereuri cunoscute din fiecare cub din subzona respectivă. Pe următoarele Q2Q_2 linii se află câte șase numere naturale, x1x_1, y1y_1, z1z_1, x2x_2, y2y_2, z2z_2, care reprezintă subzonele pentru care Armando se întreabă care este numărul de minereuri cunoscute.

Date de ieșire

Se vor afișa, în ordine, pe linii separate, răspunsurile celor Q2Q_2 întrebări.

Restricții și precizări

  • 1l,L,H3001 \leq l, L, H \leq 300;
  • 1Q1,Q2500 0001 \leq Q_1, Q_2 \leq 500 \ 000;
  • 1x1x2l1 \leq x_1 \leq x_2 \leq l;
  • 1y1y2L1 \leq y_1 \leq y_2 \leq L;
  • 1z1z2H1 \leq z_1 \leq z_2 \leq H;
  • 1v100 0001 \leq v \leq 100 \ 000;
  • Paralelipipedul se consideră că are colțurile la (1,1,1)(1, 1, 1) și la (l,L,H)(l, L, H);
  • Pentru 3030 de puncte, Q1,Q230Q_1,Q_2 \leq 30;
  • Pentru restul de 7070 de puncte, nu există restricții suplimentare.
  • Dacă folosiți std::cin pentru citire, se recomandă folosirea:
std::cin.tie(0)->sync_with_stdio(false);

Exemplul 1

stdin

10 11 12 5 6
1 1 1 3 4 5 7
1 2 3 4 8 3 4
3 5 11 7 10 12 104
5 10 2 6 11 8 1005
9 7 8 10 10 10 232
1 2 1 7 8 9
2 3 4 9 7 8
9 10 11 10 11 12 
2 2 2 3 3 4
5 3 2 10 9 11
3 4 3 5 6 5

stdout

427
288
0
100
5736
45

Exemplul 2

stdin

6 6 6 2 1
3 2 2 5 4 3 3
3 5 5 4 6 6 10
1 1 1 6 6 6

stdout

134

Log in or sign up to be able to send submissions!