TopCoder

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

92.3% (12/13)

Tags

Description

小明最近在學習數學,今天,他正在學有關於「多項式」的章節。

小明學到,一類單純的多項式是由若干個單項式通過加法或減法組合而成的表達式。每個單項式是 x 的非負整數次幂。例如,x5 是一個單項式,但 1/x 不是。因此,x3+x2+x2x0x0 是一個多項式,但 x5+1/x 不是。然而,當我們多次相加(或相減)同一個單項式時,為了方便,我們通常將結果表示為該單項式與一個係數相乘,這稱為一個。例如,x2+x2+x2x2+x2 可以表示為項 3x2,其係數為 3。多項式的次數是所有係數不為零的項中單項式的最高次幂。

為了方便後續的學習,小明發現他可以把任意的多項式都寫成一個長度為 k 的序列 a0,a1,,ak1ak10,其對應的多項式是
i=0k1aixi=a0x0+a1x1+ak1xk1
其中 k 就是這個多項式的次數加 1

例如前面提到的 x3+4x2+5,就可以被表示成 5,0,4,1

而有了方便的標示方法後,小明便決定直接來挑戰學習多項式的運算。雖然加法和減法對小明來說相當容易,但乘法就複雜多了!

小明知道,兩個多項式 fg 若表示成兩個序列 a0,a1,,ak11b0,b1,,bk21 的話,則他們的乘積 fg 將可以被表示成一個長度為 k1+k21 的序列 c,滿足
ci=p+q=i,0p<k1,0q<k2apbq, 0i<k1+k21

例如兩個多項式 x2+x+1x3+1 可以被表示成 1,1,11,0,0,1,他們相乘後便能得到 1,1,1,1,1,1,也就是 x5+x4+x3+x2+x+1

因為涉及到太多計算,導致小明常常算錯,所以他請你幫他寫一個程式可以事先輸出解答來幫他驗算。請你撰寫一支程式,在讀入多個多項式後,輸出這些多項式的乘積。

Input Format

輸入首行有一個 N,代表多項式的個數。

接下來 N 行,第 i 行首先會是一個數字 ki,代表第 i 個多項式的長度。接下來 ki 個數字,代表使用序列表示出來的多項式 ai,0,ai,1,,ai,ki1

  • 2N10
  • 1ki100
  • 1ai,j1
  • 對於第 i 個多項式,ai,ki10

Output Format

輸出一行 (i=1Nki)N+1 個數字,代表相乘後的結果以序列表示出來的樣子。

Sample Input 1

2
3 1 1 1
4 1 0 0 1

Sample Output 1

1 1 1 1 1 1

Sample Input 2

3
3 1 -1 1
4 0 0 0 -1
5 1 -1 1 -1 1

Sample Output 2

0 0 0 -1 2 -3 3 -3 2 -1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~9 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2