Palo Alto is an unusual city because it is an endless coordinate line. It is also known for the office of Lyft Level 5.

Lyft has become so popular so that it is now used by all $m$ taxi drivers in the city, who every day transport the rest of the city residents — $n$ riders.

Each resident (including taxi drivers) of Palo-Alto lives in its unique location (there is no such pair of residents that their coordinates are the same).

The Lyft system is very clever: when a rider calls a taxi, his call does not go to all taxi drivers, but only to the one that is the closest to that person. If there are multiple ones with the same distance, then to taxi driver with a smaller coordinate is selected.

But one morning the taxi drivers wondered: how many riders are there that would call the given taxi driver if they were the first to order a taxi on that day? In other words, you need to find for each taxi driver $i$ the number $a_{i}$ — the number of riders that would call the $i$-th taxi driver when all drivers and riders are at their home?

The taxi driver can neither transport himself nor other taxi drivers.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n,m \le 10^5$) — number of riders and taxi drivers.

The second line contains $n + m$ integers $x_1, x_2, \ldots, x_{n+m}$ ($1 \le x_1 < x_2 < \ldots < x_{n+m} \le 10^9$), where $x_i$ is the coordinate where the $i$-th resident lives. 

The third line contains $n + m$ integers $t_1, t_2, \ldots, t_{n+m}$ ($0 \le t_i \le 1$). If $t_i = 1$, then the $i$-th resident is a taxi driver, otherwise $t_i = 0$.

It is guaranteed that the number of $i$ such that $t_i = 1$ is equal to $m$.


-----Output-----

Print $m$ integers $a_1, a_2, \ldots, a_{m}$, where $a_i$ is the answer for the $i$-th taxi driver. The taxi driver has the number $i$ if among all the taxi drivers he lives in the $i$-th smallest coordinate (see examples for better understanding).


-----Examples-----
Input
3 1
1 2 3 10
0 0 1 0

Output
3 
Input
3 2
2 3 4 5 6
1 0 0 0 1

Output
2 1 
Input
1 4
2 4 6 10 15
1 1 1 1 0

Output
0 0 0 1 


-----Note-----

In the first example, we have only one taxi driver, which means an order from any of $n$ riders will go to him.

In the second example, the first taxi driver lives at the point with the coordinate $2$, and the second one lives at the point with the coordinate $6$. Obviously, the nearest taxi driver to the rider who lives on the $3$ coordinate is the first one, and to the rider who lives on the coordinate $5$ is the second one. The rider who lives on the $4$ coordinate has the same distance to the first and the second taxi drivers, but since the first taxi driver has a smaller coordinate, the call from this rider will go to the first taxi driver.

In the third example, we have one rider and the taxi driver nearest to him is the fourth one.

Difficulty: interview

Starter code:

Solutions:
import sys
import string
from math import gcd
import getpass
import math
from decimal import Decimal
import pprint


def ria():
    return [int(i) for i in input().split()]


if getpass.getuser() != 'frohenk':
    filename = 'half'
    # sys.stdin = open('input.txt')
    # sys.stdout = open('output.txt', 'w')
else:
    sys.stdin = open('input.txt')
    # sys.stdin.close()
# sys.stdout = open('output.txt', 'w')


n, m = ria()
ar = ria()
arc = []
art = []
res = []
for n, i in enumerate(ria()):
    if i == 1:
        art.append(ar[n])
        res.append(0)
    else:
        arc.append(ar[n])
nt = 0
for i in arc:
    while nt != len(art) - 1 and abs(art[nt] - i) > abs(art[nt + 1] - i):
        nt += 1
    res[nt] += 1

for i in res:
    print(i,end= ' ')

n, m = list(map(int, input().split()))
xs = list(map(int, input().split()))
ts = list(map(int, input().split()))

ps = [x for x, t in zip(xs, ts) if t == 0]
ds = [x for x, t in zip(xs, ts) if t == 1]
ans = [0] * m

di = 0
for pi, p in enumerate(ps):
    while di < m - 1 and abs(ds[di] - p) > abs(ds[di + 1] - p):
        di += 1

    if di >= m:
        ans[m - 1] += n - pi
        break

    ans[di] += 1


print(' '.join(map(str, ans)))


