义军舰队正在逃亡。它由目前聚集在一个行星周围的 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。
请注意,这个问题只有两个版本——简单和困难。