Processing math: 100%

Problem J. Jewel trade

Author:A. Zhuplev, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Recently, explorers have discovered a new species of giant sentient squids living at the bottom of a deep lake.

Squids are generally uninterested in dealing with humans. However, they showed appreciation for various jewels, especially diamonds, which are hard to find under water. In exchange, squids offered a wide selection of high-quality pearls.

So the trade was established. Each day, N different kinds of jewels were traded, some from the surface into the water, and some out of the water to the surface.

The Squid State Trading Commission established following rules:

  1. Each jewel mush be enclosed in a separate container.
  2. Jewels of the same kind must have identical containers.
  3. The trade must not alter the water level of the lake, so the total volume of all containers moved into the lake must be equal to the total volume of all containers moved to the surface.

You program must find the volume of the container for each kind of jewel, so as to satisfy commission's requirements.

Input file format

Input file contains an integer N followed by N integers ai, where ai>0 means that ai jewels of i-th kind are moved from the surface to the lake, and ai<0 means that |ai| jewels of i-th kind are moved from the lake to the surface.

Output file format

Output file must contain N integers bi (1bi1012), indicating the volume of containers for each kind of jewel. If there are several acceptable solutions, output any of them.

Constraints

2N105

1|ai|105

2×min(pos,neg)max(pos,neg), where pos is the number of positive values among ai and neg is the number of negative values.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
1 2 -3
1 1 1
2
5
20 -27 48 -17 6
5 13 8 11 9

0.057s 0.009s 13