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 H₀. 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 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

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