#include <vector>
#include <iostream>
using namespace std;

void riprogramma(int N, int k, vector<int>& c){
    if(k == 2){
        bool controllo = false;
        while(controllo == false){
            if(c[N-1] == c[N-2]){
                if(c[N-2] == 1){
                    c[N-1] = 2;
                }else{
                    c[N-2] = 1;
                }
            }
            for(int i=N-2; i>1; i--){
                if(c[i] == c[i-1]){
                    if(c[i+1] == c[i-1]){
                        if(c[i+1] == 2){
                            c[i] = 1;
                        }else{
                            c[i] = 2;
                        }
                    }else{
                        if(c[i-1] != c[i-2]){
                            int f=c[i-1];
                            c[i-1] = c[i-2];
                            c[i-2] = f;
                        }
                    }
                }
            }
            if(c[0] == c[1]){
                if(c[1] == 1){
                    c[0] = 2;
                }else{
                    c[0] = 1;
                }
            }
            controllo = true;
            for(int i=0; i<N and controllo == true; i++){
                if(c[i] == c[i+1]){
                    controllo = false;
                }
            }
        }
    }else{
        bool controllo = false;
        for (int i = 1; i < N-1; i++){
            if(c[i] == c[i-1]){
                for(int j=1; j<=k and controllo == false; j++){
                    if(j != c[i-1] and c[i+1] != j){
                        c[i] = j;
                        controllo = true;
                    }
                }
            }
            controllo = false;
        }
        if(c[N-1] == c[N-2]){
            for(int j=1; j<=k and controllo == false; j++){
                if(j != c[N-2]){
                    c[N-1] = j;
                    controllo = true;
                }
            }
        }
    }
}