레몬컵 출제하기

<p data-start="0" data-end="182">A problem is called <strong data-start="20" data-end="33">WellKnown</strong> if a similar problem has already appeared before. To avoid creating WellKnown problems for the Lemon Cup, Dadas established the following criterion:</p> <blockquote>If problem $A$ was published before problem $B$, and all algorithms used in problem $A$ are also used in problem $B$, then problem $B$ is defined as <strong data-start="333" data-end="346">WellKnown</strong>.</blockquote> <p data-start="349" data-end="685">There exist many algorithms in the world, but Dadas only knows $K$ algorithms. Therefore, all problems created by Dadas involve only these $K$ algorithms. You are given $N$ problems in the order they were published. For each problem, determine whether it is <strong data-start="607" data-end="620">WellKnown</strong> or <strong data-start="624" data-end="633">AdHoc</strong> by comparing it with previously published problems.</p> <p data-start="687" data-end="758">**Note that there may be problems that use no algorithms at all.**</p>

<div><p data-start="760" data-end="803">The input is given in the following format:</p> <blockquote>$N \ K$<br> $S_1$<br> $S_2$<br> $\vdots$<br> $S_N$</blockquote></div><div>Define $z_i$ as follows:</div><div><ul><li>&nbsp;If $i = 1$, then $z_1 = 0$.</li><li>If $i \gt 1$, then $z_i = 0$ if the $(i-1)$-th problem is `WellKnown`, and $z_i = 1$ otherwise.</li></ul></div><div>Each string $S_i$ represents the information of the $i$-th problem. It is a binary string of length $K$. The interpretation of $S_i$ depends on the value of $z_i$:</div><div><ul><li>If $z_i = 0$: the $j$-th character of $S_i$ is $1$ if the $j$-th algorithm is used, and $0$ otherwise.</li><li>If $z_i = 1$: the $(K - j + 1)$-th character of $S_i$ is $1$ if the $j$-th algorithm is used, and $0$ otherwise.</li></ul></div>

<ul><li>$1 \leq N \leq 300\ 000$</li><li>$1 \leq K \leq 20$</li></ul>