It's time to have a break and implement something.
You are given an matrix . All the elements are zero initially.
First, you need to perform range addition operations. For each operations, you are given .You need to add w to all the elements where and .
Then you need to perform range maximum queries. For each operations, you are given . You need to answer the maximum element among the elements that satisify and .

The first line contains three integers

Each of the following  lines contains five integers
.Each of the following  lines contains four integers
.

Output  lines, each of which contains one integer.

5 5 5
1 1 4 5 4
4 1 4 1 10
1 3 3 3 3
1 1 5 5 8
2 4 4 5 8
2 1 2 1
4 1 5 4
1 2 3 5
2 1 5 3
1 3 5 5

12
22
20
22
20