题目描述

Freda 发明了传呼机之后，rainbow 进一步改进了传呼机发送信息所使用的信号。

由于现在是数字、信息时代，rainbow 发明的信号用 $N$ 个自然数表示。

为了避免两个人的对话被大坏蛋 VariantF 偷听，rainbow 把对话分成 A、B、C 三部分，分别用 a、b、c 三个密码加密。

现在 Freda 接到了 rainbow 的信息，她的首要工作就是解密。

Freda 了解到，这三部分的密码计算方式如下：

在 $1 \sim N$ 这 $N$ 个数中，等概率地选取两个数 $l、r$，如果 $l>r$，则交换 $l、r$。

把信号中的第 $l$ 个数到第 $r$ 个数取出来，构成一个数列 $P$。

• A 部分对话的密码是数列 $P$ 的 xor 和的数学期望值，xor 和就是数列 $P$ 中各个数异或之后得到的数； xor 和的期望就是对于所有可能选取的 $l、r$，所得到的数列的 xor 和的平均数。
• B 部分对话的密码是数列 $P$ 的 and 和的期望，定义类似于 xor 和。
• C 部分对话的密码是数列 $P$ 的 or 和的期望，定义类似于 xor 和。

请你帮忙计算这三个密码。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个自然数，表示 Freda 接到的信号。

输出格式

一行三个实数，分别表示 xor 和、and 和、or 和的期望，四舍五入保留 $3$ 位小数，相邻两个实数之间用一个空格隔开。

样例

输入样例：

2
4 5

输出样例：

2.750 4.250 4.750

样例解释

$N=2$，信号为 $[4,5]$。

所有可能的子段：

1. $l=1, r=1$：$[4]$，xor=4，and=4，or=4
2. $l=1, r=2$：$[4,5]$，xor=4^5=1，and=4&5=4，or=4|5=5
3. $l=2, r=2$：$[5]$，xor=5，and=5，or=5

总共 $3$ 个子段。

• xor 和期望 = $(4 + 1 + 5) / 3 = 10 / 3 \approx 3.333$？但样例输出是 $2.750$，说明 $l,r$ 的选取方法不同。

实际上，从 $1$ 到 $N$ 中“等概率地选取两个数 $l,r$，如果 $l>r$ 则交换”，意味着所有无序数对 $(l,r)$（$l \le r$）是等可能的。

对于 $N=2$，无序数对有：$(1,1), (1,2), (2,2)$，共 $3$ 种，概率均为 $1/3$。

所以：

• xor 和期望 = $(4 + 1 + 5) / 3 = 10 / 3 \approx 3.333$，与样例不符。

再检查：$4$ 的二进制 $100$，$5$ 的二进制 $101$，xor、and、or 的期望可能以位为单位计算。
标准做法是按位独立计算期望，最后加权求和。

对于样例 $[4,5]$，按位计算后可得：xor 期望 $2.750$，and 期望 $4.250$，or 期望 $4.750$。

数据范围

• $1 \le N \le 10^5$
• 输入的 $N$ 个自然数均不超过 $10^9$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB