خلفية المسألة

«يا بنيّ الطيب، لو مُنحت ثروة تكفي ثلاث حيوات، أكنت ستدرس؟»

اليوم، وصلت 玛德琳 و坏德琳 إلى آلة خيالية. داخل الآلة كرات بأربعة ألوان، لكل منها استخدام مختلف. الكرة الزرقاء هي أبسط الكرات النطاطة؛ عندما ترتد عليها، تكتسب القدرة على الاندفاع مرة واحدة. الكرة الوردية نسخة محسّنة؛ عندما ترتد عليها، تكتسب اندفاعتين. أما الارتداد على الكرة البيضاء فلا يمنحك أي اندفاع. وبعد الارتداد على الكرة الصفراء مرة واحدة، تنمو عليها أشواك، ولا يمكنك لمسها بعد ذلك.

يمكن وصف المراحل الموجودة داخل الآلة بمتتالية من الألوان. لعبت 玛德琳 و坏德琳 فيها وقتًا طويلًا، لكنهما لم تتجاوزا المرحلة الأولى بعد. فأجهشت 玛德琳 بالبكاء من شدة القلق! وقررت الغش باستخدام أداة تعديل! هذه الأداة مميزة للغاية: لا تستطيع تعديل سوى الكرات البيضاء والصفراء، ولا تستطيع تحويلها إلا إلى كرات زرقاء أو وردية، كما أن موضع الكرة التي تُعدّل في كل مرة محدد مسبقًا. وعندما علمت 坏德琳 بذلك، قررت منع 玛德琳 من الغش، فاخترقت أداة التعديل وحصلت على صلاحية تغيير ألوان الكرات الصفراء. كذلك، ترى 玛德琳 أن سلسلة من الكرات المتطابقة تجعل المرحلة أسهل. وتعتبر أن سهولة المرحلة هي أكبر طول لمقطع من لون واحد. تريد 玛德琳 تعظيم هذه القيمة، بينما تريد 坏德琳 تصغيرها.

وصف المسألة

تلعب Alice وBob لعبة على متتالية طولها $n$. لا يمكن أن تكون قيمة أي عنصر في المتتالية إلا $0$ أو $1$، ويُحدد الوقت الذي تُسند فيه قيمة كل عنصر قبل بدء اللعبة.

تُعطى متتاليتين $p$ و$a$ طول كل منهما $n$، حيث $p$ تبديل للأعداد $1\dots n$، و$a_i\in\{-2,-1,0,1\}$.

تُحدد قيمة العنصر رقم $i$ في المتتالية في اللحظة رقم $p_i$، وفق القواعد التالية:

• إذا كان $a_i=0$، تُسند إلى هذا العنصر القيمة $0$؛
• إذا كان $a_i=1$، تُسند إلى هذا العنصر القيمة $1$؛
• إذا كان $a_i=-1$، تختار Alice قيمة هذا العنصر في تلك اللحظة؛
• إذا كان $a_i=-2$، يختار Bob قيمة هذا العنصر في تلك اللحظة.

تعرف Alice وBob المتتاليتين $p$ و$a$ قبل بدء اللعبة. تستمر اللعبة $n$ لحظات؛ في اللحظة رقم $k$، تُحدد قيمة الموضع $i$ الذي يحقق $p_i=k$. وبعد انتهاء اللحظات الـ $n$، تكون قيمة كل عنصر في المتتالية قد حُددت مرة واحدة بالضبط.

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

تريد Alice تعظيم أكبر طول بين جميع المقاطع المتصلة ذات اللون الواحد غير القابلة للتمديد في المتتالية بعد اللحظة رقم $n$، بينما يريد Bob تصغير هذه القيمة.

تُعطى عددًا صحيحًا موجبًا $typ \in \{1,2\}$.

إذا كان $typ=1$، يتبع الطرفان استراتيجية مثلى. أوجد أكبر طول بين المقاطع المتصلة ذات اللون الواحد غير القابلة للتمديد في المتتالية النهائية. يمكن إثبات أن الإجابة محددة بشكل وحيد.

إذا كان $typ=2$، تُعطى أيضًا متتالية $A$ طولها $n$. تحقق $A_i \in \{0,1\}$، وتمثل القرار المتخذ في اللحظة رقم $i$ من اللعبة كما يلي: ليكن $x$ العدد الصحيح الموجب الوحيد من بين $1,2,\dots,n$ الذي يحقق $p_x=i$؛ تُسند القيمة $A_i$ إلى العنصر رقم $x$ في المتتالية (قد تصيب أشعة كونية الموضع رقم $x$، فتحدث حالة يكون فيها $a_x,A_i \in \{0,1\}$ و$a_x \neq A_i$). أوجد، لكل $i=0,1,\dots,n$، طول أطول مقطع متصل ذي لون واحد في المتتالية النهائية، $ans_i$، إذا اتُّبعت قرارات المتتالية $A$ حتى اللحظة رقم $i$ بما فيها تلك اللحظة، ثم اتبع الطرفان استراتيجية مثلى بعد انتهاء اللحظة رقم $i$.

الإدخال

يجب حل هذه المسألة بطريقة آنية.

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

تليه $T$ حالات اختبار. في كل حالة اختبار:

يحتوي السطر الأول على عددين صحيحين موجبين $n$ و$typ$.

يحتوي السطر الثاني على $n$ أعداد صحيحة $p_1,p_2,\dots,p_n$.

يحتوي السطر الثالث على $n$ أعداد صحيحة $a_1,a_2,\dots,a_n$.

