Cho một xâu \(s\) có độ dài \(n\) và dãy hệ số \(f_1,f_2,\ldots,f_n\).

Một số nguyên dương \(d\) là chu kỳ của xâu con \(s[l..r]\) khi và chỉ khi \(d\le r-l+1\) và \(s_i=s_{i+d}\) với mọi \(l\le i\le r-d\).

Một số nguyên dương \(d\) là chu kỳ nguyên của \(s[l..r]\) khi và chỉ khi \(d\) là chu kỳ của xâu con này và \(d\) chia hết \(r-l+1\).

Với \(1\le l\le r\le n\), gọi giá trị của xâu con \(s[l..r]\) là

trong đó \(d\) là chu kỳ nguyên nhỏ nhất của \(s[l..r]\).

Với mỗi \(1\le i\le n\), hãy tính tổng giá trị của tất cả xâu con có đầu mút phải là \(i\):

Do kết quả có thể rất lớn, hãy in các kết quả theo modulo \(998\,244\,353\).

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa xâu \(s\) gồm \(n\) chữ cái tiếng Anh viết thường.
• Dòng thứ ba chứa \(n\) số nguyên không âm \(f_1,f_2,\ldots,f_n\).

Dữ liệu ra

In một dòng gồm \(n\) số nguyên không âm. Số thứ \(i\) là tổng giá trị của mọi xâu con có đầu mút phải là \(i\), lấy modulo \(998\,244\,353\).

Ràng buộc

Mỗi ký tự \(s_i\) là một chữ cái tiếng Anh viết thường.

Chấm điểm

Ký hiệu \([P]\) bằng \(1\) nếu mệnh đề \(P\) đúng và bằng \(0\) nếu \(P\) sai.

Tính chất A: \(f_i=[2\mid i]\) với mọi \(1\le i\le n\).

Tính chất B: tồn tại số nguyên dương \(k\) sao cho \(f_i=[k\mid i]\) với mọi \(1\le i\le n\).

Ví dụ

8
babaaabb
0 1 1 0 0 0 0 0

0 0 0 1 1 2 0 1

Các xâu con có giá trị khác \(0\) là:

• \(s[1..4]=\) baba: chu kỳ nguyên nhỏ nhất là \(2\), giá trị bằng \(1\).
• \(s[4..5]=\) aa: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).
• \(s[4..6]=\) aaa: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).
• \(s[5..6]=\) aa: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).
• \(s[7..8]=\) bb: chu kỳ nguyên nhỏ nhất là \(1\), giá trị bằng \(1\).

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.