题目描述

Freda 发明了传呼机之后，rainbow 进一步改进了传呼机发送信息所使用的信号。由于 现在是数字、信息时代，rainbow 发明的信号用 N 个自然数表示。为了避免两个人的对话被 大坏蛋 Var iantF 偷听 T_T，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 和的平均数。

A 部分对话占接收到的信息总量的 40%，因此如果你计算出密码 a，将获得该测试点 40% 的分数。

B 部分对话的密码是数列 P 的 and 和的期望，定义类似于 xor 和，占信息总量的 30%。

C 部分对话的密码是数列 P 的 or 和的期望，定义类似于 xor 和，占信息总量的 30%。

输入格式

第一行一个正整数 N。

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

输出格式

一行三个实数，分别表示 xor 和、and 和、or 和的期望，四舍五入保留 3 位小数，相邻 两个实数之间用不少于一个空格隔开。三个实数分别占该测试点 40%、30%、30%的分数， 如果你的输出少于三个实数，或者你的输出不合法，将被判 0 分。

样例输入 1

2
4 5

样例输出 1

2.750 4.250 4.750

样例输入 2

3
1 0 1

样例输出 2

0.667 0.222 0.889

样例解释

样例 1 共包含四种可能的 l、r：

以上每一对 l、r 出现的概率均相同，因此分别对 xor 和、and 和、or 和取平均数就是数 学期望值。

数据范围与约定

对于 20%的数据，1<=N<=100。

对于 40%的数据，1<=N<=1000。

对于另外 30%的数据，N 个数为 0 或 1。

对于 100%的数据，1<=N<=100000，N 个自然数均不超过 10^9。