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 H_{0}. Units of the walls are labeled from 0 to L1.
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 H_{i} = 0 for proposal 0.
For each subsequent proposal x, Rar the Cat bases it on an existing proposal K_{x}, where K_{x} < 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 K_{x}, A_{x}, B_{x} and C_{x}. This means that proposal x is based on proposal K_{x} and Rar the Cat
will modify the height of the walls between A_{x} and B_{x} by C_{x}.
In summary, let H_{x, i} be the height of the i^{th} unit of wall in the x^{th} proposal and kx = K_{x}.
 H_{0, i} = 0, for all 0 ≤ i < L.
 H_{x, i} = H_{kx, i}, for 0 ≤ i < A_{x}

H_{x, i} = H_{kx, i} + C_{x}, for A_{x} ≤ i ≤ B_{x}

H_{x, i} = H_{kx, i}, for B_{x} < 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 x^{th} line will contain K_{x}, A_{x}, B_{x} and C_{x}.
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 ≤ 10^{5} 
M = L 
Q ≤ 10^{5} 
K = N1 
0 ≤ A = B < L 
10^{9} ≤ C ≤ 10^{9} 
P = M 
0 ≤ X ≤ Y < L 
2 
13 
1 ≤ L ≤ 10^{5} 
M ≤ 10^{5} 
Q ≤ 10^{5} 
K = N1 
0 ≤ A ≤ B < L 
10^{9} ≤ C ≤ 10^{9} 
P = M 
0 ≤ X ≤ Y < L 
3 
15 
1 ≤ L ≤ 10^{9} 
M ≤ 10^{5} 
Q ≤ 10^{5} 
K = N1 
0 ≤ A ≤ B < L 
10^{9} ≤ C ≤ 10^{9} 
P = M 
0 ≤ X ≤ Y < L 
4 
14 
1 ≤ L ≤ 10^{9} 
M ≤ 10^{5} 
Q ≤ 10^{5} 
K < N 
0 ≤ A = B < L 
C = 1 
0 ≤ P ≤ M 
0 ≤ X = Y < L 
5 
23 
1 ≤ L ≤ 10^{5} 
M ≤ 10^{4} 
Q ≤ 10^{4} 
K < N 
0 ≤ A ≤ B < L 
10^{9} ≤ C ≤ 10^{9} 
0 ≤ P ≤ M 
0 ≤ X ≤ Y < L 
6 
27 
1 ≤ L ≤ 10^{9}
 M ≤ 10^{5} 
Q ≤ 10^{5} 
K < N 
0 ≤ A ≤ B < L 
10^{9} ≤ C ≤ 10^{9} 
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