Андрианада барлық $0 \le i < n$ үшін $0 \le a_i < 2^b$ болатын $n$ бүтін саннан тұратын әдемі циклдік $a = (a_0, a_1, \dots, a_{n-1})$ массиві болған еді, бірақ, өкінішке орай, ол оны жоғалтып алды! Дегенмен, біз үшін бұл өте сәтті жағдай, өйткені осындай ұмытшақ кейіпкерлер болмаса, әлемде қалпына келтіру есептері әлдеқайда аз болар еді.
Сол уақытта Андриананың досы Бобта пайдалы ақпарат бар: ол Андриананың массивіндегі қатар орналасқан кесінділердің бит бойынша ЖӘНЕ (AND) мәндерін жазып жүрген дәптерін сақтап қалған. Бір күні Бобтың іші пысып, әрбір $i$ позициясы мен белгілі бір тұрақты $k$ ($k \le n$) ұзындығы үшін мына мәнді жазып алды: $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (мұнда массив циклдік болғандықтан, индекстер $n$ модулі бойынша алынады). Бобтың бұл AND мәндерін заңды жолмен алғаны-алмағаны белгісіз.
Андриана Бобтың дәптерінде оның бағалы бастапқы массивін бірмәнді түрде қалпына келтіруге жеткілікті ақпарат болатындай ең үлкен $k$ мәні қандай екенін білгісі келеді.
Кіріс деректері
Кіріс деректерінің бірінші жолында екі бүтін сан $n$ және $b$ берілген, мұндағы $n$ — Андриананың жоғалған массивінің ұзындығы, ал $b$ — $0 \le a_i < 2^b$ шектеуін анықтайтын параметр. Екінші жолда циклдік массивтің элементтерін білдіретін $n$ бүтін сан $a_i$ берілген.
Шығыс деректері
Бір бүтін санды — кесінділердің AND мәндерінен тұратын $x$ массивінен $a$ массивін бірмәнді түрде қалпына келтіруге болатындай ең үлкен $k$ мәнін шығарыңыз.
Шектеулер
$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$.