题目描述

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

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

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

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

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

在 1∼$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

数据范围

$1≤N≤10^5,N$ 个自然数均不超过 $10^9$。

来源

• 算法竞赛进阶指南