Artificial Intelligence Feature Simulation

In 2023, artificial intelligence has become extremely popular. In order to obtain data for AI training, we wish to produce an AI robot that simulates humans. We conducted a survey with n respondents. Each respondent has k binary features represented by a 01 string b_i,1b_i,2...b_i,k. Specifically, for the i-th respondent, if they satisfy the j-th feature, then b_i,j=1, otherwise b_i,j=0.

The AI is also described by a feature sequence q₁q₂...q_k. In order for the AI to be as human‐like as possible, its feature sequence must satisfy the following condition: For every nonempty index set \(S = \{j_1, j_2, \dots, j_t\}\) with \(1 \le j_1 < j_2 < \cdots

[ b_{i,j_l} = q_{j_l} \quad \text{for every } 1 \le l \le t. ]

Moreover, due to ethical restrictions, the AI's entire feature sequence must not be identical to that of any respondent.

Due to extremely limited budget, you can only manufacture an AI whose feature sequence has at most 3 ones (i.e. at most 3 positions where \(q_j=1\)). Your task is to output any legal AI feature sequence that satisfies the above conditions and the manufacturing constraint. If no such feature sequence exists, output none.

Note: Every condition must be verified on all nonempty subsets of indices \(S \subseteq \{1,2,...,k\}\): For every such \(S\), there must exist some respondent whose features on indices in \(S\) match the chosen AI sequence.

inputFormat

The first line contains two integers n and k separated by a space. Each of the following n lines contains a binary string of length k representing the feature sequence of a respondent.

outputFormat

Output a binary string of length k representing the AI's feature sequence that meets the conditions and has at most 3 ones. If no such sequence exists, output none.

sample

2 2
00
11

none