n, m = list(map(int, input().split()))
xs = [int(k) for k in input().split()]
ts = [int(k) for k in input().split()]
pos = [-1 for i in range(n + m)]
if ts[0]:
    pos[0] = 0
for i in range(1, n + m):
    pos[i] = pos[i - 1]
    if ts[i]:
        pos[i] += 1
result = [0 for i in range(m)]
left = 0
leftC = 0
right = 0
rightC = 0
for i in range(n + m):
    if ts[i] == 0:
        right = max(i, right)
        while right + 1 < n + m and not ts[right]:
            right += 1
        mP, mD = 0, 20000000
        if ts[left]:
            mP = pos[left]
            mD = xs[i] - xs[left]
        if ts[right] and xs[right] - xs[i] < mD:
            mD = xs[right] - xs[i]
            mP = pos[right]
        result[mP] += 1
    else:
        left = i
print(*result)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

n,m = mints()
a = list(mints())
b = list(mints())
l = [None]*(n+m)
r = [None]*(n+m)
c = [0]*(n+m)
x = None
for i in range(len(a)):
	l[i] = x
	if b[i] == 1:
		x = i
x = None
for i in range(len(a)-1,-1,-1):
	r[i] = x
	if b[i] == 1:
		x = i
for i in range(len(a)):
	if b[i] == 0:
		aa = a[i]
		ll = l[i]
		rr = r[i]
		if ll == None:
			if rr != None:
				c[rr] += 1
		elif rr == None:
			c[ll] += 1
		else:
			if aa-a[ll] <= a[rr]-aa:
				c[ll] += 1
			else:
				c[rr] += 1

for i in range(len(a)):
	if b[i] == 1:
		print(c[i], end=' ')


def solve(n, m, x, t):
    r = [0] * n
    d = [0] * m
    ans = [0] * m
    cr = 0
    cd = 0
    for i in range(n+m):
        if t[i]:
            d[cd] = x[i]
            cd += 1
        else:
            r[cr] = x[i]
            cr += 1
    cn = 0
    for i in range(m-1):
        mid = (d[i] + d[i+1]) // 2
        while cn < n and r[cn] <= mid:
            cn += 1
            ans[i] += 1
    ans[-1] += n - sum(ans)
    return ' '.join(str(i) for i in ans)


def main():
    n, m = [int(i) for i in input().split()]
    x = [int(i) for i in input().split()]
    t = [int(i) for i in input().split()]
    print(solve(n, m, x, t))


main()


n,m = map(int,input().split())
xi = list(map(int,input().split()))
ti = list(map(int,input().split()))
ai = [0] * (m+2)
ar = [0] * (m+2)
ar[-1] = 10**11
ar[0] = -100000000000
j = 1
n2 = n + m
for i in range(n2):
    if ti[i] == 1:
        ar[j] = xi[i]
        j += 1
i1 = 0
i2 = 1
for i in range(n2):
        if ti[i] == 1:
            i2 += 1
            i1 += 1
            continue
        num = xi[i] - ar[i1]
        num2 = ar[i2] - xi[i]
        if num <= num2:
            ai[i1] += 1
        else:
            ai[i2] += 1
for i in range(1,m+1):
    print(ai[i],end=" ")


n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = [0] * m
p = []
for i in range(n + m):
    if t[i] == 1:
        p.append(i)
ans[0] = p[0]
for i in range(m):
    if i == m - 1:
        ans[i] += n + m - p[i] - 1
    else:
        for j in range(p[i] + 1, p[i + 1]):
            if a[j] - a[p[i]] <= a[p[i + 1]] - a[j]:
                ans[i] += 1
            else:
                ans[i + 1] += 1
print(' '.join(map(str, ans)))


n, m = map(int, input().split())
dist = [int(x) for x in input().split()]
taxi = [int(x) for x in input().split()]
dists = {}
d = []
for person in range(len(taxi)):
    if taxi[person]:
        dists[dist[person]] = 0
        d.append(dist[person])
start = 0
d.append(10**11)
for person in range(len(taxi)):
    if taxi[person] == 0:
        while dist[person] > d[start + 1]:
            start += 1
        if abs(dist[person] - d[start]) <= abs(dist[person] - d[start + 1]):
            dists[d[start]] += 1
        else:
            dists[d[start + 1]] += 1
