← 返回题目列表

Codeforces · 662/A

A. 赌博尼姆

中文机器翻译题面 查看原题

如您所知,“Nim”游戏是用 n 堆石子进行的,其中第 i 堆最初包含 ai 石子。两名玩家轮流轮流。在一个回合中,玩家拾取任何非空堆并从中移除任意正数的石子。无法采取行动的人就输掉了比赛。

Petya 和 Vasya 厌倦了玩 Nim,因此他们发明了自己的游戏版本,并将其命名为“Gambling Nim”。他们有n张双面卡片,第i张卡片的一面写着数字ai,而另一面写着数字bi。游戏开始时,玩家将所有牌放在桌上,每张牌只有一面朝上,并且这一面是独立且统一选择的。因此,他们获得了序列 c1, c2, ..., cn,其中 ci 等于 ai 或 bi。然后他们拿 n 堆棋子,其中第 i 堆恰好包含 ci 棋子,然后玩 Nim。佩蒂亚(Petya)先行。

鉴于两名玩家都发挥最佳,求 Petya 获胜的概率。将答案输出为不可约分数。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 500 000) — 这副牌中的牌数。

以下n行每行包含一张卡的描述,由两个整数ai和bi组成(0≤ai,bi≤1018)。

输出

将答案输出为不可约分数 p / q。如果 Petya 获胜的概率为 0,则打印 0/1。

示例

输入 #1

2
1 1
1 1

输出 #1

0/1

输入 #2

2
1 2
1 2

输出 #2

1/2

输入 #3

3
0 4
1 5
2 3

输出 #3

1/1