34253번 - 레몬컵 출제하기 서브태스크

문제

어떤 문제가 웰논(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$.

서브태스크

힌트