#P4194. Mat

Mat

Mat

题目描述

小 C 有一个 NN 行 MM 列的整数矩阵 AA,行和列均从 11 开始编号。输入给出第一列的所有元素。对于每一列 jj(2≤j≤M2\le j\le M),输入给出一对整数 kj,bjk_j,b_j,满足

Ai,j=Ai,j−1+kji+bj(1≤i≤N).A_{i,j}=A_{i,j-1}+k_j i+b_j\qquad(1\le i\le N).

求每一行的最小值。

输入格式

第一行两个整数 N,MN,M(1≤N,M≤2×1051\le N,M\le2\times10^5)。

第二行 NN 个整数,第 ii 个为 Ai,1A_{i,1}。接下来 M−1M-1 行,依次给出第 22 列到第 MM 列的 kj,bjk_j,b_j。

保证 ∣Ai,1∣≤2×1012\lvert A_{i,1}\rvert\le2\times10^{12},∣kj∣≤100\lvert k_j\rvert\le100,∣bj∣≤107\lvert b_j\rvert\le10^7。

输出格式

输出 NN 行,第 ii 行一个整数,为第 ii 行的最小值。

样例 #1

样例输入 #1

2 3
1 2
-1 1
-2 1

样例输出 #1

0
-2