Bessie hilft Elsie beim bevorstehenden Vokabeltest. Die Wörter stammen aus einem Vorrat von $M$ verschiedenen Wörtern, von denen keines Präfix eines anderen Vorratswortes ist.

Solange der Vorrat nicht leer ist, wählt Bessie ein Wort, entfernt es und liest es von links nach rechts Zeichen für Zeichen. Elsie meldet sich, sobald sie es eindeutig erkennt; dann hört Bessie auf.

Die Reihenfolge ist bereits $w_1,w_2,\dots,w_M$. Wenn Elsie so schnell wie möglich antwortet, wie viele Zeichen jedes Wortes liest Bessie?

Die Wörter sind komprimiert gegeben. Zunächst definieren wir $N+1$ ($1\le N\le 10^6$) verschiedene Wörter; der Vorrat umfasst alle, die kein Präfix eines anderen Wortes sind. Die Definition lautet:

• Anfangs ist Wort $0$ die leere Zeichenfolge.
• Für jedes $1\le i\le N$ entsteht Wort $i$ aus Wort $p_i$ durch Anhängen eines Zeichens ($0\le p_i<i$). Die Zeichen sind so gewählt, dass alle $N+1$ Wörter verschieden sind.

Eingabe

Die erste Zeile enthält $N$, wobei $N+1$ die Anzahl komprimiert gegebener Wörter ist.

Die nächste enthält $p_1,p_2,\dots,p_N$; $p_i$ besagt, dass Wort $i$ durch Anhängen eines Zeichens an Wort $p_i$ entsteht.

Sei $M$ die Anzahl der Wörter, die kein Präfix anderer Wörter sind. Die nächsten $M$ Zeilen enthalten $w_1,w_2,\dots,w_M$; Wort $w_i$ wird als $i$-tes gelesen. Die Lesereihenfolge bildet garantiert eine Permutation der Vorratswörter.

Ausgabe

Gib $M$ Zeilen aus; Zeile $i$ enthält die Anzahl gelesener Zeichen des $i$-ten Wortes in Lesereihenfolge.

Beispiele

Eingabe 1

5
0 1 2 3 4
5

Ausgabe 1

0

Hinweis

Es gibt $6$ Wörter mit Nummern $0\dots 5$. Nur Wort $5$ ist kein Präfix eines anderen und daher allein im Vorrat. Bleibt nur ein Wort, braucht Elsie grundsätzlich kein Zeichen, um es zu erkennen.

Eingabe 2

4
0 0 1 1
4
3
2

Ausgabe 2

2
1
0

Hinweis

Der Vorrat enthält Wörter $2$, $3$ und $4$.

Für Wort $4$ braucht Elsie zwei Zeichen, da $3$ und $4$ mit demselben Zeichen beginnen.

Sobald Bessie das erste Zeichen von $3$ liest, erkennt Elsie es eindeutig, weil $4$ schon gelesen wurde.

Eingabe 3

4
0 0 1 1
2
3
4

Ausgabe 3

1
2
0

Teilaufgaben

• Eingaben vier bis fünf: Kein Wort ist länger als $20$.
• Eingaben sechs bis zehn: Die Gesamtlänge der Vorratswörter beträgt höchstens $10^7$.
• Eingaben elf bis achtzehn: keine zusätzlichen Beschränkungen.

Aufgabenautor: Benjamin Qi