There are now peaks with a valley between every two adjacent peaks.

The th mountain has a weight , and the th valley has a weight .

You now want to divide these peaks into several camps, and all the peaks of the same camp must be a continuous interval, and the dividing line between two adjacent camps must be a valley.

Now for all the peaks of each camp, you need to choose exactly one ``General Peak`` among them.

The weight of a certain distribution scheme is defined as: the weight sum of all general peaks plus the weight sum of all dividing valleys.

But your aesthetics are special, and now there are additional bonus points:

The th condition is given by three numbers , indicating that if there are at least two dividing lines in the th to th valleys, the weight of this allocation scheme will be additionally increased by .And these intervals do not intersect with each other.

Your aesthetic will also change, and each change will change a value in .

Please find the maximum value of the distribution scheme weight after each aesthetic change.

In the first line, there are three integers  separated by spaces, which represent the number of peaks, the number of additional bonus conditions and the number of aesthetic changes.

The second line has  integers separated by spaces, and the  th integer is , which represents the weight of the  th peak.

The third line has  integers separated by spaces, and the  th integer is , which represents the weight of the  th valley.

Then there are three integers  in each of the following  lines, separated by spaces, indicating a bonus condition.And there must be .

Then there are three integers  in the next  lines, separated by spaces, indicating a change in aesthetics.

When  , it means changing  to , when , it means changing  to , and when , it means changing  to .

Output has  lines in total, and the  th line represents the maximum value of the distribution scheme weight after the  th aesthetic change.

2 0 1
7 -4
5
1 2 3

15

5 2 2
1 2 3 4 5
1 2 3 4
1 3 2
4 4 5
1 3 -10
2 2 -100

22
22