You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

A 城是一个独特的城市，因为它是一条无尽的数轴。

打车软件 U 如今非常流行，其被城市中所有的 $m$ 名出租车司机使用，他们每天运送剩下的城市居民——$n$ 名乘客。

A 城的每个居民（包括出租车司机）都住在一个独一无二的位置，也就是说没有两个居民的坐标是相同的。

U 的系统非常聪明：当乘客叫车时，他的呼叫不会传给所有的出租车司机，而只会传给离他最近的那个司机。如果有多个司机距离相同，那么坐标较小的司机会收到呼叫。

但是，有一天早上，出租车司机们好奇：当一个乘客是当天第一个叫车的，会有多少乘客选择给指定的出租车司机打电话？换句话说，你需要为每个出租车司机 $i$ 找到 $a_i$——当所有司机和乘客都在家时，会有多少乘客选择给第 $i$ 名出租车司机打电话？

出租车司机不能接送自己或呼叫其他出租车司机。

输入格式

第一行两个正整数 $n,m$。

第二行 $n+m$ 个正整数 $x_1,x_2,\cdots,x_{n+m}$，其中 $x_i$ 表示第 $i$ 位居民的家的位置。

第三行 $n+m$ 个整数 $t_1,t_2,\cdots,t_{n+m}$ 表示每个居民的身份，如果 $t_i=1$，那么第 $i$ 个居民是司机，否则他是乘客。

保证 $t_i=1$ 的 $i$ 的数量恰为 $m$。

输出格式

一行 $m$ 个整数 $a_1,a_2,\cdots,a_m$，其中 $a_i$ 是第 $i$ 名出租车司机的答案。家坐标第 $i$ 小的出租车司机编号为 $i$。

样例 1 输入

3 1
1 2 3 10
0 0 1 0

样例 1 输出

3

样例 1 解释

只有一个出租车司机，这意味着所有 $n$ 名乘客的订单都会传给他。

样例 2 输入

3 2
2 3 4 5 6
1 0 0 0 1

样例 2 输出

2 1

样例 2 解释

第一个出租车司机住在坐标为 $2$ 的点，第二个出租车司机住在坐标为 $6$ 的点。显然，住在坐标 $3$ 的乘客最接近第一个出租车司机，而住在坐标 $5$ 的乘客最接近的是第二个出租车司机。住在坐标 $4$ 的乘客与第一个和第二个出租车司机的距离相同，但因为第一个出租车司机的坐标较小，所以这个乘客的呼叫会传给第一个出租车司机。

样例 3 输入

1 4
2 4 6 10 15
1 1 1 1 0

样例 3 输出

0 0 0 1

样例 3 解释

有一个乘客，离他最近的是第四个出租车司机。

数据规模与约定

对于 $40\%$ 的数据，$1\leq n,m\leq 1000$。

对于另外 $30\%$ 的数据，司机全部在一个区间内，即存在区间 $[l,r]\subseteq [1,n+m]$，满足 $r-l+1=m$，且对于所有 $l\leq i\leq r$，均有 $t_i=1$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$1\leq x_1<x_2<\cdots<x_{n+m}\leq 10^9$，$0\leq t_i\leq 1$，$t_i=1$ 的 $i$ 恰有 $m$ 个。