A meteor shower passed through the kingdom of Woll, which led the people to speculate that it was a punishment from the gods. Many gathered at the door of the mage Hongly and prayed to him to protect them with his spells. The enthusiastic Hongly quickly granted them their blessing.
Hongly's spell requires the use of n magic towers lined up in a straight line, numbered as 1,2,3,...,n. Each tower requires some magic value to cast this spell. And each tower has an initial magic value of 00 . Hongly needs to add some magic ingredients to the magic tower in order to increase its magic values. When 11 unit of magic ingredients is added to a tower, it will increase the magic value of all nearby magic towers by 1 within a radius of k, in which k is called effective radius. For example, assuming the i-th magic tower is added with 1 unit of magic ingredients, when k=1, only magic tower ii will add its magic value by 1, when k=2, magic tower i-1, i, i+1 will increase their magic values by 1, and so on. The effective radius for all towers is the same. For this spell to protect the people, the i-th magic tower needs at least p_{i}pi points of magic value.
However, magic is not free to be used at will, and when there are too many magic ingredients in a range, it can lead to a big explosion. So there are q restrictions among Hongly's magic towers. The ii-th restriction contains three integers Li,Ri,Bi, which means that the sum of the magic ingredients in the magic towers [Li,Ri] cannot be greater than Bi.
Hongly is glad to help the villagers but is worried about the explosion. Now he wants to know if there is a way to place the ingredients that will meet the magic value requirements of all magic towers for using the spell while avoiding an explosion. If so, he would also like to know the minimum value of magic ingredients that need to be used.
Each test contains multiple test cases. The first line contains the number of test cases T(1≤T≤15). Desc
The input data of each test case has q+3 lines.
The first line contains two integers: n(1≤n≤10000),k(1≤k≤⌈2n⌉), representing the number of magic towers and their effective radius.
The second line contains n integers:p1,p2,p3,...pn(1≤pi≤1000) , where p_{i}pi represents the magic value required for the i-th tower.
The third line contains an integer q(0≤q≤100), representing the number of restrictions.
Next q lines, each line contains 3 integers:Li,Ri,Bi(1≤Li≤Ri≤n,0≤Bi≤10000), have the same meaning as described above.
3
5 2
2 2 0 10 3
1
1 5 11
5 2
2 2 0 10 3
1
2 3 0
3 2
3 0 6
2
1 1 0
3 3 0-1
12
6