## 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. Provided C++ solution with detailed comments

```cpp
#include <bits/stdc++.h> // Includes almost all standard C++ library headers.

using namespace std; // Allows using standard library names without std:: prefix.

// Output operator for pairs, useful for debugging.
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second; // Print first and second separated by space.
}

// Input operator for pairs, useful for convenience.
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second; // Read first and second.
}

// Input operator for vectors.
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) { // Read every element of the vector.
        in >> x;
    }
    return in; // Return stream to allow chaining.
};

// Output operator for vectors.
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) { // Print every element.
        out << x << ' ';
    }
    return out; // Return stream to allow chaining.
};

// Movement row deltas: up, down, left, right.
const int dr[4] = {-1, 1, 0, 0};

// Movement column deltas: up, down, left, right.
const int dc[4] = {0, 0, -1, 1};

// Opposite direction indices.
const int opp[4] = {1, 0, 3, 2};

// Lowercase letters for ordinary player moves.
const char low[4] = {'u', 'd', 'l', 'r'};

// Uppercase letters for box-pushing moves.
const char upp[4] = {'U', 'D', 'L', 'R'};

// Number of rows and columns in the normalized grid.
int rows, cols;

// Grid after replacing @, $, . with spaces.
vector<string> grid;

// Encoded positions of initial player, initial box, and target.
int start_keeper, start_box, target;

void read() {
    vector<string> raw; // Raw input lines.
    string line;        // Temporary input line.

    // Read the whole input until EOF.
    while(getline(cin, line)) {
        // Remove Windows-style carriage return if present.
        if(!line.empty() && line.back() == '\r') {
            line.pop_back();
        }

        // Store line exactly, including spaces.
        raw.push_back(line);
    }

    // Number of rows is the number of lines.
    rows = raw.size();

    // Compute maximum row length.
    cols = 0;
    for(auto& s: raw) {
        cols = max(cols, (int)s.size());
    }

    // Initialize grid with walls.
    // This also safely pads shorter input lines with walls.
    grid.assign(rows, string(cols, '#'));

    // Copy raw characters into normalized rectangular grid.
    for(int r = 0; r < rows; r++) {
        for(int c = 0; c < (int)raw[r].size(); c++) {
            grid[r][c] = raw[r][c];
        }
    }

    // Initialize special positions as not found.
    start_keeper = start_box = target = -1;

    // Scan the grid to locate @, $, and ..
    for(int r = 0; r < rows; r++) {
        for(int c = 0; c < cols; c++) {
            if(grid[r][c] == '@') {
                // Encode position as r * cols + c.
                start_keeper = r * cols + c;

                // The player's initial cell is passable.
                grid[r][c] = ' ';
            } else if(grid[r][c] == '$') {
                // Store initial box position.
                start_box = r * cols + c;

                // The box's initial cell is passable.
                grid[r][c] = ' ';
            } else if(grid[r][c] == '.') {
                // Store target position.
                target = r * cols + c;

                // The target cell is passable.
                grid[r][c] = ' ';
            }
        }
    }
}

void solve() {
    // If the box is already on the target, no moves are needed.
    if(start_box == target) {
        cout << "\n";
        return;
    }

    // Total number of cells.
    int cells = rows * cols;

    // Each cell can be combined with 4 possible player sides.
    int states = 4 * cells;

    // BFS distance array for player walking.
    vector<int> walk_dist(cells);

    // Timestamp array to avoid clearing visited each BFS.
    vector<int> walk_seen(cells, 0);

    // Queue storage for BFS.
    vector<int> bfs_queue(cells);

    // Current BFS timestamp.
    int walk_timer = 0;

    // BFS that computes distances from src while treating obstacle as a wall.
    auto bfs_dist = [&](int src, int obstacle) {
        // Increase timestamp for this BFS.
        walk_timer++;

        // Decode obstacle position.
        int orow = obstacle / cols, ocol = obstacle % cols;

        // Count how many passable neighbors of the box may matter.
        int need = 0;
        for(int k = 0; k < 4; k++) {
            int nr = orow + dr[k], nc = ocol + dc[k];

            // Count passable adjacent cells.
            if(nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
               grid[nr][nc] != '#') {
                need++;
            }
        }

        // found counts how many relevant adjacent cells have been reached.
        int found = 0;

        // BFS queue pointers.
        int head = 0, tail = 0;

        // Mark source visited.
        walk_seen[src] = walk_timer;

        // Distance from source to itself is zero.
        walk_dist[src] = 0;

        // Push source into BFS queue.
        bfs_queue[tail++] = src;

        // If source is already adjacent to the obstacle, count it.
        if(abs(src / cols - orow) + abs(src % cols - ocol) == 1) {
            found++;
        }

        // Continue BFS until queue is empty or all relevant cells are found.
        while(head < tail && found < need) {
            // Pop current cell.
            int cur = bfs_queue[head++];

            // Decode current cell.
            int cr = cur / cols, cc = cur % cols;

            // Current walking distance.
            int cd = walk_dist[cur];

            // Try all four moves.
            for(int k = 0; k < 4; k++) {
                int nr = cr + dr[k], nc = cc + dc[k];

                // Skip out-of-bounds positions.
                if(nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    continue;
                }

                // Encode neighbor cell.
                int ncell = nr * cols + nc;

                // Skip walls and the current box cell.
                if(grid[nr][nc] == '#' || ncell == obstacle) {
                    continue;
                }

                // Skip already visited cells in this BFS.
                if(walk_seen[ncell] == walk_timer) {
                    continue;
                }

                // Mark neighbor as visited.
                walk_seen[ncell] = walk_timer;

                // Set distance to neighbor.
                walk_dist[ncell] = cd + 1;

                // Push neighbor into queue.
                bfs_queue[tail++] = ncell;

                // If neighbor is adjacent to the obstacle, count it.
                if(abs(nr - orow) + abs(nc - ocol) == 1) {
                    found++;
                }
            }
        }
    };

    // Infinite value for distances.
    const int INF = INT_MAX;

    // Minimum number of pushes for each state.
    vector<int> dist_push(states, INF);

    // Minimum number of total moves for each state, among same push count.
    vector<int> dist_move(states, INF);

    // Parent state for reconstruction.
    // -2 means unset, -1 means initial predecessor.
    vector<int> par(states, -2);

    // Direction of push used to enter each state.
    vector<int> par_dir(states, -1);

    // Priority queue node: pushes, moves, state.
    using node = tuple<int, int, int>;

    // Min-priority queue ordered lexicographically by pushes then moves.
    priority_queue<node, vector<node>, greater<node>> pq;

    // Relax a Dijkstra state.
    auto relax = [&](int st, int np, int nm, int from, int dir) {
        // Update if push count improves, or same pushes but fewer moves.
        if(np < dist_push[st] || (np == dist_push[st] && nm < dist_move[st])) {
            dist_push[st] = np; // Store new push count.
            dist_move[st] = nm; // Store new move count.
            par[st] = from;     // Store predecessor.
            par_dir[st] = dir;  // Store push direction.
            pq.push({np, nm, st}); // Add candidate to priority queue.
        }
    };

    // Try every possible next push from a configuration.
    auto try_pushes = [&](int box, int keeper, int from, int base_push,
                          int base_move) {
        // Compute all cells player can reach while box blocks its cell.
        bfs_dist(keeper, box);

        // Decode current box position.
        int brow = box / cols, bcol = box % cols;

        // Try pushing the box in each of four directions.
        for(int i = 0; i < 4; i++) {
            // Cell where player must stand before pushing.
            int wr = brow - dr[i], wc = bcol - dc[i];

            // Cell where box moves after push.
            int fr = brow + dr[i], fc = bcol + dc[i];

            // Required player cell must be in bounds.
            if(wr < 0 || wr >= rows || wc < 0 || wc >= cols) {
                continue;
            }

            // Box destination must be in bounds.
            if(fr < 0 || fr >= rows || fc < 0 || fc >= cols) {
                continue;
            }

            // Both required player cell and destination cell must be passable.
            if(grid[wr][wc] == '#' || grid[fr][fc] == '#') {
                continue;
            }

            // Encode required player cell.
            int behind = wr * cols + wc;

            // If player cannot reach the required cell, push is impossible.
            if(walk_seen[behind] != walk_timer) {
                continue;
            }

            // Encode new box position.
            int new_box = fr * cols + fc;

            // After pushing direction i, player stands behind the new box.
            int new_state = new_box * 4 + opp[i];

            // Relax successor state.
            relax(
                new_state,
                base_push + 1,
                base_move + walk_dist[behind] + 1,
                from,
                i
            );
        }
    };

    // Generate all possible first pushes from the initial situation.
    try_pushes(start_box, start_keeper, -1, 0, 0);

    // State where the target is first reached.
    int goal_state = -1;

    // Dijkstra loop.
    while(!pq.empty()) {
        // Extract best candidate.
        auto [pp, mm, st] = pq.top();
        pq.pop();

        // Ignore stale queue entries.
        if(pp != dist_push[st] || mm != dist_move[st]) {
            continue;
        }

        // Decode box position and player side.
        int box = st / 4, side = st % 4;

        // If the box is on target, this is optimal.
        if(box == target) {
            goal_state = st;
            break;
        }

        // Recover actual player position from box and side.
        int keeper = (box / cols + dr[side]) * cols + (box % cols + dc[side]);

        // Try all possible next pushes.
        try_pushes(box, keeper, st, pp, mm);
    }

    // If no goal state was found, puzzle is impossible.
    if(goal_state == -1) {
        cout << "Impossible.\n";
        return;
    }

    // Recover chain of push states from goal to start.
    vector<int> chain;
    for(int cur = goal_state; cur != -1; cur = par[cur]) {
        chain.push_back(cur);
    }

    // Reverse to get chronological order.
    reverse(chain.begin(), chain.end());

    // Arrays for BFS path reconstruction.
    vector<int> path_seen(cells, 0), path_par(cells), path_par_dir(cells);

    // Timestamp for path BFS.
    int path_timer = 0;

    // Find one shortest walking path from src to dst avoiding obstacle.
    auto bfs_path = [&](int src, int dst, int obstacle) {
        string moves; // Resulting lowercase walking moves.

        // If already there, no walking needed.
        if(src == dst) {
            return moves;
        }

        // Start new BFS.
        path_timer++;

        // Queue pointers.
        int head = 0, tail = 0;

        // Mark source.
        path_seen[src] = path_timer;

        // Source has no parent.
        path_par[src] = -1;

        // Push source into queue.
        bfs_queue[tail++] = src;

        // Standard BFS.
        while(head < tail) {
            // Pop current cell.
            int cur = bfs_queue[head++];

            // Stop once destination is reached.
            if(cur == dst) {
                break;
            }

            // Decode current cell.
            int cr = cur / cols, cc = cur % cols;

            // Try four directions.
            for(int k = 0; k < 4; k++) {
                int nr = cr + dr[k], nc = cc + dc[k];

                // Skip out-of-bounds cells.
                if(nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    continue;
                }

                // Encode neighbor.
                int ncell = nr * cols + nc;

                // Skip walls and current box cell.
                if(grid[nr][nc] == '#' || ncell == obstacle) {
                    continue;
                }

                // Skip visited cells.
                if(path_seen[ncell] == path_timer) {
                    continue;
                }

                // Mark visited.
                path_seen[ncell] = path_timer;

                // Store parent cell.
                path_par[ncell] = cur;

                // Store direction used to reach this cell.
                path_par_dir[ncell] = k;

                // Push into BFS queue.
                bfs_queue[tail++] = ncell;
            }
        }

        // Reconstruct path backward from destination to source.
        for(int cur = dst; cur != src; cur = path_par[cur]) {
            moves += low[path_par_dir[cur]];
        }

        // Reverse because path was collected backward.
        reverse(moves.begin(), moves.end());

        return moves;
    };

    // Final answer string.
    string result;

    // Process each push state in chronological order.
    for(int st: chain) {
        // Direction of the push that created this state.
        int dir = par_dir[st];

        // Previous state.
        int prev = par[st];

        // Previous box and player positions.
        int prev_box, prev_keeper;

        // If previous is -1, this push came from the initial configuration.
        if(prev == -1) {
            prev_box = start_box;
            prev_keeper = start_keeper;
        } else {
            // Decode previous state.
            int pb = prev / 4, ps = prev % 4;

            // Previous box position.
            prev_box = pb;

            // Previous player position.
            prev_keeper = (pb / cols + dr[ps]) * cols + (pb % cols + dc[ps]);
        }

        // Required cell behind the previous box before pushing in dir.
        int behind =
            (prev_box / cols - dr[dir]) * cols + (prev_box % cols - dc[dir]);

        // Append shortest walking path to push position.
        result += bfs_path(prev_keeper, behind, prev_box);

        // Append the actual push as an uppercase direction.
        result += upp[dir];
    }

    // Print final solution.
    cout << result << "\n";
}

int main() {
    // Speed up C++ IO.
    ios_base::sync_with_stdio(false);

    // Untie cin from cout.
    cin.tie(nullptr);

    // Only one test case.
    int T = 1;

    // Multiple test cases are not used.
    // cin >> T;

    // Process test case.
    for(int test = 1; test <= T; test++) {
        read();  // Read maze.
        solve(); // Solve maze.
    }

    return 0; // Successful termination.
}
```

---

## 4. Python solution with detailed comments

```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.`.