Parity Check

Problem Description

Data may be corrupted during transmission, so the receiver usually verifies whether the received data is correct. Parity checking is one of the classic verification methods.

You are given $n$ non-negative integers $c_1, c_2, \ldots, c_n$ representing the transmitted data. Their check code depends on the parity of the total number of $1$-bits (in binary) among these integers: if the integers have an odd total number of $1$-bits, the check code is $1$; otherwise it is $0$. Can you compute the check code of these integers?

Input Format

The first line contains a positive integer $n$, the amount of transmitted data.

The second line contains $n$ non-negative integers $c_1, c_2, \ldots, c_n$, the transmitted data.

Output Format

Output one line containing two integers separated by a single space:

• the first integer is the total number of $1$-bits (in binary) among $c_1, c_2, \ldots, c_n$;
• the second integer is the check code ($0$ or $1$).

Sample Input 1

4
71 69 83 80

Sample Input 2

6
1 2 4 8 16 32

Sample Output 1

13 1

Sample Output 2

6 0

Sample Explanation

For the first sample, the input consists of $4$ integers: $71, 69, 83, 80$. Count the $1$-bits of each in binary:

• $71 = 64 + 4 + 2 + 1 = (1000111)_2$, which contains $4$ ones.
• $69 = 64 + 4 + 1 = (1000101)_2$, which contains $3$ ones.
• $83 = 64 + 16 + 2 + 1 = (1010011)_2$, which contains $4$ ones.
• $80 = 64 + 16 = (1010000)_2$, which contains $2$ ones.

The total number of $1$-bits is $4 + 3 + 4 + 2 = 13$, which is odd. Therefore the check code is $1$, and the final output is 13 1.

Constraints

For all test cases, $1 \leq n \leq 100$, $0 \leq c_i \leq 255$.