Need More T-shirts!

Time limit1sMemory limit512 MB

Summary

Given a list where each entry is either a T-shirt count or a percentage, find every possible total number of T-shirts consistent with the list.

Level: Hard8 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Statement

The Innopolis Open 2020 is coming. That means it is time to order T-shirts for the participants of the Olympiad.

The organizers decided it would be good to buy T-shirts in different colors so that anyone can easily tell who is an organizer, who is on the jury, and who is a participant.

Two people were assigned to this task, and they decided how many T-shirts of each color to order. However, they did not agree with each other: one of them wrote down the number of T-shirts of a certain color to order, and the other wrote down the percentage of T-shirts of a certain color. The result is a list of length $n$ , where each element $a_i$ is either the number of T-shirts of color $i$ or the percentage of T-shirts of color $i$ out of the total number of T-shirts. It is also known that at least one element $a_i$ in the list is the number of T-shirts of color $i$ .

Now the organizers need to figure out the total number of T-shirts they need to buy for the Olympiad. Help them find all possible values of the total number of T-shirts for which such a list could be obtained.

Input

The first line contains a single integer $n$ , the number of different colors ( $1 \le n \le 10^5$ ).

The second line contains $n$ integers $a_i$ , each being either the number of T-shirts or the percentage of T-shirts of color $i$ ( $1 \le a_i \le 10^9$ ).

Output

In the first line print the number of possible values of the total number of T-shirts for which such a list could be obtained.

In the second line print all possible values of the total number of T-shirts in sorted order.

Notes

Explanation of the first example:

If the total number of T-shirts is $2$ : one of color $1$ and one of color $2$ . We obtain the given list if the first element ( $1$ ) is the number of T-shirts of color $1$ and the second element ( $50$ ) is the percentage of T-shirts of color $2$ . $2 = 1 + 2 \cdot \frac{50}{100}$ .

If the total number of T-shirts is $51$ : one of color $1$ and $50$ of color $2$ . We obtain the given list if both elements are the numbers of T-shirts of colors $1$ and $2$ . $51 = 1 + 50$ .

Explanation of the second example:

$120 = 20 + 30 + 70$
$125 = 125 \cdot \frac{20}{100} + 30 + 70$
$140 = 140 \cdot \frac{20}{100} + 140 \cdot \frac{30}{100} + 70$
$300 = 300 \cdot \frac{20}{100} + 30 + 300 \cdot \frac{70}{100}$

Examples4

Example 1
Input
```
2
1 50
```
Expected output
```
2
2 51
```
Example 2
Input
```
3
20 30 70
```
Expected output
```
4
120 125 140 300
```
Example 3
Input
```
4
2 40 90 5
```
Expected output
```
3
137 470 840
```
Example 4
Input
```
7
10 20 5 15 30 17 3
```
Expected output
```
1
100
```