rarwall

Problem Description

Rar the Cat wants to build a wall of L units long. Each unit of the wall can have different height, with the first unit having height H0. Units of the walls are labeled from 0 to L-1.

Rar has a total of M+1 proposals to build the wall. In proposal 0, Rar the Cat has not started planning for the wall yet. Hence, all Hi = 0 for proposal 0.

For each subsequent proposal x, Rar the Cat bases it on an existing proposal Kx, where Kx < x. The heights of the wall in proposal x will be the same as proposal k, except for one contigous segment of the wall which Rar the Cat will change the height of.

For each proposal x (x < 0), Rar the Cat will provide Kx, Ax, Bx and Cx. This means that proposal x is based on proposal Kx and Rar the Cat will modify the height of the walls between Ax and Bx by Cx.

In summary, let Hx, i be the height of the ith unit of wall in the xth proposal and kx = Kx.

  • H0, i = 0, for all 0 ≤ i < L.
  • Hx, i = Hkx, i, for 0 ≤ i < Ax
  • Hx, i = Hkx, i + Cx, for AxiBx
  • Hx, i = Hkx, i, for Bx < i < L

Given these proposals, Rar the Cat wants you to answer Q queries online. Each query will ask for the maximum height of the wall between a given contigous range of the wall in a certain proposal.

Input

The first line of input will contain 3 integers, L, M and Q.

M lines follow with 4 integers each, the xth line will contain Kx, Ax, Bx and Cx.

Q lines of queries will follow. Each line of query will contain 3 integers, P, X and Y. This means Rar the Cat is asking for the maximum wall height between unit X and Y in proposal P.

Output

For each query, output the maximum height requested on a single line each.

Implementation

You are to code the following functions:

  • void init(int L, int M, int Q)
    • L: Length of the wall
    • M: Number of proposals in addition to proposal 0
    • Q: Number of queries Rar the Cat has
    • This function will be called once at the start of the program. You should place all initialization code here.
  • void proposal(int N, int K, int A, int B, int C)
    • N: Proposal number of this current proposal
    • K: The proposal that the current proposal is based on
    • A, B: Range of modification Rar the Cat is going to make
    • C: Constant that Rar the Cat would add to the heights between wall unit A and B in this proposal.
    • There will be M calls to this function in total.
    • It is guaranteed that they will be called in increasing N, from 1 to M.
  • long long max_height(int P, int X, int Y)
    • P: Proposal that this query is referring to
    • X, Y: Segment of the wall that this query is referring to
    • This function will be called Q times, once for each query.
    • You are to return the maximum height of the wall in proposal P between unit X and Y inclusive.

Limits

Subtask Score L M Q K A, B C P X, Y
1 8 1 ≤ L ≤ 105 M = L Q ≤ 105 K = N-1 0 ≤ A = B < L -109 ≤ C ≤ 109 P = M 0 ≤ X ≤ Y < L
2 13 1 ≤ L ≤ 105 M ≤ 105 Q ≤ 105 K = N-1 0 ≤ A ≤ B < L -109 ≤ C ≤ 109 P = M 0 ≤ X ≤ Y < L
3 15 1 ≤ L ≤ 109 M ≤ 105 Q ≤ 105 K = N-1 0 ≤ A ≤ B < L -109 ≤ C ≤ 109 P = M 0 ≤ X ≤ Y < L
4 14 1 ≤ L ≤ 109 M ≤ 105 Q ≤ 105 K < N 0 ≤ A = B < L C = 1 0 ≤ P ≤ M 0 ≤ X = Y < L
5 23 1 ≤ L ≤ 105 M ≤ 104 Q ≤ 104 K < N 0 ≤ A ≤ B < L -109 ≤ C ≤ 109 0 ≤ P ≤ M 0 ≤ X ≤ Y < L
6 27 1 ≤ L ≤ 109 M ≤ 105 Q ≤ 105 K < N 0 ≤ A ≤ B < L -109 ≤ C ≤ 109 0 ≤ P ≤ M 0 ≤ X ≤ Y < L

Sample Testcase 1

Input

5 5 5
0 0 4 5
1 1 1 4
0 2 2 9
2 1 3 6
4 0 2 4
2 1 3
2 0 3
2 1 3
2 2 4
0 1 4

Output

9
9
9
5
0

Sample Testcase 2

Input

20 10 10
0 13 18 3
1 0 7 5
2 12 17 3
2 4 8 2
4 16 17 6
2 4 12 5
3 1 19 9
0 7 13 8
6 0 18 8
3 3 8 1
3 7 8
3 10 17
4 4 17
6 0 10
6 14 18
3 16 17
6 1 19
2 4 19
0 6 12
2 16 18

Output

5
6
7
10
3
6
10
5
0
3

Sample Testcase 3

Input

100 15 15
0 2 68 9
1 10 97 7
2 0 52 6
0 50 53 10
1 23 30 7
0 10 25 2
0 70 77 9
4 41 99 5
1 47 99 9
3 21 70 5
2 38 40 2
1 33 85 1
12 7 54 7
3 0 76 9
5 14 91 9
1 4 84
5 65 67
0 4 61
5 59 68
5 12 64
2 34 43
3 2 55
0 33 92
1 30 98
1 22 35
2 40 85
1 8 68
3 26 90
1 17 85
2 44 56

Output

9
9
0
9
16
16
22
0
9
9
16
9
22
9
16

Submitting .cpp to 'rarwall'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2.5 Seconds
Memory Limit: 1024MB
No. of ACs: 9
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 8
2 13
3 15
4 14
5 23
6 27
7 0