Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
TN's Kingdom III - Assassination
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 345Accepted: 56
Case Time Limit: 6000MSSpecial Judge

Description

TN had never given up the thought that rebellion was always a possibility since that was how he came to de throne. He was worried about that Dzx might someday pay him back in his own coin. Therefore he elaborated a plot of sending killers to assassinate Dzx. In order to keep everything secret and guard against his enemies' spying, TN used a special scheme to encrypt the order of assassination before having it sent to the killers. The encryption scheme was as follows:
  1. Encode the plot as a real sequence α of length n where n perfectly factors over the first eight prime numbers;
  2. Choose another real sequence β of the same length;
  3. Calculate a real sequence γ as the result of encryption according to the steps below:
    1. Let γ be an empty sequence;
    2. Write β in reversed order;
    3. Rotate β to the right by one place;
    4. Append the sum of element-wise products of α and β to the end of γ;
    5. Repeat the steps iii. and iv. until γ has length n.
Though his most intimate advisor had warned that this scheme was unsafe and might cause the plot to be leaked, but TN obstinately stuck to it.

However, in the killers' eyes, the scheme was simply too safe rather than unsafe that they failed to decrypt the plot. They looked for help with little care about secrecy. Dzx was just lucky to come across them. He got and decrypted the plot and eventually survived the assassination. Nevertheless, the result was satisfactory to TN for Dzx had never been heard of since then.

From some rare records found in written history only the fact that what Dzx got was the sequences β and γ along with the encryption scheme was known. The sequences and the scheme were once lost. But through archaeologists' great effort they are rediscovered. From them the sequence α can be calculated, which will enable the historians to know more about TN.

Input

The input consists of a single test case. On the first line of input there is a positive integer n not greater than 217 that perfectly factors over the first eight prime numbers. It is the length of the sequences. Then follow 2n lines each containing a real number. The first n lines give the sequence β and the next n lines the sequence γ.

Output

Your solution should output n lines. These n lines should give the sequence α in the same format as sequences β and γ are given. All real numbers should be rounded to four decimal places.

Sample Input

4
1
2
3
4
26
28
26
20

Sample Output

1.0000
2.0000
3.0000
4.0000

Hint

It is recommended that your solution uses standard C I/O interface to achieve better efficiency and avoid unpredictable behaviours.
That an integer n perfectly factors over the first eight prime numbers means that n = 2a * 3b * 5c * 7d * 11e * 13f * 17g * 19h where a, b, c, d, e, f, g and h are all non-negative integers.

Source

POJ Monthly--2006.04.28, frkstyc@PKU_RPWT

[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