Andi is a mathematician, a computer scientist, and a songwriter. After spending so much time writing songs, he finally writes a catchy melody that he thought as his best creation. However, the singer who will sing the song/melody has a unique vocal range, thus, an adjustment may be needed.
A melody is defined as a sequence of \(N\) notes which are represented by integers. Let \(A\) be the original melody written by Andi. Andi needs to adjust \(A\) into a new melody \(B\) such that for every \(i\) where \(1 \le i < N\):
- If \(A_i < A_{i+1}\), then \(B_i < B_{i+1}\).
- If \(A_i = A_{i+1}\), then \(B_i = B_{i+1}\).
- If \(A_i > A_{i+1}\), then \(B_i > B_{i+1}\).
- \(|B_i - B_{i+1}| \le K\), i.e. the difference between two successive notes is no larger than \(K\).
Moreover, the singer also requires that all notes are within her vocal range, i.e.
\(L \le B_i \le R\) for all
\(1 \le i \le N\).
Help Andi to determine whether such \(B\) exists, and find the lexicographically smallest \(B\) if it exists. A melody \(X\) is lexicographically smaller than melody \(Y\) if and only if there exists \(j\) (\(1 \le j \le N\)) such that \(X_i = Y_i\) for all \(i < j\) and \(X_{j} < Y_{j}\).
For example, consider a melody \(A = \{1,3,5,6,7,8,9,10,3,7,8,9,10,11,12,12\}\) as shown in the following figure. The diagonal arrow up in the figure implies that \(A_i < A_{i+1}\), the straight right arrow implies that \(A_i = A_{i+1}\), and the diagonal arrow down implies that \(A_i > A_{i+1}\).
Supposed we want to make a new melody with \(L = 1\), \(R = 8\), and \(K = 6\). The new melody \(B = \{1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,8\}\) as shown in the figure satisfies all the requirements, and it is the lexicographically smallest possible.