Background

Xiao P originally wanted to submit an interesting adaptation of a problem, but it was directly bypassed by the solution to the original problem.

Xiao P was extremely frustrated, so he decided to submit an easy problem to provide some warmth.

Problem Statement

Xiao P learned Hall's Marriage Theorem and found it very interesting.

Xiao P discovered a direct corollary of Hall's Theorem: if the size of the left vertex set $L$ does not exceed the size of the right vertex set $R$, the degrees of all vertices in $L$ are equal, the degrees of all vertices in $R$ are equal, and the edge set is non-empty, then there must exist a matching of size $|L|$.

Xiao P found that one problem with Hall's Theorem is that it only provides existence without a construction.

Xiao P randomized a problem and wants you to help him solve it:

Given $n$ and $K$, it is guaranteed that $2K > n$. Let $[n] = \{0, 1, 2, \dots, n-1\}$. Let $\mathcal L$ be the set of all subsets of $[n]$ with size $K$, and $\mathcal R$ be the set of all subsets of $[n]$ with size $K-1$. For $S \in \mathcal L$ and $T \in \mathcal R$, there is an edge between $S$ and $T$ if and only if $T \subset S$. Please find a matching of size $|\mathcal L|$.

To reduce I/O time, this problem is evaluated using an interactive format.

Please do not attempt to hack the interactor!

Implementation Details

You must include the header file hall.h.

You need to implement the following procedure:

int solve(int n,int K,int s);

Here, $s$ represents a subset $S$ of $[n]$, where $x \in S$ if and only if the $x$-th bit of $s$ (from low to high) is $1$. It is guaranteed that $|S| = K$. You need to return a non-negative integer $t$, representing the set $T$ in the same format, such that $T \subset S$ and $|T| = K-1$.

The solve function may be called multiple times; please pay attention to variable initialization. It is guaranteed that $n$ and $K$ remain unchanged for every call, and each specific $s$ will be queried only once.

Evaluation Method

The sample interactor will read input data in the following format:

One line containing two positive integers, $n$ and $K$.

The sample interactor will output data in the following format:

Suppose the sample interactor calls the solve function $q$ times. It will output $q+1$ lines. The $i$-th line ($1 \le i \le q$) will be in the format s -> t, where $s$ and $t$ are strings of length $n$ consisting of $0$s and $1$s, representing the parameter and return value of the solve function, with bits ordered from low to high. The $(q+1)$-th line will output OK or WA, indicating whether the matching is valid.

Examples

Input 1

5 3

Output 1

00111 -> 00101
01011 -> 00011
01101 -> 01100
01110 -> 01010
10011 -> 10010
10101 -> 10001
10110 -> 00110
11001 -> 01001
11010 -> 11000
11100 -> 10100
OK

Constraints

It is guaranteed that $1 \le n \le 27$ and $2K > n$.

For $20\%$ of the data, $n \le 15$.

For $40\%$ of the data, $n \le 19$.

For $60\%$ of the data, $n \le 23$.

For $80\%$ of the data, $n \le 25$.

Please pay attention to the memory limit of this problem.

It is guaranteed that the interactor consumes no more than $0.3\text{s}$ of time and no more than $18\text{MB}$ of memory (including #include<bits/stdc++.h> and using namespace std;).