Problem: traffic_control (2021 round1)

In the rapidly growing towns of Silicon Valley, traffic congestion is becoming a major problem. The governor has contracted Travis, the rock star traffic engineer, to come up with some solutions.

A town consists of \(N\) horizontal streets and \(M\) vertical avenues, making up \(N*M\) intersections. Each intersection has some wait time, which is an integer number of seconds between \(1\) and \(1{,}000\), inclusive. The town's wait times can thus be represented as a grid with \(N\) rows and \(M\) columns of integers.

A *route* within the grid consists of a sequence of one or more intersections, such that each pair of consecutive intersections are either horizontally or vertically adjacent to one another. The *duration* of a route is the sum of all of its intersections' wait times.

Travis is tasked with assigning valid wait times for all \(N*M\) intersections. However, he must be careful in his choices. Routes too slow will lead to congestion, and routes too fast will lead to accidents. After careful calculations, Travis has determined that that an optimal grid must simultaneously satisfy the following two benchmark conditions based off the four corners of the town:

1. The duration of the fastest route starting in the top-left intersection and ending in the bottom-right one is exactly \(A\) seconds, and
2. the duration of the fastest route starting in the top-right intersection and ending in the bottom-left one is exactly \(B\) seconds.

Please help Travis generate any such valid grid, or determine that no such grid exists.


# Constraints

\(1 \le T \le 40\)
\(2 \le N, M \le 50\)
\(1 \le A, B \le 1000\)

The sum of \(N*M\) across all towns is at most \(40{,}000\).


# Input

Input begins with an integer \(T\), the number of towns that Travis is contracted for. For each town, there is a single line containing the \(4\) space-separated integers \(N\), \(M\), \(A\), and \(B\).


# Output

For the \(i\)th town, first print a line containing *"Case #i: "* followed by either the string "Possible" or "Impossible". If possible, this should be followed \(N\) rows of \(M\) space-separated integers each, comprising your chosen grid of intersection wait times in seconds.


# Sample Explanation

In the first town, the following is one possible grid for which the minimum durations of routes from the top-left to the bottom-right intersection, as well as from the top-right to the bottom-left intersection, are each equal to \(333 + 333 + 333 = 999\) seconds (as required):

```
  333 333
  333 333
```

In the second town, the following is one possible grid satisfying the requirements:

```
  5 3 1
  3 4 3
```

For example, the fastest route from the top-left to the bottom-right intersection involves moving right, then right, then down, for a total duration of \(5 + 3 + 1 + 3 = 12\) seconds. Meanwhile, the fastest route from the top-right to the bottom-left intersection has a duration of \(1 + 3 + 4 + 3 = 11\) seconds.

**For each of the first \(3\) towns, other outputs would also be accepted.**


Sample input:
4
2 2 999 999
2 3 12 11
4 3 6 6
50 50 1 1


Sample output:
Case #1: Possible
333 333
333 333
Case #2: Possible
5 3 1
3 4 3
Case #3: Possible
1 1 1
1 2 1
1 2 1
1 1 1
Case #4: Impossible


Solution: Any path from one corner of the grid to the opposite corner must include at least \(K = N + M - 1\) cells and therefore have a minimum duration of \(K\). Therefore, if \(A < K\) or \(B < K\), no valid grid exists.

Otherwise, consider a grid with a wait time of \(A - (N + M - 2)\) for the top-left cell, a wait time of \(B - (N + M - 2)\) for the top-right cell, and wait times of \(1\) for all remaining cells. In such a grid, the minimum duration of a path from the top-left to the bottom-right corner includes the top-left cell along with \(K - 1\) cells with wait times of \(1\), for a total of \(A - (N + M - 2) + (N + M - 2) = A\). The minimum duration of a path from the top-right to the bottom-left corner is similarly \(B\). Therefore, such a grid constitutes a valid output.

[See David Harmeyer's solution video here](https://youtu.be/R4ooAlRc93Y).


Code: #include <iostream>
using namespace std;

int N, M, A, B;

void solve() {
  cin >> N >> M >> A >> B;
  A -= N + M - 2;
  B -= N + M - 2;
  if (A < 1 || B < 1) {
    cout << "Impossible" << endl;
    return;
  }
  cout << "Possible" << endl;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      int ans = (!i && !j) ? A : (!i && j == M - 1) ? B : 1;
      cout << ans << (j < M - 1 ? ' ' : '\n');
    }
  }
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": ";
    solve();
  }
  return 0;
}