״כנס טעימות היין הקיצי השנתי של Huanying Pavilion״ נפתח ברוב פאר. הכנס כולל שני שלבים, טעימות ואתגר משעשע, שבהם מוענקים לזוכים, בהתאמה, הפרסים ״טועם היין הראשי״ ו״הצייד הראשי״, והוא משך אליו טועמי יין רבים.
בארוחת הערב של הכנס הכין הברמן Rainbow $n$ כוסות קוקטייל. $n$ הכוסות מסודרות בשורה, ועל הכוס ה־$i$ ($1\le i\le n$) מודבקת תווית $s_i$, שהיא אחת מ־26 האותיות האנגליות הקטנות. נסמן ב־$Str(l,r)$ את המחרוזת המתקבלת משרשור $r-l+1$ התוויות של הכוסות מהכוס ה־$l$ עד הכוס ה־$r$, לפי הסדר. אם $Str(p,po)=Str(q,qo)$, כאשר $1\le p\le po\le n$, $1\le q\le qo\le n$, $p\ne q$, ו־$po-p+1=qo-q+1=r$, נאמר שהכוס ה־$p$ והכוס ה־$q$ הן ״דומות ברמה $r$״. כמובן, שתי כוסות הדומות ברמה $r$ עבור $r>1$ דומות גם ברמות $1,2,\ldots,r-1$. בפרט, לכל $1\le p,q\le n$, $p\ne q$, הכוסות ה־$p$ וה־$q$ דומות ברמה $0$.
בשלב הטעימות העריכה טועמת היין Freda בקלות את מידת הטעימות של כל כוס, וזכתה בתואר ״טועמת היין הראשית״ בזכות מקצועיותה וניסיונה. מידת הטעימות של הכוס ה־$i$ ($1\le i\le n$) היא $a_i$. כעת מפרסם Rainbow את שאלת האתגר: לקוקטיילים שהוכנו בכנס יש תכונה מיוחדת — ערבוב הכוס ה־$p$ והכוס ה־$q$ יוצר כוס שמידת טעימותה $a_pa_q$. על טועמי היין לחשב, לכל $r=0,1,2,\ldots,n-1$, את מספר הדרכים לבחור שתי כוסות הדומות ברמה $r$, ואת מידת הטעימות המרבית שאפשר לקבל מערבוב שתי כוסות הדומות ברמה $r$.
קלט
קראו את הנתונים מהקובץ savour.in.
השורה הראשונה של קובץ הקלט מכילה מספר שלם חיובי $n$, המציין את מספר כוסות הקוקטייל.
השורה השנייה מכילה מחרוזת $S$ באורך $n$, שהתווית של הכוס ה־$i$ היא התו ה־$i$ בה.
השורה השלישית מכילה $n$ מספרים שלמים, כשמספרים סמוכים מופרדים ברווח יחיד. המספר ה־$i$ מציין את מידת הטעימות $a_i$ של הכוס ה־$i$.
פלט
כתבו את הפלט לקובץ savour.out.
קובץ הפלט יכיל $n$ שורות. בשורה ה־$i$ הדפיסו שני מספרים שלמים, המופרדים ברווח יחיד. הראשון מציין את מספר הדרכים לבחור שתי כוסות הדומות ברמה $i-1$, והשני מציין את מידת הטעימות המרבית שניתן לקבל מערבוב שתי כוסות הדומות ברמה $i-1$. אם אין שתי כוסות הדומות ברמה $i-1$, שני המספרים יהיו $0$.
דוגמאות
קלט 1
10 ponoiiipoi 2 1 4 7 4 8 3 6 4 7
פלט 1
45 56 10 56 3 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0
הסבר
הזוג $(p,q)$ מציין את הכוס ה־$p$ ואת הכוס ה־$q$.
דמיון ברמה $0$: כל $45$ הזוגות דומים ברמה $0$, ומידת הטעימות המרבית היא $8\times7=56$.
דמיון ברמה $1$: $(1,8)$, $(2,4)$, $(2,9)$, $(4,9)$, $(5,6)$, $(5,7)$, $(5,10)$, $(6,7)$, $(6,10)$, $(7,10)$. הערך המרבי הוא $8\times7=56$.
דמיון ברמה $2$: $(1,8)$, $(4,9)$, $(5,6)$. הערך המרבי הוא $4\times8=32$.
אין שתי כוסות הדומות ברמות $3,4,5,\ldots,9$, ולכן עבור כולן מודפס $0$.
קלט 2
12 abaabaabaaba 1 -2 3 -4 5 -6 7 -8 9 -10 11 -12
פלט 2
66 120 34 120 15 55 12 40 9 27 7 16 5 7 3 -4 2 -4 1 -4 0 0 0 0
דוגמה 3
ראו את הקבצים savour/savour.in ו־savour/savour.ans בתיקיית המתחרה.
מגבלות והנחות
התחומים והמאפיינים של כל נתוני הבדיקה מוצגים בטבלה הבאה:
| מספר הבדיקה | התחום של $n$ | התחום של $a_i$ | הערות |
|---|---|---|---|
| $1$ | $n=100$ | $\lvert a_i\rvert\le10\,000$ | |
| $2$ | $n=200$ | ||
| $3$ | $n=500$ | ||
| $4$ | $n=750$ | ||
| $5$ | $n=1\,000$ | $\lvert a_i\rvert\le1\,000\,000\,000$ | |
| $6$ | |||
| $7$ | $n=2\,000$ | ||
| $8$ | |||
| $9$ | $n=99\,991$ | $\lvert a_i\rvert\le1\,000\,000\,000$ | אין כוסות הדומות ברמה $10$ |
| $10$ | |||
| $11$ | $n=100\,000$ | $\lvert a_i\rvert\le1\,000\,000$ | כל ערכי $a_i$ שווים |
| $12$ | $n=200\,000$ | ||
| $13$ | $n=300\,000$ | ||
| $14$ | |||
| $15$ | $n=100\,000$ | $\lvert a_i\rvert\le1\,000\,000\,000$ | |
| $16$ | |||
| $17$ | $n=200\,000$ | ||
| $18$ | |||
| $19$ | $n=300\,000$ | ||
| $20$ |