Byteotia Town Walk

In Byteotia, town names are unique sequences of exactly \(n\) bits. Out of the \(2^n\) possible bit strings, exactly \(k\) strings do not correspond to any town, so there are \(2^n-k\) towns in total.

Two towns are connected directly by a road if and only if their names differ in exactly one bit. The roads do not cross outside of towns.

Byteasar wishes to take a stroll from town x to town y using the available roads. Your task is to determine whether such a walk is possible in the resulting subgraph of the \(n\)-dimensional hypercube, after \(k\) bit strings (towns) have been removed.

Input and constraints:

• All bit strings are of length \(n\).
• The first line of input contains two integers: \(n\) and \(k\).
• The second line contains the bit string corresponding to town x.
• The third line contains the bit string corresponding to town y.
• The next \(k\) lines each contain a bit string that has been removed (i.e. does not represent a town).
• If either x or y is among the removed strings, then the answer is NO.

Output:

Output YES if there is a path from x to y using the roads. Otherwise, output NO.

inputFormat

The input is given as follows:

n k
x
 y
removed_1
removed_2
... 
removed_k

Where:

• n is the length of each bit string.
• k is the number of removed bit strings.
• x is the starting town's bit string.
• y is the destination town's bit string.
• Each of the next k lines contains a bit string that does not represent a town.

outputFormat

Output a single line containing either YES if town y is reachable from town x using the roads, or NO otherwise.

sample

3 1
000
111
010

YES