Optimal Travel Plan for Little L

In the far‐away country of HX, a traveler named Little L wants to tour the country on his bicycle. There are n cities numbered from 1 to n. Each city either has an attraction that Little L wishes to visit or does not have any. Little L has already determined a route that is a permutation a₁, a₂, \(\ldots\), a_n of the cities which is the shortest route to visit all the cities with attractions (note that the order is arbitrary).

He plans to complete his trip in exactly m months (m < n), so he must partition his journey into m segments. In each month, he visits one or more new cities consecutively. He always ends the month by resting in the last city he visits that month. Let the resting cities be x₁, x₂, \(\ldots\), x_m with x_m = a_n. For example, if n = 5, m = 3, and (a₁,a₂,a₃,a₄,a₅) = (3,2,4,1,5), a valid segmentation is (x₁,x₂,x₃) = (2,1,5):

• Month 1: cities 3 and 2 are visited, and Little L rests in city 2.
• Month 2: cities 4 and 1 are visited, and he rests in city 1.
• Month 3: city 5 is visited, and he rests in city 5.

Whenever Little L arrives at a city, he gains 1 unit of happiness if that city has an attraction, and 1 unit of fatigue if it does not. In each month, let the difference d_i be defined as the absolute difference between the total happiness and fatigue values in that month. For a segmentation plan with monthly differences d₁, d₂, \(\ldots\), d_m, define c as the maximum of these differences. Little L wants to choose a travel plan which minimizes c across all possible segmentations. If there are multiple segmentation plans achieving the minimum value of c, he chooses the one with the lexicographically smallest resting sequence (x₁,x₂, \(\ldots\),x_m) (compare two sequences by the first position where they differ).

Your task is to help Little L by computing and outputting the lexicographically smallest resting sequence corresponding to a segmentation whose maximum monthly happiness‐fatigue difference c is minimized.

Note: For any contiguous segment from position i+1 to j in the route (with 0-index correction), let s denote the sum of attraction indicators in that segment and \(\ell\) be the number of cities in the segment. Then the monthly difference is given by \[ d = |2s - \ell|. \]

inputFormat

The first line contains two integers n and m (m < n), where n is the number of cities and m is the number of months.

The second line contains n distinct integers a₁, a₂, \(\ldots\), a_n representing the travel route.

The third line contains n integers, each either 0 or 1. The i^th integer indicates whether the city a_i has an attraction (1) or not (0).

outputFormat

Output a single line containing m integers x₁, x₂, \(\ldots\), x_m, where x_i is the city where Little L rests at the end of month i. The sequence must be the lexicographically smallest resting sequence among those segmentation plans that achieve the minimum possible maximum monthly difference c.

sample

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

2 1 5