Minimize Maximum Subarray Sum

Given two sequences a and b of length n and an integer k, you need to construct a sequence c as follows: choose exactly k indices i where you set c_i = a_i, and for the remaining indices, assign c_i = b_i.

Let the maximum subarray sum of a sequence be defined as:

$$\max_{1\leq L \leq R \leq n}\Big(\sum_{i=L}^{R} c_i\Big)$$

Your task is to choose the indices such that the maximum subarray sum of c is as small as possible. Output the minimum achievable maximum subarray sum and one valid assignment of indices. In the assignment, output a binary sequence of length n where a value of 1 indicates that index is chosen from a (i.e. c_i=a_i), and 0 indicates that index is taken from b.

Hint: Notice that if we denote diff[i] = a[i] - b[i] then the choice of index i increases the value at that position by diff[i]. Hence, to minimize the maximum subarray sum, it is optimal to choose those indices where diff[i] is smallest.

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 10⁵).

The second line contains n integers representing the sequence a.

The third line contains n integers representing the sequence b.

outputFormat

On the first line, print the minimized maximum subarray sum of the constructed sequence c.

On the second line, print n integers (each either 0 or 1) separated by spaces representing your assignment. Here, 1 indicates that c_i is taken from a and 0 indicates that it is taken from b.

sample

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

9
1 1 0 0 0