## 1. Abridged problem statement

You are given a rectangular Sokoban maze of up to `100 x 100` cells with exactly one player `@`, one box `$`, and one target cell `.`.

Cells are:

- `#` — wall
- space — empty/passable
- `@` — initial player position
- `$` — initial box position
- `.` — target position

The player can move in four directions through passable cells. If the player moves into the box, the box is pushed one cell in that direction, provided the destination cell is passable. The box cannot be pulled.

Find a solution that moves the box onto the target.

Among all valid solutions:

1. Minimize the number of box pushes.
2. Subject to that, minimize the total number of player moves.

Output the sequence of moves:

- lowercase `u`, `d`, `l`, `r` for ordinary player moves,
- uppercase `U`, `D`, `L`, `R` for moves that push the box.

If no solution exists, output:

```text
Impossible.
```

---

## 2. Detailed editorial

Because there is only one box, we can solve the puzzle using shortest path search over compressed states.

### Key observation

The full state of the game consists of:

- the box position,
- the player position.

However, after a push, the player is always standing in the previous box cell. Therefore, for planning future pushes, we do not need the exact full player position during walking; we only need to know from which side of the box the player currently stands.

So we define a state as:

```text
(box cell, side)
```

where `side` is one of the four directions around the box and tells us where the player is relative to the box.

For example, if the box is at `(r, c)` and `side = up`, then the player is at `(r - 1, c)`.

There are at most:

```text
rows * cols * 4
```

states, which is manageable for a `100 x 100` maze.

---

### Cost function

We need the best solution by lexicographic order:

```text
(number of pushes, total number of moves)
```

A push contributes:

- `+1` push,
- `+1` move.

Walking without pushing contributes:

- `+0` pushes,
- `+k` moves.

Therefore, we run Dijkstra where the distance of each state is a pair:

```text
(pushes, moves)
```

and pairs are compared lexicographically.

---

### Transition between states

Suppose the box is at cell `B`.

To push it in direction `d`, the player must stand at the cell behind the box:

```text
behind = B - d
```

The destination cell of the box is:

```text
front = B + d
```

The push is valid if:

1. `behind` is passable,
2. `front` is passable,
3. the player can walk from their current position to `behind` without passing through the box.

To test condition 3, we run BFS on the maze, treating the current box cell as a wall.

If the player can reach `behind` in `walk_distance` steps, then the new state becomes:

```text
(new box position = front, new player side = opposite(d))
```

because after the push, the player stands at the old box position, which is behind the new box.

The cost added is:

```text
(+1 push, +walk_distance + 1 moves)
```

---

### Initial states

Initially, the player is at `@` and the box is at `$`.

We run one BFS from the initial player position, treating the initial box position as blocked.

For each direction in which the player can stand behind the box and push it, we create an initial Dijkstra state.

---

### Goal

The first time Dijkstra removes a state whose box position is the target cell, that state is optimal because Dijkstra processes states in increasing order of:

```text
(pushes, moves)
```

---

### Path reconstruction

For each relaxed state, we store:

- its predecessor state,
- the direction of the push that created it.

After reaching the target, we follow predecessors backward to recover the sequence of pushes.

Between two consecutive pushes, the player may need to walk. We recompute a BFS path from the previous player position to the required pushing position, again treating the box as an obstacle.

We output:

- lowercase letters for the walking path,
- one uppercase letter for the push.

---

### Complexity

Let:

```text
N = rows * cols
```

There are at most `4N` states.

For each processed state, we may perform a BFS over the grid, costing `O(N)`.

Worst-case complexity:

```text
O(N * 4N log N)
```

in the most pessimistic case, but in practice this is acceptable for the given one-box Sokoban setting.

Memory usage is:

```text
O(N)
```

for BFS arrays plus:

```text
O(4N)
```

