Decrypting Rainbow’s Signal

Freda has received a signal from Rainbow, who has improved upon the pager invented by Freda. In this digital era, Rainbow’s signal is represented by a sequence of (N) natural numbers. To avoid eavesdropping by the villain VariantF, Rainbow divided the conversation into three parts (A, B, and C), encrypting each part with a different cipher based on the contiguous subarray taken from the signal.

For a given signal of length (N), two indices (l) and (r) are chosen uniformly at random (if (l > r), they are swapped), and the contiguous subarray (P = [p_l, p_{l+1}, \dots, p_r]) is formed.

The ciphers are defined as follows:

1. Part A: The password is the expected value of the bitwise XOR of the numbers in (P). That is, if (xor(P) = p_l \oplus p_{l+1} \oplus \cdots \oplus p_r), then the answer for part A is the average of (xor(P)) over all contiguous subarrays.

2. Part B: The password is the expected value of the bitwise AND of the numbers in (P). Here, (and(P) = p_l & p_{l+1} & \cdots & p_r).

3. Part C: The password is the expected value of the bitwise OR of the numbers in (P). Here, (or(P) = p_l | p_{l+1} | \cdots | p_r).

Mathematically, if the total number of contiguous subarrays is (T = \frac{N(N+1)}{2}), then the expected value for an operation (\circ) (where (\circ) can be XOR, AND, or OR) is given by: [ E[\circ] = \frac{1}{T} \sum_{1 \le l \le r \le N} (p_l \circ p_{l+1} \circ \cdots \circ p_r). ]

Your task is to compute and print the three expected values corresponding to the XOR, AND, and OR operations respectively.

Note: All formulas must be rendered in (\LaTeX) format.

inputFormat

The first line contains a single integer (N) indicating the number of natural numbers in the signal. The second line contains (N) space-separated natural numbers representing the signal.

outputFormat

Output three floating point numbers: the expected XOR, expected AND, and expected OR values respectively. Print each value with at least 12 decimal places of precision.

sample

3
1 2 3

1.666666666667 1.333333333333 2.500000000000