Farmer John tem $N$ pilhas de fardos de feno ($1 \leq N \leq 5 \cdot 10^5$), das quais a $i$-ésima contém $a_i$ fardos ($1 \leq a_i \leq 10^9$). Quer remover todos estes fardos e tem $M$ ($1 \leq M \leq 2500$) vacas disponíveis para ajudar. Se for contratada, a $i$-ésima vaca repetirá a seguinte operação $s_i$ vezes ($1 \leq s_i \leq 100$), por um custo de $c_i$ ($1 \leq c_i \leq 10^9$):

• Se a pilha contiver pelo menos $p_i$ fardos ($1 \leq p_i \leq 10^9$), a vaca removerá um fardo.
• Se a pilha contiver menos de $p_i$ fardos, a vaca não fará nada.

Para cada pilha, FJ quer remover todos os fardos que contém. Contratará vacas sucessivamente (possivelmente a mesma vaca mais de uma vez) até a pilha ficar vazia. Ajude FJ a determinar o custo mínimo para esvaziar cada pilha.

Entrada

A entrada é recebida do terminal / stdin.

A primeira linha contém $T$ ($1\le T\le 100$), o número de testes independentes. Cada teste tem o seguinte formato:

A primeira linha contém um inteiro $N$. A segunda contém $N$ inteiros, $a_1, a_2, \dots, a_N$.

A terceira linha contém um inteiro $M$. As $M$ linhas seguintes contêm $p_i, s_i, c_i$.

É garantido que as vacas poderão remover todos os fardos de cada pilha. Além disso, a soma de $N$ em todos os testes não excede $5\cdot 10^5$ e a soma de $M$ não excede $2500$.

Saída

Imprima a saída no terminal / stdout.

Para cada teste, imprima $N$ inteiros separados por espaços. O $i$-ésimo inteiro é o custo de remover todos os fardos da $i$-ésima pilha.

Exemplos

Entrada 1

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

Saída 1

29 155 21
73 328 50

Explicação

Primeiro teste: Para a última pilha, inicialmente de tamanho $10$, podemos contratar a vaca $3$ uma vez, por $5$, removendo dois fardos (não três, porque ficam $8$ fardos depois de remover o segundo). Depois podemos contratar a vaca $2$ duas vezes, removendo os $8$ fardos, sem deixar nenhum. O custo total é $ 5+8+8=21$.

Segundo teste: Satisfaz $\max(s)=1$.

Pontuação

• Entradas 2-3: $a_i \le 100$
• Entradas 4-5: $\max(s)=1$
• Entradas 6-9: $\max(s)\le 4$
• Entradas 10-15: $\max(s)\le 20$
• Entradas 16-21: Sem restrições adicionais.

Autor do problema: Sujay Konda