for Dijkstra arrays.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
const int opp[4] = {1, 0, 3, 2};
const char low[4] = {'u', 'd', 'l', 'r'};
const char upp[4] = {'U', 'D', 'L', 'R'};

int rows, cols;
vector<string> grid;
int start_keeper, start_box, target;

void read() {
    vector<string> raw;
    string line;
    while(getline(cin, line)) {
        if(!line.empty() && line.back() == '\r') {
            line.pop_back();
        }
        raw.push_back(line);
    }

    rows = raw.size();
    cols = 0;
    for(auto& s: raw) {
        cols = max(cols, (int)s.size());
    }

    grid.assign(rows, string(cols, '#'));
    for(int r = 0; r < rows; r++) {
        for(int c = 0; c < (int)raw[r].size(); c++) {
            grid[r][c] = raw[r][c];
        }
    }

    start_keeper = start_box = target = -1;
    for(int r = 0; r < rows; r++) {
        for(int c = 0; c < cols; c++) {
            if(grid[r][c] == '@') {
                start_keeper = r * cols + c;
                grid[r][c] = ' ';
            } else if(grid[r][c] == '$') {
                start_box = r * cols + c;
                grid[r][c] = ' ';
            } else if(grid[r][c] == '.') {
                target = r * cols + c;
                grid[r][c] = ' ';
            }
        }
    }
}

