Lexicographically Smallest String with Given Transitions

Given a string \(s = s_1 s_2 \cdots s_n\) of length \(n\) where \(s_i \in \{0, 1, ?\}\) and an integer \(k\), replace each '?' with either '0' or '1' so that the number of indices \(i\) satisfying \(1 \le i < n\) and \(s_i \ne s_{i+1}\) is exactly \(k\). Among all valid replacements (if any), output the lexicographically smallest string. If no valid replacement exists, output NO.

A string \(a = a_1a_2\cdots a_n\) is lexicographically smaller than \(b = b_1b_2\cdots b_n\) if there exists an index \(j\) such that \(a_i = b_i\) for all \(1 \le i < j\) and \(a_j < b_j\).

inputFormat

The input consists of two lines:

1. The first line contains a non-empty string \(s\) composed of characters '0', '1', and '?'.
2. The second line contains an integer \(k\) representing the required number of transitions.

outputFormat

Output a single line containing the lexicographically smallest valid string after replacing all '?' characters such that the number of transitions (i.e. positions \(i\) with \(s_i \ne s_{i+1}\)) is exactly \(k\). If no such string exists, output NO.

sample

1?0
1

100