Transformation of Sets with Minimum Cost

We are given a set \(B\) (with elements in \([1,n]\)) and an array \(p = [p_1, p_2, \dots, p_n]\). We want to select a subset \(A\) from \([1,n]\) such that the pair \((A,B)\) is good and the cost \[ C(A)=\sum_{i=1}^{n}[\,i\in A] \times p_i \] is minimized.

A pair of sets \((A,B)\) (both with elements in \([1,n]\)) is defined to be good if and only if one can transform \(A\) into \(B\) by a finite number of the following operations:

• In each operation, select an element \(x\) in \(A\); remove \(x\) from \(A\), and then add \(x-1\) and \(x+1\) to \(A\) (if duplicates occur, keep only one copy).

It can be shown that a necessary and sufficient condition for \(B\) to be reachable from \(A\) is that the invariant \[ \Delta(X)=\#\{\text{even numbers in }X\} - \#\{\text{odd numbers in }X\} \] remains equal modulo 3. In other words, a subset \(A\) (with at least one element if \(B\) is nonempty) can be transformed into \(B\) if and only if \[ \Delta(A)\equiv \Delta(B)\pmod{3}. \]

Your task is to choose a subset \(A\subseteq\{1,2,\dots,n\}\) (if \(B\) is nonempty, require \(A\neq \emptyset\)) which satisfies \[ (\#\{\text{even }i\in A\} - \#\{\text{odd }i\in A\}) \equiv (\#\{\text{even }i\in B\} - \#\{\text{odd }i\in B\}) \pmod{3}, \] and minimizes \(C(A)\). If there are multiple answers, any one is acceptable. The output should be the chosen set \(A\) printed in increasing order; first output its size \(k\) on one line, followed by a line with the \(k\) numbers (if \(k=0\), output a single line with 0).

inputFormat

The input consists of the following lines:

1. An integer \(n\) (\(1 \le n \le \) appropriate limit), the size of the initial domain \([1,n]\).
2. An integer \(m\) (\(0 \le m \le n\)), the number of elements in set \(B\). Note: if \(m=0\) then \(B\) is empty.
3. If \(m > 0\), a line with \(m\) distinct integers in the range \([1,n]\) representing the set \(B\).
4. A line with \(n\) integers \(p_1, p_2, \dots, p_n\), where \(p_i\) is the cost associated with including \(i\) in \(A\).

outputFormat

If a valid subset \(A\) exists (according to the rules above), output it in the following format:

1. On the first line, an integer \(k\) indicating the number of elements in the chosen \(A\) (or 0 if \(A\) is empty).
2. If \(k > 0\), on the second line output the \(k\) elements of \(A\) in strictly increasing order, separated by spaces.

If no such subset \(A\) exists, output a single line containing -1.

sample

3
2
1 2
1 2 3

2
1 2