The Best Problem of 2021

Time limit2sMemory limit1024 MB

Summary

Given a set B of n binary strings of length m and a binary number X, the task is to find an answer from B and X, though the output format is not stated.

Level: Medium7 of 10
Topics: Bit manipulation, Matrix, Math
Solved: No attempts yet

Problem

The year is 2021. People still care about COVID, NNSU just won ICPC 2020, and he is already crazy, we just don't know yet how much. We are looking for problems for the SnackDown finals, and 7dan suggested this one. For some reason, we decided not to use it then, but internally it became known as The Best Problem of 2021.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 2000$ ): the size of $B$ and the length of the binary numbers. All elements of $B$ and the number $X$ are given in binary with exactly $m$ digits (leading zeroes are allowed).

Each of the next $n$ lines contains a binary string of length $m$ that represents an element of $B$ .

The last line contains a binary string of length $m$ that represents the number $X$ .

Output

You'll figure it out.

Examples4

Example 1
Input
```
4 4
0001
0010
0100
1000
1101
```
Expected output
```
7364
```
Example 2
Input
```
3 2
00
00
00
11
```
Expected output
```
0
```
Example 3
Input
```
2 3
110
101
101
```
Expected output
```
1
```

Example 4

Input

Expected output