Фермер Джон имеет $N$ стогов сена ($1 \leq N \leq 5 \cdot 10^5$), где в $i$-м стоге содержится $a_i$ тюков сена ($1 \leq a_i \leq 10^9$). Он хочет убрать все эти тюки и имеет $M$ ($1 \leq M \leq 2500$) коров, готовых помочь ему. Если нанять $i$-ю корову, она повторит следующие действия $s_i$ раз ($1 \leq s_i \leq 100$) за стоимость $c_i$ ($1 \leq c_i \leq 10^9$):

• Если в стоге содержится не менее $p_i$ тюков сена ($1 \leq p_i \leq 10^9$), корова убирает один тюк.
• Если в стоге содержится меньше $p_i$ тюков сена, корова ничего не делает.

Для каждого стога ФД хочет убрать все тюки. Он будет делать это, нанимая коров последовательно (возможно, одну и ту же корову несколько раз), пока стог не станет пустым. Помогите ФД определить для каждого стога минимальную стоимость его опустошения.

Входные данные

Первая строка содержит $T$ ($1 \le T \le 100$), количество независимых тестов. Каждый тест отформатирован следующим образом:

Первая строка содержит целое число $N$. Вторая строка содержит $N$ целых чисел $a_1, a_2, \dots, a_N$.

Третья строка содержит целое число $M$. Затем следующие $M$ строк содержат $p_i, s_i, c_i$.

Гарантируется, что коровы смогут убрать все тюки сена в каждом стоге. Кроме того, гарантируется, что сумма $N$ по всем тестам не превышает $5\cdot 10^5$, а сумма $M$ по всем тестам не превышает $2500$.

Выходные данные

Для каждого теста выведите $N$ целых чисел, разделенных пробелами, где $i$-е число — это стоимость удаления всех тюков сена из $i$-го стога.

Примеры

Входные данные 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

Выходные данные 1

29 155 21
73 328 50

Примечание

В первом тесте: для последнего стога начального размера $10$ мы можем нанять корову $3$ один раз, что стоит $5$ и уберет тюки дважды (не трижды, так как количество тюков становится равным $8$ после того, как второй тюк убран). Затем мы можем нанять корову $2$ дважды, убрав оставшиеся $8$ тюков, в результате чего стог станет пустым. Общая стоимость составляет $5+8+8=21$.

Во втором тесте выполняется условие $\max(s)=1$.

Подзадачи

• Тесты 2-3: $a_i \le 100$
• Тесты 4-5: $\max(s)=1$
• Тесты 6-9: $\max(s)\le 4$
• Тесты 10-15: $\max(s)\le 20$
• Тесты 16-21: Без дополнительных ограничений.