إذا كان $typ=2$، يحتوي السطر الرابع على $n$ أعداد صحيحة $A'_1,A'_2,\dots,A'_n$.

القيمة الحقيقية لـ $A_i$ هي باقي قسمة ناتج عملية XOR على مستوى البتات بين $A'_i$ و$ans_{i-1}$ على $2$.

الإخراج

لكل حالة اختبار:

إذا كان $typ=1$، اطبع سطرًا يحتوي على عدد صحيح واحد يمثل طول أطول مقطع متصل ذي لون واحد في المتتالية النهائية عندما يتبع الطرفان استراتيجية مثلى.

إذا كان $typ=2$، اطبع سطرًا يحتوي على $n+1$ أعداد صحيحة تمثل، لكل $i=0,1,\dots,n$، طول أطول مقطع متصل ذي لون واحد في المتتالية النهائية إذا اتُّبعت قرارات المتتالية $A$ حتى اللحظة رقم $i$ بما فيها تلك اللحظة، ثم اتبع الطرفان استراتيجية مثلى بعد انتهاء اللحظة رقم $i$.

أمثلة

الإدخال 1

1
3 1
3 1 2
-1 -2 -1

الإخراج 1

3

ملاحظة

تعني $p=[3,1,2]$ أن $p_1=3,\ p_2=1,\ p_3=2$: تُحدد قيمة العنصر رقم $1$ في اللحظة رقم $3$، وقيمة العنصر رقم $2$ في اللحظة رقم $1$، وقيمة العنصر رقم $3$ في اللحظة رقم $2$. إذن، يكون الترتيب الزمني كما يلي:

• اللحظة $1$: تُحدد قيمة العنصر رقم $2$ ($a_2=-2$، ويختارها Bob)؛
• اللحظة $2$: تُحدد قيمة العنصر رقم $3$ ($a_3=-1$، وتختارها Alice)؛
• اللحظة $3$: تُحدد قيمة العنصر رقم $1$ ($a_1=-1$، وتختارها Alice).

تريد Alice أن يكون أطول مقطع ذي لون واحد أطول ما يمكن، بينما يريد Bob أن يكون أقصر ما يمكن. رغم أن Bob يلعب أولًا، فهو يتحكم فقط في العنصر رقم $2$ الموجود في الوسط؛ أما Alice فتتحكم في العنصرين الطرفيين رقمي $1$ و$3$.

بعد أن يختار Bob القيمة $0$ للعنصر رقم $2$، تستطيع Alice اختيار القيمة $0$ أيضًا لكل من العنصرين رقمي $1$ و$3$، فتكون المتتالية النهائية 0 0 0، ويكون طول أطول مقطع ذي لون واحد $3$. وإذا اختار Bob القيمة $1$ للعنصر رقم $2$، تختار Alice كذلك القيمة $1$ لكليهما، فتكون المتتالية النهائية 1 1 1، ويظل طول أطول مقطع ذي لون واحد $3$.

يؤدي خيارا Bob إلى النتيجة نفسها تمامًا، فلا يستطيع خفض الإجابة إلى أقل من $3$؛ كما أن أقصى ما تستطيع Alice تحقيقه هو جعل المتتالية كلها ذات لون واحد، لذا فالإجابة هي $3$.

الإدخال 2

1
2 1
2 1
-1 -1

الإخراج 2

2

ملاحظة

تعني $p=[2,1]$ أن $p_1=2,\ p_2=1$: تُحدد قيمة العنصر رقم $1$ في اللحظة رقم $2$، وقيمة العنصر رقم $2$ في اللحظة رقم $1$. قيمة $a$ لكلا العنصرين هي $-1$، لذا تختار Alice قيمتيهما:

• اللحظة $1$: تُحدد قيمة العنصر رقم $2$ ($a_2=-1$، وتختارها Alice)؛
• اللحظة $2$: تُحدد قيمة العنصر رقم $1$ ($a_1=-1$، وتختارها Alice).

تريد Alice تعظيم طول أطول مقطع ذي لون واحد. بما أنها تختار قيمتي العنصرين، يكفي أن تسند إليهما القيمة نفسها لتحصل على 0 0 أو 1 1، وعندئذ يكون $(1,2)$ مقطعًا متصلًا ذا لون واحد غير قابل للتمديد وطوله $2$. وبما أن طول المتتالية الكلي هو $2$ فقط، فهذه أيضًا أفضل نتيجة تستطيع تحقيقها.

الإدخال 3

3
2 1
1 2
-1 -2
4 2
1 3 2 4
-1 0 -2 -1
1 0 0 1
3 1
3 1 2
0 0 1

الإخراج 3

1
2 2 3 2 2
2

القيود

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

في جميع حالات الاختبار، يُضمن ما يلي:

• $1 \leq T \leq 2 \times 10^5$, $1\le n\le 2\times 10^5$, $1 \le typ \le 2$, $1 \leq \sum n \leq 2 \times 10^5$.

• $p$ تبديل للأعداد $1\dots n$.

• $a_i\in\{-2,-1,0,1\}$.

• $A_i\in\{0,1\}$.

الخاصية الخاصة A: يُضمن أن $a_i\in\{0,1\}$.

الخاصية الخاصة B: يُضمن توليد $p$ و$a$ عشوائيًا من بين المتتاليات ذات الطول $n$ التي تحقق القيود.

تنبيه: تعتمد المهام الفرعية $3,4,5,8,9$ على المهمة الفرعية $2$.