<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

459. Choreographer Problem
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



As you probably know, choreography is the art of making dances. But it is not a so well-known fact that it is also the science of making dances.

There are n dancers numbered from 1 to n in the dance troupe, and all of them are working hard to create a new original dance. Before the dance starts each dancer puts on his special hand-made costume, and he has to wear this costume for the duration of the entire dance.

It is known that the costume of i-th dancer is similar to the costumes of (i-1)-th and (i+1)-th dancers (therefore the dancers are similar too), but at the same time, i-th dancer is not similar to any other dancer. Therefore, (i-1)-th and (i+1)-th dancers are not similar. If n > 1, then the first dancer has the only similar dancer, the last dancer has the only similar dancer, and all other dancers have exactly two similar dancers.

The dance starts and ends with an empty stage. The stage should not be empty during the dance. Each minute one of the following changes happens on the stage:
one dancer (who is currently not on the stage) appears;
one dancer (who is currently on the stage) leaves the stage;
one dancer takes the place of another dancer similar to him/her (basically the dancers switch over — one dancer leaves the stage, while a similar dancer appears on the stage)


At every moment of time the stage must not have more than k dancers, because spectators may lose attention if there are too many dancers on the stage.

Now choreographer is thinking about arranging the dance in such a way that each set of the dancers containing no more than k dancers appears on the stage exactly once. Your job is to write a program to help the choreographer.

Input
The first line contains two positive integer numbers n,k (1 ≤ n ≤ 20; 1 ≤ k ≤ n).

Output
Print the only line describing the dance. The substring +i means that the i-th dancer appears on the stage, the substring -i means that the i-th dancer leaves the stage. The substring ++i means that the i-th dancer leaves while the similar (i+1)-th dancer appears, and --i means that the i-th dancer leaves while the similar (i-1)-th dancer appears. The output will be processed from the left to the right.

If there are many solutions, you may output any of them. If there is no solution, print 0 to the only line of output.

Example(s)
sample input
sample output
2 1
+1++1-2

<|response|>
## 1) Abridged problem statement (concise)

There are `n (1..n)` dancers. Dancer `i` is similar only to `i-1` and `i+1` (if they exist).  
The stage starts empty and must end empty; it must not be empty in between.

Each minute exactly one move happens:

- `+i`: dancer `i` enters (was not on stage)
- `-i`: dancer `i` leaves (was on stage)
- `++i`: dancer `i` leaves and similar dancer `i+1` enters (swap `i → i+1`)
- `--i`: dancer `i` leaves and similar dancer `i-1` enters (swap `i → i-1`)

At all times the stage contains at most `k` dancers.

Construct any sequence of moves such that **every subset of dancers of size ≤ k** appears on stage **exactly once** during the dance (empty set only at start and end). If impossible, print `0`.

Constraints: `n ≤ 20`.

---

## 2) Key observations

1. **State = subset of dancers**  
   The set of dancers on stage can be represented as a bitmask of length `n`.  
   We must visit every mask with `popcount(mask) ≤ k` exactly once.

2. **Allowed transitions between masks**
   From one minute to the next, the state changes by:
   - toggling **one** bit (`+i` or `-i`), i.e., Hamming distance 1
   - toggling **two adjacent** bits (`++i` or `--i`), i.e., bits `i` and `i+1` flip and no others

3. **This is a restricted Gray-code-like ordering**
   Classic Gray code lists all `2^n` masks with 1-bit transitions.  
   Here we list only masks with weight ≤ `k`, but we’re also allowed a special adjacent 2-bit transition, which is enough to connect the recursion halves.

4. **Recursive “reflection” construction works**
   If we can generate a valid order for `(n-1)` bits, we can extend to `n` bits by:
   - first listing masks with top bit `0`
   - then listing masks with top bit `1` in **reverse order**
   This reflection trick is exactly what makes the boundary transition small (here: 2 adjacent bits, still allowed).

---

## 3) Full solution approach

### Step A: Generate an ordering of all masks with ≤ k ones

Define `rec(n, k)` returning a list of masks (integers) over `n` bits that:

- contains every mask `m` with `popcount(m) ≤ k` exactly once
- consecutive masks differ by:
  - 1 bit, or
  - 2 **adjacent** bits

Recurrence:

- Base: `rec(n, 0) = [0]`
- For `k > 0`:
  - `A = rec(n-1, min(k, n-1))`  (top bit is 0)
  - `B = rec(n-1, k-1)`          (top bit is 1, remaining ≤ k-1)
  - append `reverse(B)` with the top bit set:
    \[
    rec(n,k) = A \;+\; \text{reverse}(B)\; \text{with bit } (n-1) \text{ set}
    \]

Why reverse?  
It ensures the boundary between the two halves is always an allowed move (it ends up being a 2-adjacent-bit toggle in this restricted setting).

### Step B: Ensure dance ends empty
`rec(n,k)` starts with `0` (empty). We append another `0` at the end so the dance ends empty:
```
gray = rec(n,k)
gray.append(0)
```
The empty stage appears only at the start and at the end.

### Step C: Convert mask transitions to move strings
For each consecutive pair `(prev, cur)`:

