Compute the sum of an array and classify it by the parity of that sum.

Input

The first line contains \(n\). The second line contains \(n\) integers.

The input satisfies:

• \(0 <= n <= 1000\)

Output

Print the sum. On the next line print good array if the sum is even, otherwise bad array.

Example

Input

5
6 8 1 5 3

Output

23
bad array