void solve() {
    // We search over states (box cell, side), where "side" records which of
    // the four cells neighbouring the box the keeper stands on, i.e. the cell
    // the box was last pushed from. A push in direction d is possible only when
    // the keeper can walk to the cell directly behind the box (opposite to d)
    // and the cell in front of the box is free; the push then advances the box
    // one cell and moves the keeper onto the box's old cell.
    //
    // The objective is lexicographic: first minimise the number of pushes, then
    // the total number of keeper moves. This is a shortest path with cost
    // (pushes, moves) compared lexicographically, so we run Dijkstra over the
    // (box, side) states. Walking the keeper does between two consecutive
    // pushes costs no push and contributes its length in moves; for a popped
    // state we recover those lengths with a single grid BFS from the keeper's
    // cell that treats the box as a wall, yielding the distance to every
    // reachable push position at once.
    //
    // Pushing in direction d from box cell B sends the box to B + d and the
    // keeper to B, so the successor is (B + d, opposite(d)) with one extra push
    // and (walk distance to B - d) + 1 extra moves. The keeper's starting cell
    // is handled by one initial BFS that seeds every possible first push. The
    // first popped state whose box sits on the target cell is optimal.
    //
    // To print a solution we follow the predecessor chain and, for each
    // recorded push, recompute the keeper's walking path with a BFS that tracks
    // parents, emitting lower case letters for plain moves and the upper case
    // letter for the push itself. If no state with the box on the target is
    // ever popped the puzzle is unsolvable.

    if(start_box == target) {
        cout << "\n";
        return;
    }

    int cells = rows * cols;
    int states = 4 * cells;

    vector<int> walk_dist(cells), walk_seen(cells, 0);
    vector<int> bfs_queue(cells);
    int walk_timer = 0;

    auto bfs_dist = [&](int src, int obstacle) {
        walk_timer++;
        int orow = obstacle / cols, ocol = obstacle % cols;
        int need = 0;
        for(int k = 0; k < 4; k++) {
            int nr = orow + dr[k], nc = ocol + dc[k];
            if(nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
               grid[nr][nc] != '#') {
                need++;
            }
        }

        int found = 0, head = 0, tail = 0;
        walk_seen[src] = walk_timer;
        walk_dist[src] = 0;
        bfs_queue[tail++] = src;
        if(abs(src / cols - orow) + abs(src % cols - ocol) == 1) {
            found++;
        }

        while(head < tail && found < need) {
            int cur = bfs_queue[head++];
            int cr = cur / cols, cc = cur % cols, cd = walk_dist[cur];
            for(int k = 0; k < 4; k++) {
                int nr = cr + dr[k], nc = cc + dc[k];
                if(nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    continue;
                }
                int ncell = nr * cols + nc;
                if(grid[nr][nc] == '#' || ncell == obstacle) {
                    continue;
                }
                if(walk_seen[ncell] == walk_timer) {
                    continue;
                }

                walk_seen[ncell] = walk_timer;
                walk_dist[ncell] = cd + 1;
                bfs_queue[tail++] = ncell;
                if(abs(nr - orow) + abs(nc - ocol) == 1) {
                    found++;
                }
            }
        }
    };

    const int INF = INT_MAX;
    vector<int> dist_push(states, INF), dist_move(states, INF);
    vector<int> par(states, -2), par_dir(states, -1);

    using node = tuple<int, int, int>;
    priority_queue<node, vector<node>, greater<node>> pq;

    auto relax = [&](int st, int np, int nm, int from, int dir) {
        if(np < dist_push[st] || (np == dist_push[st] && nm < dist_move[st])) {
            dist_push[st] = np;
            dist_move[st] = nm;
            par[st] = from;
            par_dir[st] = dir;
            pq.push({np, nm, st});
        }
    };

    auto try_pushes = [&](int box, int keeper, int from, int base_push,
                          int base_move) {
        bfs_dist(keeper, box);
        int brow = box / cols, bcol = box % cols;
        for(int i = 0; i < 4; i++) {
            int wr = brow - dr[i], wc = bcol - dc[i];
            int fr = brow + dr[i], fc = bcol + dc[i];
            if(wr < 0 || wr >= rows || wc < 0 || wc >= cols) {
                continue;
            }
            if(fr < 0 || fr >= rows || fc < 0 || fc >= cols) {
                continue;
            }
            if(grid[wr][wc] == '#' || grid[fr][fc] == '#') {
                continue;
            }

            int behind = wr * cols + wc;
            if(walk_seen[behind] != walk_timer) {
                continue;
            }

            int new_box = fr * cols + fc;
            int new_state = new_box * 4 + opp[i];
            relax(
                new_state, base_push + 1, base_move + walk_dist[behind] + 1,
                from, i
            );
        }
    };

    try_pushes(start_box, start_keeper, -1, 0, 0);

    int goal_state = -1;
    while(!pq.empty()) {
        auto [pp, mm, st] = pq.top();
        pq.pop();
        if(pp != dist_push[st] || mm != dist_move[st]) {
            continue;
        }

        int box = st / 4, side = st % 4;
        if(box == target) {
            goal_state = st;
            break;
        }

        int keeper = (box / cols + dr[side]) * cols + (box % cols + dc[side]);
        try_pushes(box, keeper, st, pp, mm);
    }

    if(goal_state == -1) {
        cout << "Impossible.\n";
        return;
    }

    vector<int> chain;
    for(int cur = goal_state; cur != -1; cur = par[cur]) {
        chain.push_back(cur);
    }
    reverse(chain.begin(), chain.end());

    vector<int> path_seen(cells, 0), path_par(cells), path_par_dir(cells);
    int path_timer = 0;

    auto bfs_path = [&](int src, int dst, int obstacle) {
        string moves;
        if(src == dst) {
            return moves;
        }

        path_timer++;
        int head = 0, tail = 0;
        path_seen[src] = path_timer;
        path_par[src] = -1;
        bfs_queue[tail++] = src;

        while(head < tail) {
            int cur = bfs_queue[head++];
            if(cur == dst) {
                break;
            }

            int cr = cur / cols, cc = cur % cols;
            for(int k = 0; k < 4; k++) {
                int nr = cr + dr[k], nc = cc + dc[k];
                if(nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    continue;
                }
                int ncell = nr * cols + nc;
                if(grid[nr][nc] == '#' || ncell == obstacle) {
                    continue;
                }
                if(path_seen[ncell] == path_timer) {
                    continue;
                }

                path_seen[ncell] = path_timer;
                path_par[ncell] = cur;
                path_par_dir[ncell] = k;
                bfs_queue[tail++] = ncell;
            }
        }

        for(int cur = dst; cur != src; cur = path_par[cur]) {
            moves += low[path_par_dir[cur]];
        }
        reverse(moves.begin(), moves.end());
        return moves;
    };

    string result;
    for(int st: chain) {
        int dir = par_dir[st];
        int prev = par[st];

        int prev_box, prev_keeper;
        if(prev == -1) {
            prev_box = start_box;
            prev_keeper = start_keeper;
        } else {
            int pb = prev / 4, ps = prev % 4;
            prev_box = pb;
            prev_keeper = (pb / cols + dr[ps]) * cols + (pb % cols + dc[ps]);
        }

        int behind =
            (prev_box / cols - dr[dir]) * cols + (prev_box % cols - dc[dir]);
        result += bfs_path(prev_keeper, behind, prev_box);
        result += upp[dir];
    }

    cout << result << "\n";
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys
import heapq
from collections import deque


# Direction order: up, down, left, right.
DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]

