كان لدى Andriana مصفوفة دورية جميلة $a = (a_0, a_1, \dots, a_{n-1})$ مكونة من $n$ من الأعداد الصحيحة، حيث $0 \le a_i < 2^b$ لكل $0 \le i < n$، ولكنها للأسف فقدتها! ومع ذلك، بالنسبة لنا، هذا أمر محظوظ للغاية، فبدون هؤلاء الأبطال كثيري النسيان، لكان في العالم عدد أقل بكثير من مسائل إعادة البناء.
في هذه الأثناء، يمتلك Bob صديق Andriana بعض المعلومات المفيدة: فقد احتفظ بدفتر ملاحظات سجل فيه قيم عملية 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$.