Codeforces Round 267 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

brute force

constructive algorithms

implementation

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Fedor and New Game

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3».

The game has (*m* + 1) players and *n* types of soldiers in total. Players «Call of Soldiers 3» are numbered form 1 to (*m* + 1). Types of soldiers are numbered from 0 to *n* - 1. Each player has an army. Army of the *i*-th player can be described by non-negative integer *x*_{i}. Consider binary representation of *x*_{i}: if the *j*-th bit of number *x*_{i} equal to one, then the army of the *i*-th player has soldiers of the *j*-th type.

Fedor is the (*m* + 1)-th player of the game. He assume that two players can become friends if their armies differ in at most *k* types of soldiers (in other words, binary representations of the corresponding numbers differ in at most *k* bits). Help Fedor and count how many players can become his friends.

Input

The first line contains three integers *n*, *m*, *k* (1 ≤ *k* ≤ *n* ≤ 20; 1 ≤ *m* ≤ 1000).

The *i*-th of the next (*m* + 1) lines contains a single integer *x*_{i} (1 ≤ *x*_{i} ≤ 2^{n} - 1), that describes the *i*-th player's army. We remind you that Fedor is the (*m* + 1)-th player.

Output

Print a single integer — the number of Fedor's potential friends.

Examples

Input

7 3 1

8

5

111

17

Output

0

Input

3 3 3

1

2

3

4

Output

3

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2023 21:05:34 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|