#P2821. TN's Kingdom III - Assassination

    ID: 1831 远端评测题 10000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>POJ Monthly--2006.04.28, frkstyc@PKU_RPWT

TN's Kingdom III - Assassination

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;

<li>Choose another real sequence β of the same length;</li>

<li>Calculate a real sequence γ as the result of encryption according to the steps below:</li>

  1. Let γ be an empty sequence;

<li>Write β in reversed order;</li>

<li>Rotate β to the right by one place;</li>

<li>Append the sum of element-wise products of α and β to the end of γ;</li>

<li>Repeat the steps iii. and iv. until γ has length n.</li>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.

4
1
2
3
4
26
28
26
20
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