The Rebel fleet is on the run. It consists of m ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, and the Rebels will need to escape into hyperspace. In order to spread the fleet, the captain of each ship has independently come up with the coordinate to which that ship will jump. In the obsolete navigation system used by the Rebels, this coordinate is given as the value of an arithmetic expression of the form $\frac{a + b}{c}$.

To plan the future of the resistance movement, Princess Heidi needs to know, for each ship, how many ships are going to end up at the same coordinate after the jump. You are her only hope!


-----Input-----

The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) – the number of ships. The next m lines describe one jump coordinate each, given as an arithmetic expression. An expression has the form (a+b)/c. Namely, it consists of: an opening parenthesis (, a positive integer a of up to two decimal digits, a plus sign +, a positive integer b of up to two decimal digits, a closing parenthesis ), a slash /, and a positive integer c of up to two decimal digits.


-----Output-----

Print a single line consisting of m space-separated integers. The i-th integer should be equal to the number of ships whose coordinate is equal to that of the i-th ship (including the i-th ship itself).


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

Output
1 2 2 1 


-----Note-----

In the sample testcase, the second and the third ship will both end up at the coordinate 3.

Note that this problem has only two versions – easy and hard.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
dict1={}
dict2={}
for i in range(n):
    s=input()
    s=s.split('/')
    c=int(s[1])
    s=s[0].strip('(').strip(')').split('+')
    a=int(s[0])
    b=int(s[1])
    ans=(a+b)/c
    try:
        dict2[ans] += 1
    except:
        dict2[ans] = 1
    dict1[i] = ans
for i in range(n):
    print(dict2[dict1[i]],end=' ')


while True:
    try:
        mp=dict()
        a=list()
        n=int(input())
        for i in range(n):
            s=input()
            num=eval(s)
            a.append(num)
            if num in mp:
                mp[num]=mp[num]+1
            else:
                mp[num]=1
        for i in a:
            print(mp[i],end=' ')
        print()
    except EOFError:
        break

from collections import Counter

def getList(l, m):
  r = []
  cnt = Counter(l)
  for i in l:
    r.extend([cnt[i]])
  return r
    

m = int(input())
res = []
for i in range(m):
  a, b = [i for i in input().split("/")]
  a = a.split("+")
  aux1 = a[0].replace("(", "")
  aux2 = a[len(a) - 1].replace(")", "")
  a = [aux1, aux2]
  a = list(map(lambda x: int(x), a))
  b = float(b)
  res.extend([sum(a)/b])
  
output = getList(res, m)
for i in range(len(output)):
  if i == len(output) - 1: print(output[i])
  else: print(str(output[i]) + " ", end = "")

x = int(input())
a = []
b = dict()
for i in range(x):
	s = input()
	a.append(eval(s))
	if(a[i] not in b):
		b[a[i]] = 1
	else:
		b[a[i]] += 1

for i in range(x):
	print("%d "%b[a[i]], end = '')
print()

n = int(input())

ccnt = {}
sn = {}

for i in range(1, n+1):
	s = input()
	res = eval(s)
	res = str(format(res, '.6f'))
	if (res in ccnt):
		ccnt[res] += 1
	else:
		ccnt[res] = 1
	sn[i] = res

for i in range(1, n+1):
	print(str(ccnt[sn[i]]) + " ", end='')

print()

table = {}
cur = 1


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a%b)


def read():
	nonlocal cur
	nonlocal table
	s = input().split('/')
	nom = eval(s[0])
	den = int(s[1])
	g = gcd(nom, den)
	nom //= g
	den //= g
	h_code = nom * 1000 + den
	if h_code in table:
		table[h_code].append(cur)
	else:
		table[h_code] = [cur]
	cur += 1


m = int(input())
for i in range(m):
	read()
ans = [0] * 213456

for key, val in table.items():
	for idx in val:
		ans[idx] = len(val)

for i in range(1, m+1):
	print(ans[i], end = " ")

import re
from collections import defaultdict

P = re.compile(r'\((\d+)\+(\d+)\)/(\d+)')

m = int(input())
s = defaultdict(int)
xs = []

for _ in range(m):
    a, b, c = list(map(int, P.match(input()).groups()))
    x = (a + b) / c
    s[x] += 1
    xs.append(x)

print(' '.join(str(s[x]) for x in xs))


n = int(input())
lst = []
d = dict()
for temp in range(n):
  input_str, z = input().split('/')
  x, y = input_str.split('+')
  x = x [1:]
  y = y [:len(y)-1]
  x = int(x)
  y = int(y)
  z = int(z)
  ans = (x+y)/z
  if(ans in d.keys()) : d[ans]+=1
  else : d[ans]=1
  lst.append(ans)
for i in lst:
  print(d[i], end=" ")

from fractions import gcd

ans = []
dic = {}

n = int(input())
for i in range(n):
  word = input()
  word = word.replace('(',',')
  word = word.replace('+',',')
  word = word.replace(')/',',')
  w = word.split(',')
  a = int(w[1])
  b = int(w[2])
  numerator = a + b
  denumerator = int(w[3])
  x = numerator // gcd(numerator, denumerator)
  y = denumerator // gcd(numerator, denumerator)
  ans.append((x, y))
  if (x, y) in dic:
    dic[(x, y)] += 1
  else:
    dic[(x, y)] = 1
for i in range(n):
  if i > 0:
    print(' ', end='')
  print(dic[ans[i]], end='')
print("\n", end='')

n=int(input())
ct = {}
ctx = []
for ni in range(0, n):
	st = input().strip()[1:]
	p1 = st.index('+')
	a = int(st[:p1])
	st = st[p1+1:]
	p2 = st.index(')')
	b = int(st[:p2])
	c = int(st[p2+2:])
	v = ((a+b)/c)
	if v in ct: ct[v]+=1
	else: ct[v]=1
	ctx.append(v)
