Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
The Highest Profits
Time Limit: 1000MSMemory Limit: 30000K
Total Submissions: 776Accepted: 334


This program will not be part of the KOKODáKH collection, but it may be more important than the games themselves. It will serve to the marketing staff to find suitable procedures for promoting and selling the collection. So try to do your best.

Extensive marketing case study tried to prove that the total income from selling a product is polynomial function of number of satisfied customers. Experiments showed that the real results are not exactly the same which you can obtain using the function. However, this method is widely used. The reason is probably nonexistence of better solution. Let's denote the number of satisfied customers y, than we can express profits (denoted x) as

x = P(y) =a0 +a1.y +a2.y2 + ... +am.ym
The number of satisfied customers depends on the price of a product. Again, there is hypothese that this dependence is polynomial. If we denote the price z, we can write

y = Q(x) =b0 +b1.z +b2.z2 + ... +bn.zn
Coeficients ai and bi strongly depend on the season of the year, the moon phase, the purchasing power of customers, inflation rate and hunderds of other parameters. Besides on the kind of product and its quality, of course. In the past there was lot of effort put into the reserarch of these parameters. For various combinations of input parameters, the coeficients are stated in Pyshwejc's marketing tables. It is not thus difficult to find out their values. But the degree of polynoms is usualy very high. It is very difficult to substitute one polynom into the other and to compute the dependency of the profit on the price. This dependency is usually crucial for us to set the right price.

Your goal is to write the program which can substitute the polynom Q into the polynom P and determine the restulting polynom R indicating dependency of the profit on the price:

x = R(z) =c0 +c1.z +c2.z2 + ... +cp.zp


The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Each assingement constist of three lines. On the first line there are two integers m and n (0 <= n,m <= 100) separated by space. These numbers give the degree of polynoms Q and P. On the second line there are m+1 integers a0 ... am. These numbers are coeficients of polynom P. On the third line there are n+1 integers b0 ... bn. Always am <> 0 and bn <> 0. Coeficients ai and bi are separated by space and they are chosen in order to each resulting coeficient could fit into the standard type integer.


The program prints exactly one line for each assignement. On this line, there will be p+1 numbers. These numbers are coeficients c0 ... cp of resulting polynom. The coeficients are separated by space and the line does not consist any redundant spaces. The coeficient in the highest degree should not be zero.

Sample Input

0 0
1 1
6 6
9 -6
3 3
-3 6 -5 1
0 3 -3 1

Sample Output

60 -36
-3 18 -63 123 -156 138 -86 36 -9 1


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator