Description

Immortal $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ has strong abilities in many aspects. Specifically, she has a total of $m$ abilities, numbered $1 \sim m$.

Her abilities improve day by day. Each day, some abilities increase once. She records each day’s improvements with a single integer, called the ability upgrade number. For example, the number $13$ in binary is $1101$, and read from right to left, it indicates that abilities numbered $1, 3, 4$ each increased once that day.

$\mathsf E \color{red} \mathsf{ntropyIncreaser}$ writes down the ability upgrade number for every day. If over a consecutive period each of her abilities increases the same number of times, she calls that period a balanced period. For example, if over $5$ consecutive days each ability increases $4$ times, then it is a balanced period of length $5$.

Given the ability upgrade numbers for $n$ days, find the maximum length of a balanced period.

Input Format

The first line contains two integers $n, m$, meaning there are $n$ days and $m$ abilities.

The next $n$ lines each contain one integer, representing the ability upgrade number for days $1 \sim n$.

After converting an ability upgrade number to binary, from right to left, each bit indicates whether the corresponding ability increased once that day.

Output Format

Output a single integer, the maximum length of a balanced period.

7 3
7
6
7
2
1
4
2

4

Hint

Constraints

• For $50\%$ of the testdata, $1 \le n \le 1000$.
• For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 30$.

Sample Explanation

The abilities improved each day are as follows:

Days $3$ through $6$ form the longest balanced period because, in those four days, each ability increased exactly $2$ times.

Translated by ChatGPT 5