小机器人
题号：NC308084
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小灰灰有 n 个数字，第 i 个数字记为 a_i。
\hspace{15pt}小蓝有一个笨笨的机器人，接下来她将使用这个机器人对小灰灰的 n 个数字进行 m 轮操作，第 i 轮操作使用三个参数 l_i,r_i,k_i 描述：
\hspace{23pt}\bullet\,机器人会根据参数执行 k_i 次重复操作，每次操作会找到第 l_i 到第 r_i 个数字中最小的数（如果有多个数字同样小，那么机器人会选择更靠前的数字），并将这个最小数的数值 +1。

\hspace{15pt}小灰灰知道小蓝是胡乱指挥的机器人，但他还是对这 n 个数字的最终状态感兴趣，所以你需要输出进行 m 轮操作之后的每个数字的数值为多少。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(1\le n \le 8000\right)，表示数字的数量。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots a_n \left(1\le a_i \le 10^9\right)，表示每个数字的初始数值。
\hspace{15pt}第三行输入一个整数 m \left(1\le m \le 5000\right)，表示操作的数量。
\hspace{15pt}此后 m 行，第 i 行输入三个整数 l_i, r_i, k_i \left(1\le l_i \le r_i \le n;\,1\le k_i \le 10^9\right)，表示第 i 轮操作的参数。

输出描述:

\hspace{15pt}在一行上输出 n 个整数，表示进行 m 轮操作之后的每个数字的数值。
示例1

输入

复制 
6
4 2 7 2 5 1
3
1 6 3
4 6 10
2 4 10

输出

复制 
4 9 9 9 7 6

说明

\hspace{15pt}在这个样例中，操作如下：\begin{array}{c}<br />\{4, 2, 7, 2, 5, 1\} \\<br />\ce{v 1,6,3} \\<br />\{4, 3, 7, 3, 5, 2\} \\<br />\ce{v 4,6,10} \\<br />\{4,3,7,7,7,6\} \\<br />\ce{v 2,4,10} \\<br />\{4,9,9,9,7,6\} \\<br />\end{array}。