for d in dists:
    print(dists[d] if d!=10**11 else '', end=' ')



import sys

num_riders, _ = list(map(int, next(sys.stdin).split()))

houses = list(map(int, next(sys.stdin).split()))
is_rider = list(map(int, next(sys.stdin).split()))

current_left_driver = None
current_citizens = []

result = []

for house, is_rider in zip(houses, is_rider):
    if is_rider:
        if current_left_driver is None:
            result.append(len(current_citizens))
        else:
            result.append(0)
            for citizen in current_citizens:
                if abs(citizen - current_left_driver) <= abs(citizen - house):
                    result[-2] += 1
                else:
                    result[-1] += 1

        current_citizens = []
        current_left_driver = house
    else:
        current_citizens.append(house)

result[-1] += len(current_citizens)

print(' '.join(map(str, result)))


n, m = list(map(int, input().split(' ')))

distances = list(map(int, input().split(' ')))
taxiDriver = list(map(int, input().split(' ')))

people = []
drivers = []
result = [0] * m

for i in range(len(distances)):
  if(taxiDriver[i]):
    drivers.append(distances[i])
  else:
    people.append(distances[i])

j = 0

for person in people:
  if (j + 1) < len(drivers):
    while (j + 1) < len(drivers) and (drivers[j] - person) < (person - drivers[j + 1]) :
      j += 1
    
    result[j] += 1
  else:
    result[j] += 1

print(' '.join(map(str, result)))



n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))
t = list(map(int, input().split()))
taxi = list()
for i in range(len(arr)):
    if t[i] == 1:
        taxi.append(arr[i])
