У Farmer John есть $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$ тюков сена, корова ничего не делает.

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

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

Входные данные поступают из терминала / stdin.

Первая строка содержит $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$.

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

Выводите результат в терминал / stdout.

Для каждого теста выведите $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: без дополнительных ограничений.

Автор задачи: Sujay Konda