Tìm vị trí ~i~ nhỏ nhất sao cho ~S_i \neq S_{n - i + 1}~. Gọi ~ans~ là mảng đáp án.

Với các vị trí ~j < i~ thì ~ans_j = ans_i + C \times (i - j)~.

Với các vị trí ~j > n - i + 1~ thì ~ans_j = ans_{n - i + 1} + C \times (j - (n - i + 1))~.

Do đó ta chỉ quan tâm tới việc tính toán những vị trí ~i \le j \le n - i + 1~. Thật vậy tại ~j~, ta luôn đi sang trái rồi đến ~n - i + 1~ hoặc sang phải rồi đến ~i~.

Xét trường hợp sang phải rồi đến ~i~. Ta chỉ cần tìm ~r~ sao cho ~P_r + C \times (r - j) + C \times (r - i)~ đạt giá trị nhỏ nhất trong đó ~P_r~ là chi phí nhỏ nhất thay đổi kí tự nếu ta chỉ thay đổi các kí tự trong đoạn ~[i, r]~. Việc tính toán có thể làm trong ~O(n)~.

Tương tự với trường hợp còn lại.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
template <typename A, typename B> bool maximize(A& a, B b) {
    return a < b ? a = b, true : false;
}
template <typename A, typename B> bool minimize(A& a, B b) {
    return a > b ? a = b, true : false;
}

const ll INF = 4557430888798830399;
const int N = 1e6 + 5;

int n, c;
string s;
int a[N];
ll f[N], g[N];
ll ans[N];
ll suff[N];

void solve() {
    cin >> s >> c;
    n = s.length();
    s = " " + s;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    vector<int> l, r;
    for (int i = 1; i <= n / 2; ++ i) {
        if (s[i] != s[n - i + 1]) {
            l.push_back(i);
            r.push_back(n - i + 1);
        }
    }
    if (l.size() == 0) {
        for (int i = 1; i <= n; ++ i) {
            cout << 0 << " \n"[i == n];
        }
        return;
    }
    // memset(ans, 0x3f, sizeof ans);
    for (int i = 1; i <= n; ++ i) {
        ans[i] = INF;
    }

    {
        ll sum = 0;
        for (int i = 1; i <= n / 2; ++ i) {
            if (s[i] != s[n - i + 1]) {
                sum += a[i];
            }
        }

        r.push_back(l.back());
        sort(r.begin(), r.end());

        f[0] = sum + 1ll * (l.back() - l[0]) * c;
        int run = (n + 1) / 2 + 1;
        for (int i = 1; i + 1 < (int)r.size(); ++ i) {
            while (run <= r[i]) {
                if (s[run] != s[n - run + 1]) {
                    sum -= a[n - run + 1];
                    sum += min(a[n - run + 1], a[run]);
                }
                ++ run;
            }
            clog << db(i) << db(run) << db(sum) << db(r[i]) << endl;
            f[i] = sum + 1ll * (r[i] - l[0]) * c;
        }
        for (int i = 0; i <= n + 1; ++ i) {
            suff[i] = INF;
        }
        // memset(suff, 0x3f, sizeof suff);
        map<int, int> dd;
        for (int i = 0; i + 1 < (int)r.size(); ++ i) {
            // st.insert(f[i] + 1ll * r[i] * c);
            dd[r[i]] = i + 1;
        }
        for (int i = 0; i + 1 < (int)r.size(); ++ i) {
            suff[r[i]] = min(suff[r[i]], f[i] + 1ll * r[i] * c);
        }
        for (int i = n; i >= 1; -- i) {
            suff[i] = min(suff[i], suff[i + 1]);
        }
        ll mn = *min_element(f, f + (int)r.size() - 1);
        for (int i = 1; i <= n; ++ i) {
            ans[i] = mn + 1ll * abs(i - l[0]) * c;
        }
        mn = INF;
        for (int i = 1; i <= n; ++ i) {
            minimize(ans[i], mn + 1ll * i * c);
            // if (st.size()) {
                minimize(ans[i], suff[i] - 1ll * i * c);
            // }
            if (dd[i]) {
                mn = min(mn, f[dd[i] - 1] - 1ll * i * c);
            }
        }
    }

    // for (int i = 1; i <= n; ++ i) {
    //     cout << ans[i] << " \n"[i == n];
    // }
    // cout << endl;

    {
        ll sum = 0;
        for (int i = 1; i <= n / 2; ++ i) {
            if (s[i] != s[n - i + 1]) {
                sum += a[n - i + 1];
            }
        }

        l.push_back(r[1]);
        sort(l.begin(), l.end());

        g[(int)l.size() - 1] = sum + 1ll * (r.back() - r[1]) * c;
        int run = n / 2;
        for (int i = (int)l.size() - 2; i >= 1; -- i) {
            while (run >= l[i]) {
                if (s[run] != s[n - run + 1]) {
                    sum -= a[n - run + 1];
                    sum += min(a[n - run + 1], a[run]);
                }
                -- run;
            }
            g[i] = sum + 1ll * (r.back() - l[i]) * c;
        }
        // memset(suff, 0x3f, sizeof suff);
        for (int i = 0; i <= n + 1; ++ i) {
            suff[i] = INF;
        }
        map<int, int> dd;
        multiset<ll> st;
        for (int i = 1; i < (int)l.size(); ++ i) {
            // st.insert(g[i] + 1ll * l[i] * c);
            dd[l[i]] = i + 1;
        }
        for (int i = 1; i < (int)l.size(); ++ i) {
            suff[l[i]] = min(suff[l[i]], g[i] + 1ll * l[i] * c);
            clog << db(i) << db(g[i]) << db(l[i]) << db(g[i] + 1ll * l[i] * c) << endl;
        }
        for (int i = n; i >= 1; -- i) {
            suff[i] = min(suff[i], suff[i + 1]);
        }
        ll mn = *min_element(g + 1, g + (int)l.size());
        for (int i = 1; i <= n; ++ i) {
            ans[i] = min(ans[i], mn + 1ll * abs(i - r.back()) * c);
        }

        mn = INF;
        for (int i = 1; i <= n; ++ i) {
            ans[i] = min(ans[i], mn + 1ll * i * c);
            // if (st.size()) {
                // minimize(ans[i], *st.begin() - 1ll * i * c);
                minimize(ans[i], suff[i] - 1ll * i * c);
            // }
            if (dd[i]) {
                // st.erase(st.find(g[dd[i] - 1] + 1ll * i * c));
                mn = min(mn, g[dd[i] - 1] - 1ll * i * c);
            }
        }
    }
    for (int i = 1; i <= n; ++ i) {
        cout << ans[i] << " \n"[i == n];
    }

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
#endif
    int tt;
    cin >> tt;
    while (tt --)
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}