Computation of Salary

Time Limit : 2 sec, Memory Limit : 65536 KB

親方の給料計算

ワシはパイプつなぎ組合の親方じゃ。職人を工事現場に派遣し、現場でパイプをつながせておる。去年は工事が増えて大儲けするかと思ったのじゃが、ちょっと給料の出し方がまずくてのぅ。ウチとしては大赤字になってしまったのじゃよ…。そこで、今年は職人たちへの給料の出し方を工夫したいのじゃ。

職人たちの給料は、工事の種類とこなした回数で決めておる。つまり、
職人の給料 = 種類 1 の単価 × 種類 1 をこなした回数
                    + 種類 2 の単価 × 種類 2 をこなした回数
                      ....
                       + 種類 M の単価 × 種類 M をこなした回数

となるのじゃ。これを計算するために、ウチでは、どの職人がどの種類の工事を何回こなしたかを次のような表に記録しておる。


例えば、上の表では、職人1が工事2を2回、工事4を1回こなしたことを示しておる。

職人たちがこなした仕事の回数はもう変えられんが、やつらは工事の単価を知らんので、単価をいろいろと変えながら皆の不満が出ぬよう給料を調整しようと思うておる。じゃが、ワシがこしらえたプログラムが今もって動かなくてのぅ。ちょっとみてくれんかね。

//省略
int i, j;
for ( i = 0; i < N; i++ ){
    c[i] = 0;
    for ( j = 0; j < M; j++ ){
        c[i] = c[i] + a[i][j]*b[j];
    }
}
//省略

N は職人の数で M は工事の種類の数じゃ。変数 a[i][j] に職人iが工事 j をこなした回数を、b[j] に工事 j の単価をいれて、c[i] に職人 i の給料を格納しておる。合っているはずなのに、うんともすんとも言わん!そろそろ今年の給料を職人たちに払わないとまずいのじゃが・・・・・なんとかならんかのぅ。

それでは、職人のこなした仕事の回数と各工事の単価の情報が与えられたとき、各職人の給料を計算するプログラムを作成してください。

入力

入力は1つのデータセットからなる。入力データは以下の形式で与えられる。

N M
s1 t1 e1
s2 t2 e2
:
0 0 0
L
b11 b12 ... b1M
b21 b22 ... b2M
:
bL1 bL2 ... bLM
  • 1行目は職人の数 N(1 ≤ N ≤ 10000)と工事の種類の数 M(1 ≤ M ≤ 10000)。
  • 続いて、工事の記録として、職人の番号 si (1 ≤ siN) と工事の種類の番号 ti(1 ≤ tiM)、および職人 si が工事 ti をこなした回数 ei (1 ≤ ei ≤ 50000) からなる行が1行以上与えられる。工事の記録はゼロ3つの行で終わる。ただし、ei の合計は 1 以上 50000 以下である。また、工事の記録には、どの職人と工事の種類の組も2度以上現れない。工事をこなした回数が 0 である職人と工事の種類の組は与えられない。
  • 続く 1 行は給料の算出を行う回数 L (1 ≤ L ≤ 100) 。
  • 続く L 行は、i 回目の給料の算出に必要な、工事 j の単価 bij (0 ≤ bij ≤ 10000) の並び。

出力

以下の形式で、i 回目の給料の算出によって得られた職人 j の給料 cij を順番に出力する。各給料の間は空白1つで区切る。

c11 c12 ... c1N
c21 c22 ... c2N
:
cL1 cL2 ... cLN

入出力例


入力例

4 6
1 2 1
2 3 2
2 4 3
3 1 5
4 2 4
4 3 2
4 6 10
0 0 0
3
1 3 2 4 0 10
6 5 4 3 2 1
5 1 1 5 5 1

出力例

3 16 5 116
5 17 30 38
1 17 25 16

Source: PC Koshien 2013 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2013-11-9
http://web-ext.u-aizu.ac.jp/pc-concours/