רקע

״ילד טוב, אילו הייתי נותן לך עושר לשלושה גלגולי חיים, האם היית לומד?״

היום הגיעו 玛德琳 ו־坏德琳 אל מכונה מופלאה. בתוך המכונה יש כדורים בארבעה צבעים, ולכל צבע תפקיד משלו. הכדור הכחול הוא הכדור הבסיסי ביותר: כשקופצים עליו, מקבלים יכולת לבצע זינוק אחד. הכדור הוורוד הוא גרסה משופרת: כשקופצים עליו, מקבלים שני זינוקים. קפיצה על כדור לבן אינה מעניקה זינוקים. לאחר שקופצים פעם אחת על כדור צהוב, צומחים עליו קוצים, ולא ניתן עוד לגעת בו.

אפשר לתאר את השלבים שבמכונה באמצעות סדרת צבעים. 玛德琳 ו־坏德琳 שיחקו בה זמן רב, אך עדיין לא עברו את השלב הראשון. מרוב תסכול, 玛德琳 פרצה בבכי! היא החליטה לרמות בעזרת כלי לשינוי המשחק! הכלי הזה מיוחד מאוד: הוא יכול לשנות רק כדורים לבנים וצהובים, ורק לכדורים כחולים וורודים; כמו כן, בכל שינוי, מיקומו של הכדור שמשתנה קבוע מראש. כש־坏德琳 גילתה זאת, היא החליטה למנוע מ־玛德琳 לרמות, ולכן פרצה לכלי וקיבלה הרשאה לשנות את צבע הכדורים הצהובים. נוסף על כך, 玛德琳 סבורה שרצף של כדורים זהים הופך את השלב לקל יותר. היא מגדירה את מידת הקלות של שלב כאורך המרבי של קטע בצבע אחיד. 玛德琳 רוצה למקסם את הערך הזה, ואילו 坏德琳 רוצה למזער אותו.

תיאור הבעיה

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$; מציבים באיבר ה־$x$ בסדרה את הערך $A_i$ (ייתכן שקרן קוסמית פגעה במיקום ה־$x$, כך ש־$a_x,A_i \in \{0,1\}$ ובכל זאת $a_x \neq A_i$). לכל $i=0,1,\dots,n$, מצאו את האורך $ans_i$ של הקטע הרציף הארוך ביותר בצבע אחיד בסדרה הסופית, אם עד המועד ה־$i$ ועד בכלל פועלים לפי ההחלטות שבסדרה $A$, ולאחר תום המועד ה־$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$, המספר המתאים מציין את אורך הקטע הרציף הארוך ביותר בצבע אחיד בסדרה הסופית, אם עד המועד ה־$i$ ועד בכלל פועלים לפי ההחלטות שבסדרה $A$, ולאחר תום המועד ה־$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 קובע את ערך האיבר ה־$2$ ל־$0$, Alice יכולה לקבוע גם את ערכי האיברים ה־$1$ וה־$3$ ל־$0$, כך שהסדרה הסופית היא 0 0 0, ואורך הקטע הארוך ביותר בצבע אחיד הוא $3$. אם Bob קובע את ערך האיבר ה־$2$ ל־$1$, 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$.