First, for each color \(i = 1, 2, \ldots, M\), construct a variable-length array \(P^{(i)}\) containing the positions of the characters in \(S\) painted in color \(i\).

By scanning \(S\) once, we can obtain \(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) all at once in an \(O(N)\) time. Specifically, initialize the variable-length arrays \(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) with empty ones. Inspect \(S\) for each index \(i = 1, 2, \ldots, N\) in this order, and append \(i\) to the tail of the variable-length array \(P^{(C_i)}\).

With \(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\), the length-\(n\) string \(T\) to print is found as follows:

• Let \(P^{(1)} = (p^{(1)}_1, p^{(1)}_2, \ldots, p^{(1)}_{k_1})\). The \(p^{(1)}_2\)-th, \(\ldots\), \(p^{(1)}_{k_1}\)-th, and \(p^{(1)}_1\)-th and characters of \(T\) is found to be the \(p^{(1)}_1\)-th, \(p^{(1)}_2\)-th, \(\ldots\)-th, and \(p^{(1)}_{k_1}\)-th characters of \(S\).

• Let \(P^{(2)} = (p^{(2)}_1, p^{(2)}_2, \ldots, p^{(2)}_{k_1})\). The \(p^{(2)}_2\)-th, \(\ldots\), \(p^{(2)}_{k_1}\)-th, and \(p^{(2)}_1\)-th and characters of \(T\) is found to be the \(p^{(2)}_1\)-th, \(p^{(2)}_2\)-th, \(\ldots\)-th, and \(p^{(2)}_{k_1}\)-th characters of \(S\).

• \(\cdots\)

• Let \(P^{(M)} = (p^{(M)}_1, p^{(M)}_2, \ldots, p^{(M)}_{k_1})\). The \(p^{(M)}_2\)-th, \(\ldots\), \(p^{(M)}_{k_1}\)-th, and \(p^{(M)}_1\)-th and characters of \(T\) is found to be the \(p^{(M)}_1\)-th, \(p^{(M)}_2\)-th, \(\ldots\)-th, and \(p^{(M)}_{k_1}\)-th characters of \(S\).

The following is a sample code for this problem in C++ language.

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

int n, m;
string s;
int c[200000];
vector<int> p[200001];

int main(void)
{
    cin >> n >> m;
    cin >> s;
    for(int i = 0; i < n; i++) cin >> c[i];
    for(int i = 0; i < n; i++) p[c[i]].push_back(i);
    
    string t(n, '?');
    for(int i = 1; i <= m; i++){
        int k = p[i].size();
        for(int j = 0; j < k; j++) t[p[i][(j+1)%k]] = s[p[i][j]];
    }
    cout << t << endl;
    
    return 0;
}