← 返回题目列表

Codeforces · 958/D1

D1. 超空间跳跃(简单)

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

义军舰队正在逃亡。它由目前聚集在一个行星周围的 m 艘飞船组成。就在几秒钟前,更强大的帝国舰队出现在同一个太阳系中,义军需要逃入超空间。为了分散舰队,每艘船的船长都独立地提出了该船将跳跃到的坐标。在叛军使用的过时导航系统中,该坐标以 $${ \frac { a + b } { c } }$$ 形式的算术表达式的值给出。

为了规划抵抗运动的未来,海蒂公主需要知道,对于每艘船,有多少艘船在跳跃后最终会到达同一坐标。你是她唯一的希望!

输入

输入的第一行包含一个整数 m (1 ≤ m ≤ 200 000) – 船只数量。接下来的 m 行每行描述一个跳跃坐标,以算术表达式给出。表达式的形式为 (a+b)/c。即由:左括号(、最多两位小数的正整数a、加号+、最多两位小数的正整数b、右括号 )、斜杠/、最多两位小数的正整数c组成。

输出

打印由 m 个空格分隔的整数组成的单行。第 i 个整数应该等于坐标与第 i 艘船坐标相同的船舶数量(包括第 i 艘船本身)。

示例

输入 #1

4
(99+98)/97
(26+4)/10
(12+33)/15
(5+1)/7

输出 #1

1 2 2 1

注意

在示例测试用例中,第二艘和第三艘船都将到达坐标 3。

请注意,这个问题只有两个版本——简单和困难。