Count and sum the even and odd elements of an array separately.

Input

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

The input satisfies:

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

Output

Print, on four lines: the even count, odd count, even sum, and odd sum.

Example

Input

5
5 4 1 3 2

Output

2
3
6
9