אחרי שנים של ארגון משחקים וצפייה ב־Bessie מסיימת ראשונה שוב ושוב, Farmer John הבין שאין זו מקריות. הוא הסיק שהניצחון חייב להיות מקודד ב־DNA שלה ויצא לחפש את הגן ״המנצח״ הזה.

הוא פיתח תהליך לזיהוי מועמדים אפשריים לגן. הגנום של Bessie הוא מחרוזת $S$ באורך $N$, כאשר $1 \leq N \leq 3000$. הוא בוחר זוג $(K,L)$ עם $1 \leq L \leq K \leq N$, שמשמעותו שהגנים המועמדים באורך $L$ ויימצאו בתוך תת־מחרוזת גדולה יותר באורך $K$. הוא לוקח את כל תת־המחרוזות של $S$ באורך $K$, ולכל אחת נקרא $k$-mer. לכל $k$-mer הוא לוקח את כל תת־המחרוזות באורך $L$ ובוחר את הקטנה ביותר בסדר לקסיקוגרפי כמועמדת לגן מנצח (השמאלית ביותר במקרה של שוויון). לאחר מכן הוא מוסיף לקבוצה $P$ את מיקום ההתחלה $p_i$ שלה ב־$S$, באינדקסים החל מ־$0$.

מכיוון שעוד לא בחר את $K$ ואת $L$, הוא רוצה לדעת את מספר המועמדים לכל זוג $(K,L)$.

לכל $v$ ב־$1\dots N$, עזרו לו לקבוע את מספר הזוגות $(K,L)$ שעבורם $|P|=v$.

קלט

$N$ מייצג את אורך המחרוזת ו־$S$ את המחרוזת הנתונה. מובטח שכל התווים הם אותיות גדולות עם $s_i \in A-Z$, שכן הגנטיקה של הבקר מתקדמת הרבה יותר משלנו.

פלט

לכל $v$ ב־$1\dots N$, הדפיסו את מספר הזוגות $(K,L)$ שעבורם $|P|=v$, כל מספר בשורה נפרדת.

דוגמאות

קלט 1

8
AGTCAACG

פלט 1

11
10
5
4
2
2
1
1

הערה

במקרה זה, השורה השלישית בפלט היא 5, כי בדיוק 5 זוגות של $K$ ו־$L$ נותנים שלושה גנים ״מנצחים״ מועמדים. המועמדים הם הבאים ($p_i$ הוא באינדקסים החל מ־$0$):

(4,2) -> P = [0,3,4]
(5,3) -> P = [0,3,4]
(6,4) -> P = [0,3,4]
(6,5) -> P = [0,1,3]
(6,6) -> P = [0,1,2]

כדי לראות כיצד (4,2) נותן את התוצאות האלה, ניקח את כל ה־$4$-mers:

AGTC
GTCA
TCAA
CAAC
AACG

לכל $4$-mer נמצא את תת־המחרוזת באורך 2 הקטנה ביותר בסדר לקסיקוגרפי:

AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA

נוסיף לקבוצה $P$ את מיקומי תת־המחרוזות האלה במחרוזת המקורית ונקבל $P = [0,3,4]$.

לעומת זאת, הזוג $(4,1)$ נותן רק $2$ גנים ״מנצחים״ מועמדים בסך הכול. אם ניקח את כל ה־$4$-mers ונמצא את תת־המחרוזת באורך $1$ הקטנה ביותר בסדר לקסיקוגרפי (בעזרת A, A' ו־A* כדי להבחין בין אותיות A שונות), נקבל:

AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'

בשלושת המקרים האחרונים גם A' וגם A* קטנות ביותר בסדר לקסיקוגרפי, אך לתת־המחרוזת השמאלית ביותר יש עדיפות. לכן בכל המקרים האלה רק A' נספרת כמועמדת. פירוש הדבר הוא $P = [0,4]$.

ניקוד

• קלטים 2-4: $N \leq 100$
• קלטים 5-7: $N \leq 500$
• קלטים 8-16: ללא מגבלות נוספות.

מחבר הבעיה: Suhas Nagar