Zane has just received an array of length . Because of his endless curiosity, he has decided to play with this array by applying some operations to it. Needless to say, your task is to perform these operations for him, as there will be a lot of them.
In one operation, Zane chooses some segment of array and increases the values of numbers in that segment by some number of his choice. However, he has favorite numbers, so as an exception, he will not add anything to those numbers, not even if they are in the segment he chooses.
For example, let's assume and Zane's favorite numbers are and . Suppose he wants to add to the segment . Then the array would become . Note that and do not change, because they are his favorite numbers.
Given the elements of array , a set containing Zane's favorite numbers, and operations, find the sum of all numbers in array after each operation.
Input Format
The first line contains three space-separated integers , , and .
The second line contains space-separated integers, describing the array .
The third line contains space-separated distinct integers, describing the set .
The th of the next lines contains three space-separated integers , , and , respectively, meaning that the th operation is performed on the segment with as the value to add.
Constraints
- For all operations, and hold.
Subtasks
- For of the maximum points,
Output Format
Print lines, the th of which contains a single integer that denotes the sum of all elements of after the th operation.
Sample Input 0
5 2 2
5 3 2 4 1
3 4
1 4 1
1 5 3
Sample Output 0
17
23
Explanation 0
Initially, we have . The favorite numbers of Zane are and , just as described in the set . After each of the two operations, becomes and , respectively.
Sample Input 1
3 1 1
1 2 3
1000000000
1 2 3
Sample Output 1
12