You are given two arrays $a$ and $b$, each contains $n$ integers.

You want to create a new array $c$ as follows: choose some real (i.e. not necessarily integer) number $d$, and then for every $i \in [1, n]$ let $c_i := d \cdot a_i + b_i$.

Your goal is to maximize the number of zeroes in array $c$. What is the largest possible answer, if you choose $d$ optimally?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in both arrays.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($-10^9 \le a_i \le 10^9$).

The third line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($-10^9 \le b_i \le 10^9$).


-----Output-----

Print one integer — the maximum number of zeroes in array $c$, if you choose $d$ optimally.


-----Examples-----
Input
5
1 2 3 4 5
2 4 7 11 3

Output
2

Input
3
13 37 39
1 2 3

Output
2

Input
4
0 0 0 0
1 2 3 4

Output
0

Input
3
1 2 -1
-6 -12 6

Output
3



-----Note-----

In the first example, we may choose $d = -2$.

In the second example, we may choose $d = -\frac{1}{13}$.

In the third example, we cannot obtain any zero in array $c$, no matter which $d$ we choose.

In the fourth example, we may choose $d = 6$.

Difficulty: introductory

Starter code:

Solutions:
import collections
import math
input()
a = list(map(int, input().split()))
b = list(map(int, input().split()))
counts = collections.defaultdict(int)
arbitrary = 0
for ai, bi in zip(a, b):
    if ai == 0:
        if bi == 0:
            arbitrary += 1
    else:
        if bi == 0:
            counts[(0, 0)] += 1
        else:
            if (ai < 0 and bi < 0) or (ai >= 0 and bi < 0):
                ai = -ai
                bi = -bi

            g = math.gcd(-bi, ai)
            counts[(-bi // g, ai // g)] += 1

if counts:
    print(max(counts.values()) + arbitrary)
else:
    print(arbitrary)


import collections
import math

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

arb = 0

counts = collections.defaultdict(int)

for x, y in zip(a, b):
    if x==0:
        if y==0:
            arb+=1
    else:
        if y==0:
            counts[(0, 0)] += 1
        else:
            if x<0 and y<0:
                x=-x
                y=-y
            elif x<0 and y>=0:
                x=-x
                y=-y
            g = math.gcd(x, -y)
            counts[(-y//g, x//g)] += 1

if counts:
    print(max(counts.values()) + arb)
else:
    print(arb)

#!/usr/bin/pypy
# -*- coding: utf-8 -*-

from collections import defaultdict


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


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    e = defaultdict(int)
    cnt = 0

    for i in range(n):
        if a[i] == 0:
            if b[i] == 0:
                cnt += 1
            continue
        if b[i] == 0:
            e[(0, 0)] += 1
            continue
        w = gcd(a[i], b[i])
        wa = a[i] / w
        wb = b[i] / w
        e[(wa, wb)] += 1

    ans = 0
    for i in list(e.values()):
        ans = max(ans, i)

    print(cnt + ans)


def __starting_point():
    main()

__starting_point()

from math import gcd


n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

d = {}
w = 0
for i in range(n):
	if a[i] != 0:
		c = gcd(abs(a[i]), abs(b[i]))
		z = 1
		if a[i] * b[i] < 0:
			z = -1
		d[(abs(b[i]) // c, abs(a[i]) // c, z)] = d.get((abs(b[i]) // c, abs(a[i]) // c, z), 0) + 1
	else:
		if b[i] == 0:
			w += 1
mx = 0
#print(d)
for c in d:
	x = d[c]
	
	if x > mx:
		mx = x
print(int(mx) + w)


n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

D=[]
ANS=0
for i in range(n):
    if A[i]==0 and B[i]==0:
        ANS+=1
    elif A[i]==0 and B[i]!=0:
        continue
    elif A[i]!=0 and B[i]==0:
        D.append(0)
    else:
        D.append((A[i]//gcd(A[i],B[i]),B[i]//gcd(A[i],B[i])))

from collections import Counter
C=Counter(D)

if len(C)==0:
    print(ANS)
else:
    print(ANS+max(C.values()))
    


from decimal import Decimal as mag, getcontext

getcontext().prec = 100

def main():
    n = int(input())
    arr = list(map(mag, input().split()))
    brr = list(map(mag, input().split()))
    mp = dict()
    mp[0] = 0
    pl = 0
    for i in range(n):
        if (arr[i] == 0 and brr[i] == 0):
            pl += 1
        if arr[i] == 0:
            continue
        k = - brr[i] / arr[i]
        mp[k] = mp.get(k, 0) + 1
    print(pl + max(mp.values()))


main()


import math

n = int(input())

A = [int(x) for x in input().split()]

B = [int(x) for x in input().split()]

D = {0:0}
free = 0

for i in range(n):
    if A[i] == 0:
        if B[i] == 0:
            free += 1
    elif B[i] == 0:
        D[0] += 1
    else:
        t = math.gcd(A[i],B[i])
        a = A[i]//t
        b = B[i]//t
        if a < 0 and b < 0: 
            if (-a,-b) in D:
                D[(-a,-b)] += 1
            else:
                D[(-a,-b)] = 1
        elif a > 0 and b <0:
            if (a,b) in D:
                D[(a,b)] += 1
            else:
                D[(a,b)] = 1
        elif a < 0 and b > 0:
            if (-a,-b) in D:
                D[(-a,-b)] += 1
            else:
                D[(-a,-b)] = 1
        else:
            if (a,b) in D:
                D[(a,b)] += 1
            else:
                D[(a,b)] = 1
            
            
print(max(D.values())+free)


import math

n=int(input())
x=[*map(int,input().split())]
y=[*map(int,input().split())]
cnt=dict()
fixcnt=0
zeroToCnt=0

for i in range(n):
    if x[i]==0:
        if y[i]==0: fixcnt+=1
        continue
    if y[i]==0:
        zeroToCnt+=1
        continue
    gc=math.gcd(x[i],y[i])
    tx,ty=x[i]//gc,y[i]//gc
    if tx*ty>=0: si=True
    else: si=False
    cnt[(abs(tx),abs(ty),si)]=cnt.get((abs(tx),abs(ty),si),0)+1

cntRes=max(zeroToCnt,max(cnt.values() if cnt else [0]))
print(cntRes+fixcnt)

import math

def reduce_fraction(n,m):
    k = math.gcd(n,m)
    if (n > 0 and m < 0) or (n < 0 and m < 0):
        n = -n
        m = -m

    if n == 0 and m < 0:
        m *= -1
        
    return (n//k, m//k)

n = int(input())

a = list(map(int,input().split()))
b = list(map(int,input().split()))

d = {}

s = 0

for i in range(n):
    if a[i] != 0:
        x = reduce_fraction(b[i],a[i])

        if x in d:
            d[x] += 1
        else:
            d[x] = 1
            
    else:
        if b[i] == 0:
            s += 1
            
maxs = 0

for i in d:
    maxs = max(maxs,d[i])

print(maxs + s)


n=int(input().strip())
from fractions import gcd
a=list(map(int,input().strip().split(" ")))
b=list(map(int,input().strip().split(" ")))
d={}
t=0
for i in range(0,len(a)):
    if( b[i]==0 and a[i]!=0):
        if("x" not in d.keys()):
            d["x"]=1
        else:
            d["x"]+=1
    elif (a[i] == 0  and b[i]==0 ):
        d["m"]=0
        t+=1
    elif(a[i]==0 and b[i]!=0):
        d["y"]=0
    else:
        p=gcd(a[i],b[i])
        x=a[i]//p
        y=b[i]//p
        if(y<0):
            y=-y
            x=-x
        if ((x,y) not in d.keys()):
            d[(x,y)] = 1
        else:
            d[(x,y)] += 1
print(max(d.values())+t)

from collections import defaultdict
from math import gcd
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
l=defaultdict(int)
an=0
for i in range(n):
    if a[i]==0 and b[i]==0:an+=1
    elif a[i]!=0:
        x,y=(-b[i]//gcd(-b[i],a[i]),a[i]//gcd(-b[i],a[i]))
        if x<0:
            x*=-1;y*=-1
        if x==0:
            y=0

        l[(x,y)]+=1
#print(l)
print((sorted(l.values())[-1] if len(l)>0 else 0)+an)


import math
import collections

n= int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
z = list(zip(a,b))
zz = []
doublezeros = 0
for idx, t in enumerate(z):
    if t[0] == 0 and t[1] != 0:
        continue
    if t[0] == 0 and t[1] == 0:
        doublezeros += 1
        continue
    if t[0] != 0 and t[1] == 0:
        zz.append((1,0))
        continue
    gcd = math.gcd(t[0], t[1])
    f = 1 if t[0] > 0 else -1
    zz.append((t[0] // gcd * f,    t[1] // gcd*f))
d = collections.defaultdict(int)
for t in zz:
    d[t] += 1
r = max(d.values()) if len(d) > 0 else 0
print(r+doublezeros)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cands = {}
aux = 0
zero = 0

def gcd(x, y):
    if x % y == 0:
        return y
    return gcd(y, x % y)

for i in range(n):
    if b[i] == 0 and a[i] == 0:
        aux += 1
    elif a[i] != 0:

        if a[i] < 0:
            a_semn = -1
            a[i] = -a[i]
        else:
            a_semn = +1

        if b[i] < 0:
            b_semn = -1
            b[i] = -b[i]
        else:
            b_semn = +1

        if b[i] != 0:
            cmmdc = gcd(a[i], b[i])
            a_redus = a[i] // cmmdc
            b_redus = b[i] // cmmdc
        else:
            a_redus = a[i]
            b_redus = b[i]
            zero += 1

        c_semn = a_semn * b_semn

        cands[(a_redus, b_redus, c_semn)] = cands.get((a_redus, b_redus, c_semn), 0) + 1

cmax = 0
for i in cands:
    if cands[i] > cmax:
        cmax = cands[i]

print(aux + max(cmax, zero))


# -*- coding: utf-8 -*-
# @Time    : 2019/3/7 23:32
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : D. Zero Quantity Maximization.py

import math
from collections import Counter


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    counter = Counter()
    zero = 0
    for i in range(n):
        if a[i] == 0 and b[i] == 0:
                zero += 1
        elif a[i] != 0 and b[i] == 0:
            counter[0] += 1
        elif a[i] != 0 and b[i] != 0:
            g = math.gcd(a[i], b[i])
            x, y = a[i] // g, b[i] // g,
            mask = (x * y) > 0
            counter[(mask, abs(x), abs(y))] += 1

    ret = 0
    for k, v in list(counter.items()):
        ret = max(ret, v)
    print(ret + zero)


def __starting_point():
    main()


__starting_point()

'''input
3
1 2 -1
-6 -12 6
'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())


n=ri(1)
a=ri()
b=ri()

k=dd(int)

from math import gcd

# for i in range(n):
# 	if a[i]!=0:
# 		temp=(b[i]*pow(a[i],mod-2,mod))%mod
# 		k[temp]+=1
# 	if a[i]==0 and b[i]==0:
# 		k[0]+=1


k[0,0,0]=0
for i in range(n):
	ok=gcd(a[i],b[i])
	f=0
	if a[i]!=0 and b[i]!=0:
		one=a[i]//ok
		two=b[i]//ok
		f=f^(one<0)
		f=f^(two<0)
		one=abs(one)
		two=abs(two)
		if one!=0:
			k[one,two,f]+=1
	if a[i]!=0 and b[i]==0:
		pass
	if a[i]==0 and b[i]==0:
		k[0,0,0]+=1

ans=b.count(0)


for i in k:
	if i==(0,0,0):
		ans=max(ans,k[i])
	else:
		ans=max(ans,k[0,0,0]+k[i])
print(ans)

from collections import defaultdict


def gcd(a, b):
  while b:
    a, b = b, a % b
  return a


n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
x = defaultdict(int)
p = 0
for i in range(n):
    if a[i] == 0 and b[i] == 0:
        p += 1
    elif a[i] != 0:
        if a[i] * b[i] < 0:
            z = 0
        else:
            z = 1
        v = gcd(abs(a[i]), abs(b[i]))
        x[(z, abs(a[i]) // v, abs(b[i]) // v)] += 1
if len(x) > 0:
    print(max(x.values()) + p)
else:
    print(p)


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]

pre = 0
for ai, bi in zip(a, b):
    if (ai, bi) == (0, 0):
        pre += 1

fracs = [(-bi // gcd(ai, bi), ai // gcd(ai, bi)) if ai
         != 0 else float('inf') for ai, bi in zip(a, b)]

cnt = {item: 0 for item in fracs}

for x in fracs:
    if x != float('inf'):
        cnt[x] += 1

print(max(cnt.values()) + pre)


from fractions import Fraction

n = int(input())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))

extra_count = 0
counts_map = dict()
# counts_map_2 = dict()
for ai, bi in zip(a, b):
    # print(ai, bi)
    if ai != 0:
        fi = Fraction(-1 * bi, ai)
        # print(fi)

        num_i = fi.numerator
        den_i = fi.denominator

        # print(num_i, den_i)

        curr_str = str(num_i) + '#' + str(den_i)

        if curr_str in counts_map:
            counts_map[curr_str] += 1
        else:
            counts_map[curr_str] = 1

        # print('\n')
    else:
        if bi == 0:
            extra_count += 1
        else:
            pass


# print(counts_map)

max = 0
for key in counts_map:
    curr_count = counts_map[key]

    if curr_count > max:
        max = curr_count

print(max + extra_count)

from decimal import *
getcontext().prec = 50
n = int(input())
inputs= list(map(int,input().split()))
inputs1= list(map(int,input().split()))
dic={
}
temp=0
for i in range(len(inputs)):
    if inputs[i]==0 and inputs1[i]!=0:
        continue
    elif inputs[i]==0 and inputs1[i]==0:
        temp+=1
        continue

    c=-Decimal(inputs1[i])/Decimal(inputs[i])
    if c in list(dic.keys()):
        dic[c]+=1
    else:
        dic[c]=1
if len(dic)>0:
    print(max(dic.values())+temp)
else:
    print(0+temp)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = []
def gsd(p, q):
    if q == 0:
        return p
    return gsd(q, p % q)
ans0 = 0
for i in range(n):
    if a[i] == 0:
        if b[i] == 0:
            ans0 += 1
        n -= 1
        i -= 1
        continue
    g = gsd(abs(a[i]), abs(b[i]))
    if a[i] * b[i] < 0:
        h = 1
    else:
        h = 0
    d.append([abs(b[i]) // g, abs(a[i]) // g, h])
d.sort()
bk = 0; k = 1
for i in range(1, n):
    if d[i] == d[i - 1]:
        k += 1
    else:
        bk = max(k, bk)
        k = 1
if n != 0:
    bk = max(bk, k)
print(bk + ans0)
#print(d)


from fractions import Fraction
import collections
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
abzero = 0
bzero = 0
for i in range(n):
    if a[i] == 0:
        if b[i] == 0:
            abzero += 1
    elif b[i] == 0:
        bzero += 1
    else:
        c.append(Fraction(a[i], b[i]).limit_denominator(1000000000))
c = collections.Counter(c)
try:
    ma = c.most_common()[0][1]
except IndexError:
    ma = 0
print(max(ma+abzero, abzero+bzero))

from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
c={}
q=0
for i in range(N):
	if A[i]!=0:
		if B[i]!=0:
			g=gcd(B[i],A[i])
			k=(B[i]//g,A[i]//g)
		else:k=(0,0)
		if k in c:c[k]+=1
		else:c[k]=1
	else:
		if B[i]==0:q+=1
if c:print(max(c.values())+q)
else:print(q)

from collections import Counter
from fractions import Fraction

n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

c = Counter()

r = 0
for i in range(n):
    if a[i] == 0 == b[i]:
        r+=1
        continue

    if a[i]==0:
        continue

    c[Fraction(b[i], a[i])] += 1

#print(c)

r += c.most_common(1)[0][1] if len(c) > 0 else 0

print(r)