시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB111100.000%

## 문제

This is an interactive problem.

Jury has chosen two secret binary strings of length $N$ and called them $s$ and $t$ such that $s$ is not lexicographically greater than $t$. Your task is to find out which strings were chosen. To do that, you can ask the jury to generate up to $Q$ strings. Each such string $r$ will be generated in the following way:

1. start by assigning $r = s$ or $r = t$, choosing one of them randomly with equal probability,
2. randomly select $K$ distinct positions in the string $r$ so that each set of $K$ positions has equal probability of being selected,
3. flip the digits at the selected positions in $r$: change all "0"s to "1"s and all "1"s to "0"s,
4. give the modified string $r$ to you.

Note that $s$ and $t$ don't change during generation of string $r$.

Your task is to correctly guess $s$ and $t$.

## 인터랙션

Initially, you are given a single line with three integers $N$, $K$, and $Q$ ($N = 100$, $K = 15$, $Q = 100$): the length of the strings $s$ and $t$, the number of positions to choose for flipping, and the maximum number of strings which can be generated.

To request another generated string, print a line containing a single "?" to the standard output. After that, you will be given a line containing a string of $N$ binary digits: the newly generated string $r$. You can make no more than $Q$ such requests.

When you are ready to make a guess, print a line in the format "! $s$ $t$" where $s$ and $t$ are two strings of $N$ binary digits each. After that, terminate your program gracefully.

To prevent output buffering, flush the output buffer after each printed line: this can be done by using, for example, fflush (stdout) in C or C++, System.out.flush () in Java, flush (output) in Pascal, or sys.stdout.flush () in Python. Also, do not forget to terminate each line of output with a newline character.

## 예제 입력 1

4 1 42

1010

1110

0110

0010

0000

0100

0011

0111



## 예제 출력 1


?

?

?

?

?

?

?

?

! 0010 0110


## 노트

This example violates the constraints, and is given only to illustrate the process of interaction. All tests in the testing system will satisfy all the constraints from the statement.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.