Binary Prefix Codes

Ben has recently learned about binary prefix codes. A binary code is defined as a set of \(n\) distinct nonempty code words \(s_i\), each consisting of 0s and 1s. A code is called a prefix code if for every pair of distinct words \(s_i\) and \(s_j\), neither \(s_i\) is a prefix of \(s_j\) nor \(s_j\) is a prefix of \(s_i\). A word \(x\) is called a prefix of a word \(w\) if there exists a (possibly empty) word \(y\) such that \(xy = w\). For example, \(11\) is a prefix of \(110\) and \(0100\) is a prefix of \(0100\>.

Ben found an old paper containing \(n\) lines of binary code. Unfortunately, some characters in these code words are unreadable. It is known that each code word contains at most one unreadable character, represented by a question mark ?. Ben wonders if it is possible to replace every ? with either 0 or 1 so that the resulting set of code words forms a valid binary prefix code.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of code words. Each of the following \(n\) lines contains a nonempty binary string. Each string is composed solely of the characters 0 and 1, except that it may contain at most one unreadable character represented by ?.

outputFormat

Output YES if it is possible to replace all unreadable characters with 0 or 1 so that the resulting code is a valid binary prefix code; otherwise, output NO.

sample

3
0
10
11?

YES