ל-Andriana היה מערך מעגלי יפהפה $a = (a_0, a_1, \dots, a_{n-1})$ של $n$ מספרים שלמים, שבו $0 \le a_i < 2^b$ עבור כל $0 \le i < n$, אך למרבה הצער היא איבדה אותו! עם זאת, עבורנו זהו מזל גדול, שכן ללא הגיבורים השכחנים הללו, היו בעולם הרבה פחות בעיות שחזור.
בינתיים, לחברה של Andriana, Bob, יש מידע מועיל: הוא שמר מחברת שבה תיעד ערכי AND סיביות (bitwise AND) של מקטעים רצופים מהמערך של Andriana. יום אחד Bob היה משועמם למדי, ולכן הוא רשם, עבור כל מיקום $i$ ועבור אורך קבוע כלשהו $k$ ($k \le n$), את הערך $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (כאשר האינדקסים נלקחים מודולו $n$, מכיוון שהמערך הוא מעגלי). לא ידוע האם Bob השיג את ערכי ה-AND הללו באמצעים חוקיים.
Andriana רוצה לדעת מהו הערך הגדול ביותר של $k$ כך שהמחברת של Bob תכיל מספיק מידע כדי לשחזר באופן יחיד את המערך המקורי היקר שלה?
קלט
השורה הראשונה של הקלט מכילה שני מספרים שלמים $n$ ו-$b$, כאשר $n$ הוא האורך של המערך האבוד של Andriana ו-$b$ הוא הפרמטר המגדיר את האילוץ $0 \le a_i < 2^b$. השורה השנייה מכילה $n$ מספרים שלמים $a_i$ — איברי המערך המעגלי.
פלט
הדפיסו מספר שלם יחיד — הערך הגדול ביותר של $k$ כך שניתן לשחזר את המערך $a$ באופן יחיד מתוך המערך $x$ של ערכי ה-AND של המקטעים.
אילוצים
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
דוגמאות
קלט 1
6 3 7 3 7 7 3 7
פלט 1
2
הערה
במקרה הדוגמה, $n = 6, b = 3$. למערך $a = [7, 3, 7, 7, 3, 7]$ יש ייצוג בינארי $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, תוך שימוש בשלוש סיביות לכל איבר.
עבור $k = 2$, המערך $x$ יהיה $[3, 3, 7, 3, 3, 7]$ (כאשר $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). מהמערך $x$ ומהערך של $b$, נוכל לשחזר את $a$ באופן יחיד.
עבור $k = 3$, המערך $x$ יהיה $[3, 3, 3, 3, 3, 3]$, שאינו קובע את $a$ באופן יחיד (לדוגמה, $[3, 3, 7, 3, 7, 7]$ ייתן את אותו $x$).
לכן, עבור דוגמה זו, התשובה היא $k = 2$.