- Let `diff = prev XOR cur`
- Collect changed bit positions.

Cases:

1) Exactly one bit `p` changed:
- if bit `p` is 1 in `cur` → `+ (p+1)`
- else → `- (p+1)`

2) Exactly two bits changed, they must be adjacent (`p` and `p+1`):
This corresponds to swapping dancer `p+1` with `p+2`.
We can output either `++(p+1)` or `--(p+2)` depending on direction; one simple mapping is:

- if lower bit `p` is 1 in `cur` → output `"--" << (p+2)` (means `(p+2) → (p+1)`)
- else → output `"++" << (p+1)` (means `(p+1) → (p+2)`)

### Complexity
Number of visited masks:
\[
\sum_{i=0}^{k} \binom{n}{i}
\]
With `n ≤ 20` this is manageable.  
Time is `O(n * number_of_masks)`.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, k;

/*
  rec(bits, limit) returns a list of bitmasks over 'bits' bits
  containing all masks with popcount <= limit exactly once,
  in an order where consecutive masks differ by:
    - 1 bit, or
    - 2 adjacent bits (a swap move).
*/
static vector<int> rec(int bits, int limit) {
    // If we can pick 0 dancers, only the empty set is allowed.
    if (limit == 0) return {0};

    // First part: top bit is 0 -> just enumerate masks of (bits-1) bits with <= limit ones.
    vector<int> a = rec(bits - 1, min(limit, bits - 1));

    // Second part: top bit is 1 -> remaining (bits-1) bits must have <= limit-1 ones.
    vector<int> b = rec(bits - 1, limit - 1);

    int top = 1 << (bits - 1);

    // Reflection trick: append reversed b with top bit set.
    // This ensures the boundary transition between a.back() and the next element is valid.
    for (auto it = b.rbegin(); it != b.rend(); ++it) {
        a.push_back((*it) | top);
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    // Generate the sequence of stage states.
    vector<int> gray = rec(n, k);

    // Must end empty as well.
    gray.push_back(0);

    // Convert transitions to required operations.
    // We'll print operations consecutively with no spaces, as in the sample.
    for (int j = 1; j < (int)gray.size(); j++) {
        int prev = gray[j - 1];
        int cur  = gray[j];

        int diff = prev ^ cur;

        // Collect indices of changed bits.
        vector<int> pos;
        for (int i = 0; i < n; i++) {
            if ((diff >> i) & 1) pos.push_back(i);
        }

        if ((int)pos.size() == 1) {
            // Single-bit toggle: +i or -i
            int p = pos[0];
            if ((cur >> p) & 1) cout << "+" << (p + 1);
            else                cout << "-" << (p + 1);
        } else {
            // Two-bit toggle (construction guarantees it's adjacent): ++i or --i
            // We assume pos[0] = p, pos[1] = p+1 because we scanned bits in increasing order.
            int p = pos[0];

            // If the lower bit is ON in the current state, we interpret this as (p+2)->(p+1),
            // i.e. dancer (p+2) leaves, (p+1) enters => "--(p+2)".
            if ((cur >> p) & 1) cout << "--" << (p + 2);
            else                cout << "++" << (p + 1);
        }
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def rec(bits: int, limit: int) -> list[int]:
    """
    Generate an order of all bitmasks of length 'bits' with popcount <= limit,
    such that consecutive masks differ by either:
      - 1 bit toggle (add/remove dancer), or
      - 2 adjacent bit toggles (swap i <-> i+1).
    """
    if limit == 0:
        return [0]

    # Masks with top bit = 0
    a = rec(bits - 1, min(limit, bits - 1))

    # Masks with top bit = 1 (so remaining bits have <= limit-1 ones)
    b = rec(bits - 1, limit - 1)

    top = 1 << (bits - 1)

    # Append reversed b with the top bit set (reflection trick).
    for x in reversed(b):
        a.append(x | top)

    return a

def solve(n: int, k: int) -> str:
    gray = rec(n, k)

    # Ensure the dance ends with an empty stage.
    gray.append(0)

    out = []

    for j in range(1, len(gray)):
        prev = gray[j - 1]
        cur = gray[j]
        diff = prev ^ cur

        # Find changed bit positions.
        pos = [i for i in range(n) if (diff >> i) & 1]

        if len(pos) == 1:
            p = pos[0]
            if (cur >> p) & 1:
                out.append(f"+{p+1}")
            else:
                out.append(f"-{p+1}")
        else:
            # Two changed bits; by construction they are adjacent.
            p = pos[0]  # lower index
            if (cur >> p) & 1:
                # Now lower bit is 1 => interpret as (p+2)->(p+1) swap
                out.append(f"--{p+2}")
            else:
                # Now lower bit is 0 => interpret as (p+1)->(p+2) swap
                out.append(f"++{p+1}")

    return "".join(out)

def main() -> None:
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    k = int(data[1])
    sys.stdout.write(solve(n, k))

if __name__ == "__main__":
    main()
```

If you want, I can also add a small verifier (for debugging) that parses the output string and checks that every subset of size ≤ k appears exactly once and all moves are valid.