【题目描述】

给定序列 $\{a_n\}$ 和 $d$，接下来 $q$ 次形如 l x 的操作：

• $\forall i\in[l,n]$，$a_i\gets\max \{a_i,x+(i-l)\times d\}$。

你需要输出 $q$ 次操作后的序列。

【输入格式】

第一行 $3$ 个整数 $n,d,q$。

第二行 $n$ 个整数表示初始的 $a$ 序列。

接下来 $q$ 行每行两个整数 $l,x$ 表示一次操作。

【输出格式】

输出一行 $n$ 个整数表示操作后的序列。

【样例输入】

4 1 2
0 0 0 25
2 1
3 3

【样例输出】

0 1 3 25

【数据范围与提示】

对于 $20\%$ 的数据，$n,q\le1000$。

对于 $40\%$ 的数据，$n,q\le10^5$。

对于 $100\%$ 的数据，$n,q\leq 4\times 10^6$，$|x|,|d|,|a_i|\le10^9$。