Description

The enemy’s senior generals share many similarities. To more easily find each general’s weakness, our intelligence department has identified their differences and summarized them into $k$ types of traits. For example, trait $1$ means a general likes to fight, trait $2$ means a general likes to eat, and so on.

For storage, we use a trait value to describe a general’s characteristics. The trait value is a binary integer with $k$ bits, where each bit can represent one trait of a general. $1$ means the general has this trait, and $0$ means not.

Our spy has learned that soon $n$ enemy generals will hold a banquet, and they will enter in a single file. If among some consecutive $m$ people, the number of occurrences of each trait are all the same, then our spy can easily assassinate these $m$ people. You need to help determine the maximum number $m$ that the spy can assassinate.

Because the spy may be killed right after starting the attack, the spy can attack only once.

Input Format

The first line contains two integers $n$, $k$.

The second line contains $n$ integers, where the $i$-th number $a_i$ represents the $i$-th general’s trait value (given in decimal form).

Output Format

Output the maximum number of enemy generals that can be assassinated.

7 3
7 6 7 2 1 4 2

4

Hint

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

Translated by ChatGPT 5