We’re preparing your current view and syncing the latest data.
Fedor is playing a new game. There are n players including Fedor, each with an army described by an integer. Two armies are considered similar if the number of differing bits in their binary representation is at most k. Given Fedor's army and the armies of the other players, determine how many players have similar armies to Fedor.
The first line contains three integers n, m, and k, where n is the number of players excluding Fedor, m is the number of bits describing each army, and k is the maximum allowed differing bits. The next n lines each contain one integer ai representing each player's army. The last line contains one integer representing Fedor's army.
Print the number of players whose armies differ from Fedor's army in at most k bits.
1 ≤ n, m ≤ 10^3, 0 ≤ k ≤ m, 0 ≤ ai < 2^m