دعني أسمع صوتك، وأخبرني بقصص رحلتك—

سواء كانت أحداثًا سعيدة أم مؤلمة، وكذلك تلك اللقاءات المحفورة في القلب.

Far Away Song - anemoi

وصف المسألة

تُعطى سلسلة نصية طولها $n$ وتُسمّى $S$، وتبدأ فهارسها من $1$. نرمز بـ $S(i, j)=S_iS_{i+1}\cdots S_j$ إلى السلسلة الجزئية من $S$ التي تتكوّن من المحارف من المحرف رقم $i$ إلى المحرف رقم $j$.

إذا كانت السلسلة النصية غير الفارغة $B$ بادئةً ولاحقةً للسلسلة النصية $X$ في آن واحد، وكان $|B|<|X|$، فإننا نسمّي $B$ حدًّا للسلسلة $X$، حيث يدلّ $|X|$ على طول السلسلة النصية $X$.

في البداية، تكون عند السلسلة الجزئية $S(1, n)$. تُنفّذ كل قفزة على النحو الآتي:

1. اختر سلسلة جزئية $X$ داخل السلسلة الجزئية التي تكون عندها حاليًّا.
2. اختر حدًّا $B$ للسلسلة $X$، بشرط أن يكون $2|B|\ge |X|$.
3. اقفز إلى السلسلة الجزئية المقابلة لـ $B$ بوصفها بادئةً أو لاحقةً لـ $X$، ولك أن تختار أيًّا منهما.

على سبيل المثال، عندما تكون $S$ هي aabaaba وتكون عند $S(1, 7)$، يمكنك اختيار $X=S(2, 7)=$ abaaba. طول حدّها aba يساوي نصف $|X|$ تمامًا، لذا يمكنك القفز إلى $S(2, 4)$ أو $S(5, 7)$.

لكل $1\le i\le n$، أوجد على حدة أكبر عدد من القفزات التي يمكن إجراؤها انطلاقًا من $S(1, n)$ وصولًا في النهاية إلى $S(i, i)$. إذا تعذّر الوصول، فالإجابة هي $-1$. ويُسمح بعدم إجراء أي قفزة.

توجد عدة حالات اختبار.

الإدخال

يحتوي السطر الأول على عدد صحيح $T$، يمثّل عدد حالات الاختبار.

بعد ذلك تُعطى حالات الاختبار تباعًا. لكل حالة اختبار، يُعطى سطر واحد يمثّل السلسلة النصية $S$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على $n$ أعداد صحيحة، يمثّل العدد رقم $i$ الإجابة الخاصة بـ $S(i, i)$ (إذا تعذّر الوصول إلى $S(i, i)$، فاطبع -1).

أمثلة

الإدخال 1

5
abbababbab
bbabbaabbabbaaabab
babbaaaaabaabaaabaaba
baabaabaabaacaabaabaabaacaabaabaabaac
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba

الإخراج 1

-1 2 2 -1 -1 -1 2 2 -1 -1
3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1
-1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1
-1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1
1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1

ملاحظة

في حالة الاختبار الأولى، $S=$ abbababbab، وبادئتها ولاحقتها ذواتا الطول $5$ هما abbab. يمكن إجراء قفزتين كما يأتي:

• اقفز أولًا إلى $S(1, 5)$، ثم اختر $S(2, 3)=$ bb، واقفز إلى $S(2, 2)$ أو $S(3, 3)$.
• اقفز أولًا إلى $S(6, 10)$، ثم اختر $S(7, 8)=$ bb، واقفز إلى $S(7, 7)$ أو $S(8, 8)$.

لا يمكنك مواصلة القفز إلا إذا كانت القفزة الأولى إلى إحدى نسختي abbab المذكورتين، ولا يمكن للقفزة التالية أن تصل إلا إلى محرف منفرد. لذلك، فإن أكبر عدد من القفزات لكل واحد من هذه المواضع الأربعة هو $2$.

لا يمكن الوصول إلى أيّ من المواضع الأخرى بالقفز، لذا تكون الإجابة لها $-1$.

أمثلة 2

انظر الملفين wind2.in وwind2.ans في المرفقات. يحقّق هذا المثال قيود المهمة الفرعية 3.

أمثلة 3

انظر الملفين wind3.in وwind3.ans في المرفقات. يحقّق هذا المثال قيود المهمة الفرعية 5.

أمثلة 4

انظر الملفين wind4.in وwind4.ans في المرفقات. يحقّق هذا المثال قيود المهمة الفرعية 6.

أمثلة 5

انظر الملفين wind5.in وwind5.ans في المرفقات. يحقّق هذا المثال قيود المهمة الفرعية 8.

القيود

تُطبَّق في هذه المسألة تبعيات مناسبة بين المهام الفرعية.

الخاصية الخاصة A: توجد سلسلة نصية غير فارغة $P$، بحيث تكون $S$ بادئةً للسلسلة الدورية اللانهائية $P^{\infty}$، ويكون $|P|\le 10$.

الخاصية الخاصة B: تُولَّد $S$ عشوائيًّا، أي إن كل محرف في $S$ يُختار عشوائيًّا بتوزيع منتظم من مجموعة محارف حجمها $\ge 2$.

الخاصية الخاصة C: لكل $1\le i<n$، يتحقّق $S_i\neq S_{i+1}$.

في جميع البيانات، يُضمن أن $1\le n\le 2\times 10^5$، وأن مجموع أطوال السلاسل النصية لجميع حالات الاختبار ضمن ملف اختبار واحد هو $\sum n\le 2\times 10^5$. تحتوي السلسلة النصية $S$ على أحرف إنجليزية صغيرة فقط.