# Opposite direction for each direction.
OPP = [1, 0, 3, 2]

# Lowercase letters for ordinary moves.
LOW = ['u', 'd', 'l', 'r']

# Uppercase letters for pushes.
UPP = ['U', 'D', 'L', 'R']


def solve():
    # Read all input lines without removing spaces.
    raw = sys.stdin.read().splitlines()

    # If input is empty, do nothing.
    if not raw:
        return

    # Remove possible Windows carriage returns.
    raw = [line.rstrip('\r') for line in raw]

    # Number of rows.
    rows = len(raw)

    # Normalize width.
    # Some judges/examples may contain visually ragged rows, so we pad with walls.
    cols = max(len(line) for line in raw)

    # Create rectangular grid padded with walls.
    grid = [['#'] * cols for _ in range(rows)]

    # Copy input characters into the rectangular grid.
    for r in range(rows):
        for c, ch in enumerate(raw[r]):
            grid[r][c] = ch

    # Special positions.
    start_keeper = -1
    start_box = -1
    target = -1

    # Find @, $, and ., then replace them by empty cells.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '@':
                start_keeper = r * cols + c
                grid[r][c] = ' '
            elif grid[r][c] == '$':
                start_box = r * cols + c
                grid[r][c] = ' '
            elif grid[r][c] == '.':
                target = r * cols + c
                grid[r][c] = ' '

    # If box is already on target, no moves are needed.
    if start_box == target:
        print()
        return

    # Total number of cells.
    cells = rows * cols

    # Total number of compressed states.
    # State = box_position * 4 + player_side.
    states = cells * 4

    # Arrays used for walking BFS.
    walk_dist = [0] * cells
    walk_seen = [0] * cells
    walk_timer = 0

    # Reusable queue array for BFS.
    bfs_queue = [0] * cells

    def is_wall(cell):
        """Return True if encoded cell is a wall."""
        r = cell // cols
        c = cell % cols
        return grid[r][c] == '#'

    def bfs_dist(src, obstacle):
        """
        Compute shortest walking distances from src while treating obstacle
        as blocked. Results are stored in walk_dist and walk_seen.

        Uses timestamp technique so arrays do not need to be cleared.
        """
        nonlocal walk_timer

        # New BFS timestamp.
        walk_timer += 1

        # Decode obstacle position.
        orow = obstacle // cols
        ocol = obstacle % cols

        # Count passable neighboring cells of the obstacle.
        # We only care about reaching cells adjacent to the box,
        # because those are possible push positions.
        need = 0
        for k in range(4):
            nr = orow + DR[k]
            nc = ocol + DC[k]
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
                need += 1

        # Number of relevant adjacent cells already found.
        found = 0

        # Initialize BFS queue.
        head = 0
        tail = 0

        # Mark source as visited.
        walk_seen[src] = walk_timer
        walk_dist[src] = 0
        bfs_queue[tail] = src
        tail += 1

        # If source itself is adjacent to the obstacle, count it.
        if abs(src // cols - orow) + abs(src % cols - ocol) == 1:
            found += 1

        # Standard BFS, with early stop once all adjacent cells are reached.
        while head < tail and found < need:
            cur = bfs_queue[head]
            head += 1

            cr = cur // cols
            cc = cur % cols
            cd = walk_dist[cur]

            for k in range(4):
                nr = cr + DR[k]
                nc = cc + DC[k]

                # Skip out-of-bounds cells.
                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue

                ncell = nr * cols + nc

                # Skip walls and the current box position.
                if grid[nr][nc] == '#' or ncell == obstacle:
                    continue

                # Skip already visited cells.
                if walk_seen[ncell] == walk_timer:
                    continue

                # Visit neighbor.
                walk_seen[ncell] = walk_timer
                walk_dist[ncell] = cd + 1
                bfs_queue[tail] = ncell
                tail += 1

                # Count if it is adjacent to the obstacle.
                if abs(nr - orow) + abs(nc - ocol) == 1:
                    found += 1

    # Infinite distance.
    INF = 10**18

    # Dijkstra distances.
    dist_push = [INF] * states
    dist_move = [INF] * states

    # Parent information for reconstruction.
    parent = [-2] * states
    parent_dir = [-1] * states

    # Priority queue entries are (pushes, moves, state).
    pq = []

    def relax(st, new_pushes, new_moves, from_state, push_dir):
        """Relax one Dijkstra state."""
        if (
            new_pushes < dist_push[st]
            or (
                new_pushes == dist_push[st]
                and new_moves < dist_move[st]
            )
        ):
            dist_push[st] = new_pushes
            dist_move[st] = new_moves
            parent[st] = from_state
            parent_dir[st] = push_dir
            heapq.heappush(pq, (new_pushes, new_moves, st))

    def try_pushes(box, keeper, from_state, base_pushes, base_moves):
        """
        Try all possible pushes from current box and keeper positions.

        box: current encoded box cell.
        keeper: current encoded player cell.
        from_state: predecessor compressed state.
        base_pushes/base_moves: current Dijkstra cost.
        """
        # Compute which cells the player can reach.
        bfs_dist(keeper, box)

        # Decode box position.
        brow = box // cols
        bcol = box % cols

        # Try pushing in all four directions.
        for d in range(4):
            # Player must stand behind the box.
            wr = brow - DR[d]
            wc = bcol - DC[d]

            # Box moves to the front cell.
            fr = brow + DR[d]
            fc = bcol + DC[d]

            # Check boundaries.
            if wr < 0 or wr >= rows or wc < 0 or wc >= cols:
                continue
            if fr < 0 or fr >= rows or fc < 0 or fc >= cols:
                continue

            # Both cells must be passable.
            if grid[wr][wc] == '#' or grid[fr][fc] == '#':
                continue

            # Encoded player pushing position.
            behind = wr * cols + wc

            # Player must be able to walk there.
            if walk_seen[behind] != walk_timer:
                continue

            # New box position.
            new_box = fr * cols + fc

            # After the push, player is on the old box cell,
            # which is opposite direction from the new box.
            new_state = new_box * 4 + OPP[d]

            # Cost includes walking to behind plus one push move.
            relax(
                new_state,
                base_pushes + 1,
                base_moves + walk_dist[behind] + 1,
                from_state,
                d,
            )

    # Generate first pushes from the initial configuration.
    try_pushes(start_box, start_keeper, -1, 0, 0)

    # Dijkstra search.
    goal_state = -1

    while pq:
        pushes, moves, st = heapq.heappop(pq)

        # Ignore stale entries.
        if pushes != dist_push[st] or moves != dist_move[st]:
            continue

        # Decode state.
        box = st // 4
        side = st % 4

        # First time reaching target is optimal.
        if box == target:
            goal_state = st
            break

        # Recover current player position from box and side.
        keeper_r = box // cols + DR[side]
        keeper_c = box % cols + DC[side]
        keeper = keeper_r * cols + keeper_c

        # Try next pushes.
        try_pushes(box, keeper, st, pushes, moves)

    # If no solution exists.
    if goal_state == -1:
        print("Impossible.")
        return

    # Reconstruct sequence of compressed states.
    chain = []
    cur = goal_state
    while cur != -1:
        chain.append(cur)
        cur = parent[cur]

    # Chronological order.
    chain.reverse()

    # Arrays for reconstructing actual walking paths.
    path_seen = [0] * cells
    path_parent = [-1] * cells
    path_parent_dir = [-1] * cells
    path_timer = 0

    def bfs_path(src, dst, obstacle):
        """
        Return one shortest lowercase walking path from src to dst,
        treating obstacle as blocked.
        """
        nonlocal path_timer

        # No walking needed.
        if src == dst:
            return ""

        # New BFS timestamp.
        path_timer += 1

        # Initialize queue.
        head = 0
        tail = 0

        path_seen[src] = path_timer
        path_parent[src] = -1
        bfs_queue[tail] = src
        tail += 1

        # Standard BFS.
        while head < tail:
            cur = bfs_queue[head]
            head += 1

            if cur == dst:
                break

            cr = cur // cols
            cc = cur % cols

            for d in range(4):
                nr = cr + DR[d]
                nc = cc + DC[d]

                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue

                ncell = nr * cols + nc

                if grid[nr][nc] == '#' or ncell == obstacle:
                    continue

                if path_seen[ncell] == path_timer:
                    continue

                path_seen[ncell] = path_timer
                path_parent[ncell] = cur
                path_parent_dir[ncell] = d
                bfs_queue[tail] = ncell
                tail += 1

        # Reconstruct path from dst back to src.
        result = []
        cur = dst

        while cur != src:
            d = path_parent_dir[cur]
            result.append(LOW[d])
            cur = path_parent[cur]

        # Reverse to get forward path.
        result.reverse()

        return ''.join(result)

    # Build final answer.
    answer = []

    # Each state in chain corresponds to one push.
    for st in chain:
        # Direction used to enter this state.
        d = parent_dir[st]

        # Previous compressed state.
        prev = parent[st]

        # Determine previous box and player positions.
        if prev == -1:
            prev_box = start_box
            prev_keeper = start_keeper
        else:
            prev_box = prev // 4
            prev_side = prev % 4
            prev_keeper = (
                (prev_box // cols + DR[prev_side]) * cols
                + (prev_box % cols + DC[prev_side])
            )

        # Cell where player must stand to perform this push.
        behind = (
            (prev_box // cols - DR[d]) * cols
            + (prev_box % cols - DC[d])
        )

        # Add walking moves.
        answer.append(bfs_path(prev_keeper, behind, prev_box))

        # Add pushing move.
        answer.append(UPP[d])

    # Print complete solution string.
    print(''.join(answer))


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

---

## 5. Compressed editorial

Use Dijkstra on compressed states:

```text
state = (box position, player side relative to box)
```

There are at most `4 * rows * cols` states.

The distance of a state is:

```text
(push count, total move count)
```

compared lexicographically.

From a state, run BFS for the player while treating the current box cell as a wall. This tells which cells around the box the player can reach. For each direction, if the player can stand behind the box and the box can move forward, relax the successor state with cost:

```text
(+1 push, +walking distance + 1 move)
```

The first popped Dijkstra state whose box is on the target is optimal.

Store predecessor state and push direction. Reconstruct the push sequence, and for each push recompute a shortest walking path between the previous player position and the required pushing cell. Output walking moves in lowercase and pushes in uppercase. If no target state is reached, output `Impossible.`.
