Anish's parents have given him a complicated job. n containers have been kept in a row. Anish has to fill the containers with water in short bursts. At a time he has to fill all the containers in the range [a, b] with c cm of water each. He does this a total of m times. Find the max level of water in any container.
0 < n < 10^5 1 < a <= b <= n 1 < m <= 10^5 0 <= c <= 10^5
First line contains number of test cases T
First line of each test case contains n;
Next n line contain initial level of water in containers, 1 in each line.
Next line contains m
Next m lines contain 3 numbers each, separated by spaces, a b c
For each case print 1 line giving the max level of water.