CTT 最简单题目。先通过莫反来去掉最小的限制，即设 $g = f * \mu$，则 $w(l,r) = \sum_i g_{(r-l+1) / i}$，其中 $i$ 是任意整周期。考虑求出每一个 run $(l', r', p)$，然后计算 $[l,r] \subseteq [l', r']$ 且 $p \mid i$ 的贡献；先枚举 $i$，再枚举 $j = r - l + 1$，这样对 $r \in [l' + j - 1, r']$ 的答案产生了 $g_i$ 的贡献，差分即可处理；因为 $p \mid i$ 的所有 run 不会重叠，即固定 $i$ 后总长 $\sum r'-l'+1$ 不超过 $n$，同时 $i \mid j$ 且 $j \le r'-l'+1$，于是总的枚举量是调和级数的 $O(n \log n)$，复杂度同样。Submission。

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
using i64 = long long;
using uint = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using arr = array<int, 2>;
using vec = vector<int>;
using pii = pair<int, i64>;
const int N = 1e6 + 5;
const int P = 998244353;

void add(int &x, int y) { if ((x += y) >= P) x -= P; }
void sub(int &x, int y) { if ((x -= y) < 0) x += P;}

int n, mx[N]; char s[N];
int f[N], ans[N]; bool vis[N];

int orz[N], buc[N], id[N], pid[N];
struct SA {
  char s[N]; int sa[N], rk[N], ht[21][N];
  void Init() {
    int w = 1, m = 1 << 7, p = 0;
    auto cmp = [&](int x, int y) -> bool
      { return orz[x] == orz[y] && orz[x + w] == orz[y + w]; } ;
    auto Sort = [&]() -> void {
      F(i, 0, m) buc[i] = 0;
      F(i, 1, n) ++buc[pid[i] = rk[id[i]]];
      F(i, 1, m) buc[i] += buc[i - 1];
      dF(i, n, 1) sa[buc[pid[i]]--] = id[i];
    } ;
    F(i, 1, n) rk[i] = s[i], id[i] = i; Sort();
    for (; ; w <<= 1, m = p, p = 0) {
      dF(i, n, n - w + 1) id[++p] = i;
      F(i, 1, n) if (sa[i] > w) id[++p] = sa[i] - w;
      Sort(), p = 0; F(i, 1, n) orz[i] = rk[i];
      F(i, 1, n) rk[sa[i]] = cmp(sa[i - 1], sa[i]) ? p : ++p;
      if (p == n) break;
    }
    for (int i = 1, k = 0; i <= n; ++i) {
      if (k > 0) --k;
      while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
      ht[0][rk[i]] = k;
    }
    F(i, 1, 20) F(j, 1, n - (1 << i) + 1)
      ht[i][j] = min(ht[i - 1][j], ht[i - 1][j + (1 << i - 1)]);
  }
  int LCP(int x, int y) {
    if (!x || !y || x > n || y > n) return 0;
    if (x == y) return n - x + 1;
    if (rk[x] > rk[y]) swap(x, y); int k = __lg(rk[y] - rk[x]);
    return min(ht[k][rk[x] + 1], ht[k][rk[y] - (1 << k) + 1]);
  }
} pre, suf;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> s;
  F(i, 1, n) pre.s[i] = suf.s[n - i + 1] = s[i - 1];
  pre.Init(), suf.Init();
  F(i, 1, n) cin >> f[i];
  F(i, 2, n) {
    if (vis[i]) continue;
    F(j, 2, n / i) vis[i * j] = 1;
    dF(j, n / i, 1) sub(f[i * j], f[j]);
  }
  auto Sol = [&](int l, int r, int p) -> void {
    for (int q = p; (q << 1) <= r - l + 1; q += p)
      F(d, 2, (r - l + 1) / q)
        add(ans[l + q * d - 1], f[d]),
        sub(ans[r + 1], f[d]);
  } ;
  F(p, 1, n >> 1) {
    int lst = -1;
    F(i, 1, n / p - 1) {
      int u = p * i, v = p * (i + 1);
      int x = pre.LCP(u + 1, v + 1);
      int y = suf.LCP(n - u + 1, n - v + 1);
      if (u + x >= v - y) {
        int l = u - y + 1, r = v + x;
        if (r != lst && r > mx[l])
          Sol(l, r, p), mx[l] = r;
      }
    }
  }
  F(i, 1, n) add(ans[i], ans[i - 1]);
  F(i, 1, n) add(ans[i], 1ll * i * f[1] % P);
  F(i, 1, n) cout << ans[i] << " ";
  return 0;
}