F. Lights for the SanSiCup
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Every Christmas, while decorating the hall, the kids of ICPC UMSS organize the SanSiCup. On a wall there is a panel with $$$b$$$ lights, numbered from $$$0$$$ to $$$b-1$$$, and $$$N$$$ remote controls. At the beginning all lights are off.

Each control $$$i$$$ has an associated fixed mask $$$a_i$$$: when pressed, it toggles exactly the lights $$$j$$$ such that bit $$$j$$$ of $$$a_i$$$ is one (lights that are off turn on and lights that are on turn off). The controls can be pressed in any order and as many times as desired; pressing the same control twice cancels its effect. Consequently, a configuration of lights (the subset of lights that are on) is reachable if and only if it is equal to the bitwise XOR of the masks of some subset of the original controls (the empty subset produces the configuration with all lights off).

Since the controls often get lost among the decorations, the kids want to build some additional backup controls. The effect of each new control is chosen before any loss happens, is fixed at that moment and cannot be changed afterwards; that effect must be equal to the XOR of the masks of some subset of the original controls (not of other new controls). A new control with mask $$$0$$$ is valid, although useless.

Then, up to two arbitrary controls —original or new, in any combination— may be lost. Two different controls are always considered physical and separate even if they have exactly the same mask: losing one of them does not affect the other. Once the new controls are built and the identity of the lost controls is known, the kids can freely choose, for each configuration they want to reproduce, which remaining controls to press (different subsets for different configurations are allowed).

The kids want that, no matter which up to two controls are lost, every configuration that was reachable with the $$$N$$$ original controls (without losses and without new controls) remains reachable using only the controls that survived. What is the minimum number of additional controls they need to build to guarantee this?

Input

The first line contains two integers $$$N$$$ and $$$b$$$ ($$$1 \leq N \leq 100000$$$, $$$1 \leq b \leq 60$$$): the number of original controls and the number of lights on the panel.

The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \leq a_i \lt 2^b$$$), the masks of the original controls, in decimal. The lights are numbered from $$$0$$$ to $$$b-1$$$: control $$$i$$$ toggles light $$$j$$$ if and only if bit $$$j$$$ of $$$a_i$$$ is one.

Several original controls may have exactly the same mask (including mask $$$0$$$, a control that does not change any light); each one counts as an independent physical unit that can be lost separately.

Output

Print a single integer: the minimum number of additional controls the kids must build.

Examples
Input
5 3
4 2 1 6 5
Output
1
Input
3 3
4 2 1
Output
3
Input
3 1
1 1 1
Output
0
Note

Remember that:

  • The effect of each new control is fixed before it is known which controls will be lost, and it must be expressible as the XOR of masks of original controls (never of other new controls).
  • "Losing up to two controls" includes losing zero, one or two controls, in any combination of original and new ones.
  • Two controls with the same mask are still distinct units: losing one does not imply losing the other.

Explanation for example 1

It is enough to build one additional control with mask $$$3$$$ (equivalent to pressing the controls with masks $$$2$$$ and $$$1$$$). With the six available controls, every configuration reachable with the five original ones remains reachable even if any two of them are lost.

For example, if the controls with masks $$$4$$$ and $$$2$$$ are lost, the effect of the first one can be reconstructed by pressing those with masks $$$5$$$ and $$$1$$$, and the effect of the second one by pressing those with masks $$$3$$$ and $$$1$$$.

Without building any additional control, losing the controls with masks $$$2$$$ and $$$6$$$ already makes it impossible to obtain configuration $$$2$$$.

Explanation for example 2

The three original controls are linearly independent (they form a basis) and none of them has a backup: losing any one of them already makes it impossible to reproduce its effect. An optimal choice is to build the controls with masks $$$6$$$, $$$5$$$ and $$$3$$$.

Explanation for example 3

Even if two of the three controls are lost, there is always one left that can turn the only light on or off. There is no need to build any additional control.