تساعد Bessie زميلتها Elsie في اختبار المفردات القادم. الكلمات من بنك فيه $M$ كلمة مختلفة، ولا توجد كلمة فيه بادئة لكلمة أخرى منه.

ما دام البنك غير فارغ، تختار Bessie كلمة وتحذفها وتقرأها محرفًا محرفًا من اليسار إلى اليمين. تخبرها Elsie بمجرد أن تستطيع تحديدها بشكل فريد، فتتوقف Bessie عن القراءة.

حددت Bessie الترتيب $w_1,w_2,\dots,w_M$. إذا أجابت Elsie بأسرع ما يمكن، فكم محرفًا ستقرأ من كل كلمة؟

تُعطى الكلمات بصيغة مضغوطة. نعرف أولًا $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$ على عدد المحارف التي تقرؤها Bessie من الكلمة $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$ تشتركان بالمحرف الأول.

بمجرد قراءة أول محرف من $3$ تستطيع Elsie تحديدها، لأن $4$ قُرئت بالفعل.

الإدخال 3

4
0 0 1 1
2
3
4

الإخراج 3

1
2
0

المهام الفرعية

• الإدخالات من الرابع إلى الخامس: لا كلمة أطول من $20$.
• الإدخالات من السادس إلى العاشر: مجموع أطوال كلمات البنك لا يتجاوز $10^7$.
• الإدخالات من الحادي عشر إلى الثامن عشر: لا قيود إضافية.

مؤلف المسألة: Benjamin Qi