Problem Description

After Freda invented the pager, Rainbow further improved the signal used by the pager to send messages.

Since we are now in the digital information age, the signal invented by Rainbow is represented by $N$ natural numbers.

To prevent the big bad guy VariantF from eavesdropping on the conversation between two people, Rainbow split the conversation into three parts: $A$, $B$, and $C$, and encrypted them with three passwords $a$, $b$, and $c$ respectively.

Now Freda has received Rainbow's message, and her first task is to decrypt it.

Freda learned that the passwords for these three parts are computed as follows:

Among the $N$ numbers from $1 \sim N$, two numbers $l, r$ are chosen uniformly at random. If $l > r$, swap $l, r$.

Take out the numbers from the $l$-th to the $r$-th in the signal to form a sequence $P$.

The password for part $A$ is the mathematical expectation of the $\operatorname{xor}$ sum of sequence $P$. The $\operatorname{xor}$ sum is the value obtained by applying XOR to all numbers in $P$. The expectation of the $\operatorname{xor}$ sum is the average of the $\operatorname{xor}$ sums over all possible choices of $l, r$.

The password for part $B$ is the expected value of the $\operatorname{and}$ sum of sequence $P$, defined similarly to the $\operatorname{xor}$ sum.

The password for part $C$ is the expected value of the $\operatorname{or}$ sum of sequence $P$, defined similarly to the $\operatorname{xor}$ sum.

Please help compute these three passwords.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ natural numbers, representing the signal received by Freda.

Output Format

Output one line with three real numbers, representing the expected values of the $\operatorname{xor}$ sum, the $\operatorname{and}$ sum, and the $\operatorname{or}$ sum, respectively. Round to $3$ decimal places. Separate adjacent numbers with one space.

2
4 5

2.750 4.250 4.750

Hint

Sample Explanation

Sample 1 contains four possible choices of $l, r$ in total:

Each pair $l, r$ has the same probability of occurring, so taking the average of the $\operatorname{xor}$ sum, the $\operatorname{and}$ sum, and the $\operatorname{or}$ sum gives their mathematical expectation.

Constraints

For $20\%$ of the testdata, $1 \le N \le 100$ .
For $40\%$ of the testdata, $1 \le N \le 1000$ .
For another $30\%$ of the testdata, the $N$ numbers are $0$ or $1$ .
For $100\%$ of the testdata, $1 \le N \le 100000$, and each of the $N$ natural numbers is at most $10^9$ .

Translated by ChatGPT 5