레몬컵 출제하기

어떤 문제가 웰논(WellKnown)이라 함은, 그와 유사한 문제가 이미 출제된 적이 있음을 뜻한다. 레몬컵 문제를 출제하게 된 다다스는 웰논 문제를 피하고 싶었기 때문에 다음과 같은 기준을 세웠다.

문제 $A$가 문제 $B$보다 먼저 출제되었고 문제 $A$에서 사용하는 알고리즘이 문제 $B$에서 사용하는 알고리즘을 모두 포함한다면, 문제 $B$를 웰논이라고 정의한다.

세상에는 수많은 알고리즘이 존재하지만, 다다스는 $K$개의 알고리즘만 알고 있다. 따라서 다다스가 출제하는 문제는 이 $K$개의 알고리즘 내에서만 다뤄진다.

다다스가 출제한 $N$개의 문제가 출제 순서대로 주어진다. 각 문제마다 이전에 출제된 문제들과 비교해 웰논이라면 WellKnown, 아니라면 AdHoc을 출력하라.

알고리즘을 전혀 사용하지 않는 문제가 있을 수 있음에 유의하라.

입력은 다음과 같은 형식으로 주어진다.

$N \ K$

$S\_1$

$S\_2$

$\vdots$

$S\_N$

값 $z\_i$는 다음과 같이 정의된다.

• $i=1$일 때, $z\_1=0$이다.
• $i>1$일 때, $(i-1)$번째 문제가 웰논이었다면 $z\_i=0$, 아니라면 $z\_i=1$이다.

$S\_i$는 $i$번째 문제의 정보를 나타낸다. 이 문자열은 길이가 $K$이며, $0$과 $1$로만 이루어져 있다. $z\_i$의 값에 따라 문자열 $S\_i$의 해석 방법이 달라진다.

• $z\_i=0$인 경우: $S\_i$의 $j$번째 문자가 $1$이면 $j$번 알고리즘을 사용한다는 의미이고, $0$이면 사용하지 않는다는 의미이다.
• $z\_i=1$인 경우: $S\_i$의 $(K-j+1)$번째 문자가 $1$이면 $j$번 알고리즘을 사용한다는 의미이고, $0$이면 사용하지 않는다는 의미이다.

첫째 줄부터 $N$개의 줄에 걸쳐 각 문제가 WellKnown인지 AdHoc인지 한 줄에 하나씩 출력한다.

• $1 \leq N \leq 300\ 000$.
• $1 \leq K \leq 20$.