taxi2 = list()
kek = 1
for i in range(len(taxi) - 1):
    taxi2.append([kek, taxi[i] + (taxi[i + 1] - taxi[i]) // 2])
    kek = taxi[i] + (taxi[i + 1] - taxi[i]) // 2 + 1
taxi2.append([kek, arr[-1]])
taxi3 = [0] * m
j = 0
for i in range(len(arr)):
    if arr[i] > taxi2[j][1]:
        j += 1
    if t[i] != 1:
        taxi3[j] += 1
print(" ".join(map(str, taxi3)))


n,m=list(map(int,input().split()))
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
j=0
ansarr=[0]*m
temparr=[]
for i in range(n+m):
    if(arr2[i]==1):
        temparr.append(arr1[i])
#print(*temparr)
previ=-1
for i in range(n+m):
    #print(j)
    if(arr2[i]==1):
        j+=1
    else:
        if(j==0):
            ansarr[j]+=1
        elif(j==m):
            ansarr[j-1]+=1
        else:
            dist1=temparr[j]-arr1[i]
            dist2=abs(arr1[i]-temparr[j-1])
            #print(dist1,dist2,j,'Yo')
            if(dist1>=dist2):
                ansarr[j-1]+=1
            else:
                ansarr[j]+=1
print(*ansarr)



n, m = [int(x) for x in input().split()]
xs = [int(x) for x in input().split()]
ts = [int(x) for x in input().split()]


taxi_idx = sorted([xs[idx] for idx in range(n + m) if ts[idx] == 1])
passenger_idx = sorted([xs[idx] for idx in range(n + m) if ts[idx] == 0])

a_is = [0] * len(taxi_idx)
t_idx = 0
p_idx = 0

while True:
    if p_idx >= len(passenger_idx):
        break

    if t_idx == len(taxi_idx) - 1:
        a_is[t_idx] += 1
    else:
        while t_idx < len(taxi_idx) - 1:
            d1 = abs(passenger_idx[p_idx] - taxi_idx[t_idx])
            d2 = abs(passenger_idx[p_idx] - taxi_idx[t_idx + 1])
            # print(t_idx, d1, d2)
            if d1 > d2:
                t_idx += 1
            else:
                break

        a_is[t_idx] += 1

    p_idx += 1

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


q,w = map(int,input().split())
a = list(map(int,input().split()))
s = list(map(int,input().split()))
d = []
k = 0
for i in range(0,q+w):
    if (s[i]):
        d.append(a[i])
        k = i
d.append(100000000000)
t = 0
t1 = 1
g = 0
for i in a:
    if (i==d[t]):
        continue
    elif (i - d[t] <= d[t1] - i):
        g += 1
    else:
        print(g, end = " ")
        if (d[t1]==i):
            g = 0
        else:
            g = 1
        t += 1
        t1 += 1
print(g)


def main():
    # n = int(input())
    # a, b = list(map(int, input().split()))
    # if abs(a - 1) + abs(b - 1) <= abs(n - a) + abs(n - b) + 1:
    #     print("White")
    # else:
    #     print("Black")
    one = list(map(int, input().split()))
    location = list(map(int, input().split()))
    flag = list(map(int, input().split()))
    drivers = [location[i] for i in range(len(location)) if flag[i]]
    res = [0] * len(drivers)

    def bs(value):
        lo, hi = 0, len(drivers) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if drivers[mid] < value:
                lo = mid + 1
            else:
                hi = mid
        return lo

    for i in range(len(location)):
        if not flag[i]:
            lo = bs(location[i])
            if lo != 0 and drivers[lo] - location[i] >= location[i] - drivers[lo-1]:
                res[lo - 1] += 1
            else:
                res[lo] += 1

    print(' '.join(list(map(str, res))))


main()


import sys

n,m=map(int,sys.stdin.readline().split())
X=list(map(int,sys.stdin.readline().split()))
T=list(map(int,sys.stdin.readline().split()))

Taxi=[]
Res=[]

for i in range(n+m):
    if T[i]==1:
        Taxi.append(X[i])
    else:
        Res.append(X[i])


TMAP=[[0,0] for i in range(m)]

for i in range(m-1):
    TMAP[i][1]=(Taxi[i]+Taxi[i+1])//2
    TMAP[i+1][0]=(Taxi[i]+Taxi[i+1])//2+1

TMAP[m-1][1]=X[-1]

TCOUNT=[0 for i in range(m)]


i=0
for j in Res:
    while True:
        if TMAP[i][0]<=j<=TMAP[i][1]:
            TCOUNT[i]+=1
            break
        else:
            i+=1

for t in TCOUNT:
    print(t,end=" ")
    

    


from bisect import bisect_right as br
from bisect import bisect_left as bl
from math import *

def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True

def mhd(a,b,x,y):

    return abs(a-x)+abs(b-y)


ta = []
pa = []
d = {}
n,m = map(int,input().split())
a = list(map(int,input().split()))
t = list(map(int,input().split()))
for i in range(n+m):
    if(t[i]==1):
        ta.append(a[i])
        d[a[i]] = 0
    else:
        pa.append(a[i])
if(m==1):
    print(n)
else:
    ta.sort()
    for i in pa:
        li = bl(ta,i)
        if(li==0):
            d[ta[li]]+=1
        elif(li==m):
            d[ta[li-1]]+=1
        else:
            x = abs(ta[li-1]-i)
            y = abs(ta[li]-i)
            if(x<=y):
                d[ta[li-1]]+=1
            else:
                d[ta[li]]+=1
    for i in range(n+m):
        if(t[i]==1):
            print(d[a[i]],end=' ')

import sys

n, m = [int(w) for w in input().split()]
x = [int(w) for w in input().split()]
t = [int(w) for w in input().split()]

if m == 1:
    print(n)
    return

p = []
tx = []
for i in range(n+m):
    (tx if t[i] == 1 else p).append(x[i])

a = [0] * m
i = 0
for pi in p:
    while i < m-1 and pi > (tx[i]+tx[i+1])/2:
        i += 1
    a[i] += 1

print(" ".join(str(ai) for ai in a))


import bisect
n,m=map(int,input().split())
rid=[None for i in range(n)]
tax=[None for i in range(m)]
res=[0 for i in range(m)]
ss=input().split()
s=input().split()
indrid=0
indtax=0
for i in range(n+m):
    if s[i]=="0":
        rid[indrid]=int(ss[i])
        indrid+=1
    else:
        tax[indtax]=int(ss[i])
        indtax+=1
for x in rid:
    ind=bisect.bisect_left(tax,x)
    if ind==0:
        res[0]+=1
        continue
    if ind==m:
        res[m-1]+=1
        continue
    if tax[ind]-x<x-tax[ind-1]:
        res[ind]+=1
    else:
        res[ind-1]+=1
for i in res:
    print(i,end=" ")
print("")


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

def next(k,a):
    i=k+1
    while a[i]!=1: i+=1
    return i

ans=[0]*(m+1)

k=-1
k=next(k,b)
ans[1]=k
for i in range(2,m+1):
    kk=next(k,b)
    for j in range(k+1,kk):
        if a[j]-a[k]<=a[kk]-a[j]:
            ans[i-1]+=1
        else:
            ans[i]+=1
    k=kk
    

ans[m]+=(n+m-1-k)

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


n, m = map(int, input().split())
dist = list(map(int, input().split()))
taxists = list(map(int, input().split()))
left = [0] * (n + m)
right = [0] * (n + m)
MAX = 10000000000000000000
value = -MAX
cnt = 0
for i in range(n + m):
    if taxists[i] == 1:
        cnt += 1
        value = i
    left[i] = value

value = MAX
for i in range(n + m - 1, -1, -1):
    if taxists[i] == 1:
        value = i
    right[i] = value


answer = [0] * (n + m)
for i in range(n + m):
    if left[i] == -MAX:
        answer[right[i]] += 1
        continue
    if right[i] == MAX:
        answer[left[i]] += 1
        continue
    if abs(dist[left[i]] - dist[i]) <= abs(dist[i] - dist[right[i]]):
        answer[left[i]] += 1
    else:
        answer[right[i]] += 1
for i in answer:
    if i:
        print(i - 1, end = " ")


n, m = list(map(int,input().split()))
x = list(map(int,input().split()))
t = list(map(int,input().split()))
arr = []
pep = {}
for i in range(n+m):
    if t[i] == 0:
        arr.append(i)
        pep[x[i]] = 0
    else:
        for j in arr:
            pep[x[j]] = i
        arr = []
for i in range(n+m-1, -1, -1):
    if t[i] == 0:
        arr.append(i)
    else:
        for j in arr:
            if abs(x[j] - x[i]) <= abs(x[pep[x[j]]] - x[j]):
                pep[x[j]] = i
        arr = []
ans = []
for i in range(n+m):
    if t[i]:
        ans.append(1)
    else:
        ans.append(0)
for i in pep:
    ans[pep[i]] += 1
for i in ans:
    if i:
        print(i-1, end = ' ')




n,m = list(map(int,input().split()))
x = input().split()
t = input().split()
r = [0]*n
d = [0]*m
countr = 0
countd = 0
for i in range(n+m):
    if int(t[i]) == 1:
        d[countd] = int(x[i])
        countd += 1
    else:
        r[countr] = int(x[i])
        countr += 1
current = 0
count = [0]*m
for i in range(n):
    while current < m-1:
        if d[current+1] >= r[i]:
            break
        current += 1
    if current == m-1:
        count[m-1] += (n-i)
        break
    if 2*r[i] <= (d[current]+d[current+1]):
        count[current] += 1
    else:
        count[current+1] += 1
s = ""
for i in range(m):
    s += str(count[i])+" "
print(s[:-1])


n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
s = list(map(int, input().split()))
d = [0]*m
f = []
for q in range(len(s)):
    if s[q] == 1:
        f.append(a[q])
q2, q1 = -float('inf'), f[0]
q3, q4 = -1, 0
for q in range(len(a)):
    if s[q] == 1:
        q2, q1 = a[q], f[q4+1] if len(f) > q4+1 else float('inf')
        q3, q4 = q3+1, q4+1
    else:
        if q2 == -float('inf'):
            d[q4] += 1
        elif q1 == float('inf'):
            d[q3] += 1
        else:
            if a[q]-q2 <= q1-a[q]:
                d[q3] += 1
            else:
                d[q4] += 1
print(*d)


n, m = map(int, input().split())
s = n + m
x = list(map(int, input().split()))
loc = input().split()
t = []
for i in range(s):
    if loc[i] == '1':
        t.append(i)
for i in range(m):
    ans = 0
    if i != 0:
        for j in range(t[i - 1] + 1, t[i]):
            if x[j] - x[t[i - 1]] > x[t[i]] - x[j]:
                ans += 1
    else:
        ans += t[i]
    
    if i != m - 1:
        for j in range(t[i] + 1, t[i + 1]):
            if x[j] - x[t[i]] <= x[t[i + 1]] - x[j]:
                ans += 1
    else:
        ans += s - t[i] - 1
    
    print(ans, end = ' ')