st = []
for cti in ctx: st.append(str(ct[cti]))
print(" ".join(st))




n=int(input())
dicti={}
L=[]
for i in range(n):
  s=input()
  a=''
  b=''
  c=''
  i=1
  while s[i]!='+':
    a+=s[i]
    i=i+1 
  i=i+1 
  while s[i]!=')':
    b+=s[i]
    i=i+1
  c=s[i+2:]
  
  a,b,c=int(a),int(b),int(c)
  res=(a+b)/c 
  if res in dicti:
    dicti[res]+=1
  else:
    dicti[res]=1
  L.append(res)
  
for i in range(len(L)):
  print(dicti[L[i]],end=' ')
  
  
  

_ = int(input())
x = []
for __ in range(_) :
    s = input()
    a = s.split('/')
    c = int(a[1])
    a = a[0]
    a = a.split(')')
    a = a[0]
    a = a.split('+')
    b = int(a[1])
    a = a[0]
    a = a.split('(')
    a = int(a[1])
    x.append((a+b)/c)
d = {}
for i in x:
    d[i] = 0
for i in x :
    d[i]+=1
for i in x :
    print(d[i],end=" ")

n=int(input())
d={}
for i in range(n):
    s=input()
    s=s.replace('(','')
    s=s.replace(')','')
    s=s.split('/')
    c=float(s[-1])
    s=s[0]
    s=s.split('+')
    a=float(s[0])
    b=float(s[1])
    ans=(a+b)/c
    if ans in d:
        d[ans].append(i)
    else:
        d[ans]=[i]
l=[0]*n
for k in list(d.keys()):
    for i in d[k]:
        l[i]=str(len(d[k]))
print(' '.join(l))


import re

math = re.compile('\((\d+)\+(\d+)\)\/(\d+)')
d1 = dict()
d2 = dict()

def main():
	n = int(input())

	for i in range(n):
		string = input()
		match = math.match(string)
		a = int(match.group(1))
		b = int(match.group(2))
		c = int(match.group(3))
		d2[i+1]=((a+b)/c)
		try :
			d1[((a+b)/c)]+=1
		except:
			d1[((a+b)/c)]=1

	lis = []

	for i in range(n):
		lis.append(str(d1[d2[i+1]]))

	print(' '.join(lis))


def __starting_point():
	main()

__starting_point()

from fractions import Fraction
n = int(input())
arr = []
cc = {}
for i in range(n):
	line = input()
	ab, c = line.split('/')
	ab = ab[1:-1]
	a, b = ab.split('+')
	a, b, c = [int(x) for x in (a, b, c)]
	p = (a + b) / c
	arr.append(p)
	if p not in cc:
		cc[p] = 1
	else:
		cc[p] += 1
for i in range(n):
	if i > 0:
		print(' ', end="")
	print(cc[arr[i]], end="")


n = int (input ())
l=[]
d={}
for i in range (n) :
    ch = input()
    c= eval(ch)
    l.append(c)
    if (c in d ) :
        d[c]+=1
    else :
        d[c]=1
for i in range ( n) :
    print (d[l[i]] ,end=" ")


import re

m=int(input())
lis=list()

for i in range(m):
    s=input()
    lis+=[re.split('\W+', s)]

d=dict()

for i in range(m):
    ans=int(lis[i][1])+int(lis[i][2])
    ans=ans/int(lis[i][3])
    lis[i][0]=ans
    if ans in d:
        d[ans]+=1
    else: d[ans]=1

for i in range(m):
    print(d[lis[i][0]],end=' ')


n=int(input())
d={}
aaa=[]
for ii in range(n):
    s=input().strip()
    arr=list(s)
    for i in range(len(arr)):
        if arr[i] is "(" or arr[i] is "+" or arr[i] is ")" or arr[i] is "/":
            if arr[i] is "/":
                arr[i]=""
            else:
                arr[i]=" "
    a,b,c=map(int,("".join(arr)).split())
    ans=(a+b)/c 
    if ans in d.keys():
        d[ans][0]+=1
        d[ans][1].append(ii)
    else:
        d[ans]=[1,[ii]]
    aaa.append(ans)
arr1={}
for i in d.keys():
    for j in d[i][1]:
        arr1[j]=d[i][0]
for i in range(n):
    print(arr1[i],end=" ")
print("")
        
    

#codeforces.com/contest/958/problem/D1

m=int(input())
positions=[]
poscount={}
for i in range(m):
    crew=list(input())
    n=len(crew)
    i=1
    a=''
    while crew[i]!='+':
        a+=crew[i]
        i+=1
    b=''
    i+=1
    while crew[i]!=')':
        b+=crew[i]
        i+=1
    c=''
    i+=2
    while i<n:
        c+=crew[i]
        i+=1
    a=int(a)
    b=int(b)
    c=int(c)
    res=(a+b)/c
    positions.append(res)
    if res in poscount:
        poscount[res]+=1
    else:
        poscount[res]=1

ans=[]
for i in range(m):
    ans.append(poscount[positions[i]])
print(*ans,sep=' ')

from collections import defaultdict

m = int(input())
value = {}
count = defaultdict(int)

for i in range(m):
    s = input()
    ans = 0
    z = ""
    n = len(s)
    for j in range(1,n):
        if s[j]=='+':
            ans = int(z)
            z = ""
            continue
        elif s[j]==')':
            ans +=int(z)
            z = ""
            j+=2
            while j<n:
                z+=s[j]
                j+=1
            ans = ans/int(z)
            count[ans]+=1
            value[i] = ans
        else:
            z = z+s[j]

for i in range(m):
    print(count[value[i]],end=" ")
print()