Bessie עוזרת ל-Elsie להתכונן למבחן אוצר מילים. המילים נבחרות ממאגר של $M$ מילים שונות, שאף אחת אינה קידומת של מילה אחרת במאגר.

כל עוד המאגר אינו ריק, Bessie בוחרת מילה, מסירה אותה וקוראת אותה תו אחר תו משמאל לימין. Elsie מודיעה ברגע שהיא יכולה לזהות אותה חד-משמעית, ואז Bessie מפסיקה.

סדר הקריאה כבר נקבע ל-$w_1,w_2,\dots,w_M$. אם Elsie עונה מהר ככל האפשר, כמה תווים מכל מילה Bessie תקרא?

המילים נתונות בפורמט דחוס. תחילה מגדירים $N+1$ ($1\le N\le 10^6$) מילים שונות; המאגר כולל את כל אלה שאינן קידומת של מילה אחרת. ההגדרה היא:

• בתחילה, המילה ה-$0$ היא מחרוזת ריקה.
• לכל $1\le i\le N$, המילה ה-$i$ היא המילה ה-$p_i$ בתוספת תו אחד בסוף ($0\le p_i<i$). התווים נבחרים כך שכל $N+1$ המילים שונות.

קלט

השורה הראשונה מכילה $N$, כאשר $N+1$ הוא מספר המילים הדחוסות.

הבאה מכילה $p_1,p_2,\dots,p_N$; $p_i$ מציין שהמילה ה-$i$ נוצרת בהוספת תו בסוף המילה ה-$p_i$.

נסמן ב-$M$ את מספר המילים שאינן קידומת של אחרת. $M$ השורות הבאות מכילות $w_1,w_2,\dots,w_M$: המילה ה-$w_i$ היא ה-$i$ בסדר הקריאה. מובטח שהסדר הוא תמורה של מילות המאגר.

פלט

הדפיסו $M$ שורות; השורה ה-$i$ מכילה את מספר התווים הנקראים מהמילה ה-$i$ בסדר הקריאה.

דוגמאות

קלט 1

5
0 1 2 3 4
5

פלט 1

0

הערה

יש $6$ מילים המסומנות $0\dots 5$. רק $5$ אינה קידומת של אחרת, ולכן היא היחידה במאגר. כשנשארת מילה אחת, Elsie אינה צריכה אף תו כדי לזהותה.

קלט 2

4
0 0 1 1
4
3
2

פלט 2

2
1
0

הערה

המאגר כולל את המילים $2$, $3$ ו-$4$.

Elsie צריכה שני תווים לזהות את $4$, כי ל-$3$ ול-$4$ אותו תו ראשון.

כש-Bessie קוראת את התו הראשון של $3$, Elsie כבר מזהה אותה, כי $4$ נקראה קודם.

קלט 3

4
0 0 1 1
2
3
4

פלט 3

1
2
0

תתי-משימות

• הקלטים הרביעי עד החמישי: אין מילה שאורכה גדול מ-$20$.
• הקלטים השישי עד העשירי: סכום אורכי מילות המאגר אינו עולה על $10^7$.
• הקלטים האחד עשר עד השמונה עשר: אין מגבלות נוספות.

מחבר הבעיה: Benjamin Qi