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

522. Oil Wells
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

These are tough times for Berland nowadays. State property is being sold piece by piece, and even state oil company "BerOil" hasn't escaped the common lot.

A well-known entrepreneur Tapochkin decided to buy a piece of "BerOil"'s land. Tapochkin is very smart, so he wants to buy a piece of land that will contain all of the company's oil wells within its area or on its border. He has already bought a fence building machine that will move along the border of Tapochkin's new land and build a high fence! There is only one problem — the machine is defective.

Normally, the machine can move in any of the four directions: "north", "east", "south" and "west". Now, when it's broken, the situation is a bit different. Before the engine is turned on, the driver divides these four directions into two groups — two perpendicular directions in each group (e.g. "north" and "east" in one group, "south" and "west" in the other group). Then for some time the machine moves using only directions from the first group, after that — only directions from the second group. It's the driver who determines the moment of switching from one group to the other one.

The company's territory is split into equal squares by a system of roads. Half of the roads go in "north-south" direction, the other half — in "east-west" direction. The company has a vast territory that can be regarded as infinite. The roads form a square grid, each square of the grid has a side length equal to 1 km. Oil wells are located on the crossroads and their size is negligible, so they can be considered points.

Cartesian coordinate system can be applied to the company's territory, so that Ox axis is directed west-to-east, and Oy axis — south-to-north. Unit of length — 1 km. Initial position of the machine and coordinates of the oil wells are known. Find the area of the smallest possible piece of land that the machine can fence around, leaving all the oil wells inside the fenced area or on its border. Also, find the sequence of machine's movements. The border of Tapochkin's piece of land should be a closed non-degenerate polyline that doesn't cross or touch itself.

Input
The first line of input contains three integers n, x0 and y0 (1 ≤ n ≤ 400, -400 ≤ x0,y0 ≤ 400), where n — amount of oil wells, (x0,y0) — initial position of the fence building machine. The following n lines contain coordinates of the wells xi, yi (-400 ≤ xi,yi ≤ 400). No two wells have identical coordinates.

Output
Print the only number -1 to the output, if there is no solution. Otherwise print the area of Tapochkin's land in square kilometers to the first line, and the path of the fence building machine — to the second. The path of the machine is a sequence of characters "W", "N", "E" and "S", standing for movements one kilometer "west", "north", "east" or "south" correspondingly. You are allowed to print the path in any direction of driving — clockwise or counterclockwise, as it doesn't really change the closed polyline which the path represents. It there is more than one answer, you may print any of them.

Example(s)
sample input
sample output
3 4 2
5 6
7 2
9 4
13
NENNNEEEESSWWSSWWW

sample input
sample output
2 1 -2
-1 2
1 -2
5
NWNNNWSSSSEE

sample input
sample output
1 1 2
1 2
1
ESWN

<|response|>
## 1. Abridged problem statement

We are given `n` oil wells on integer grid points and the initial position of a fence-building machine.

The machine must build a closed, simple, non-degenerate polygon along grid edges. The polygon must contain all wells inside or on its border.

The machine is defective: its route must consist of two phases. In the first phase it may use only two perpendicular directions, and after one switch it may use only the opposite two directions.

Example:

```text
phase 1: N/E
phase 2: S/W
```

Find the minimum possible area and output any valid route, or `-1` if no such route exists.

---

## 2. Key observations needed to solve the problem

### Observation 1 — The route consists of two monotone staircases

Suppose the first phase uses `N` and `E`.

Then the machine starts at some point, moves monotonically northeast to some opposite corner, and then returns using only `S` and `W`.

So the polygon boundary consists of two monotone staircase paths between the same two endpoints.

There are four possible orientations:

```text
N/E then S/W
N/W then S/E
S/E then N/W
S/W then N/E
```

We can try all four.

---

### Observation 2 — For one orientation, all wells must lie in one quadrant

After shifting the start point to `(0, 0)`, consider the orientation `N/E` then `S/W`.

The whole polygon lies in the first quadrant, so every well must satisfy:

```text
x >= 0
y >= 0
```

For other orientations we can mirror coordinates.

For example:

```text
sx = -1 means mirror x
sy = -1 means mirror y
```

After mirroring, we always solve the same normalized case: first phase uses `N/E`.

---

### Observation 3 — The opposite corner can be chosen minimally

For one normalized orientation, let:

```text
a = max(max well x, 1)
b = max(max well y, 1)
```

The opposite corner of the two staircases can be chosen as `(a, b)`.

Both `a` and `b` must be at least `1`, otherwise the polygon would be degenerate.

---

### Observation 4 — Represent staircases by horizontal step heights

For every column `x = 0 ... a - 1`, define:

```text
upper[x] = y-coordinate of the upper path's east step in column x
lower[x] = y-coordinate of the lower path's east step in column x
```

Both arrays must be non-decreasing because the paths only move north and east.

The area is:

```text
sum(upper[x] - lower[x])
```

---

### Observation 5 — Greedy construction is optimal

The upper path increases area, so we want it as low as possible.

The lower path decreases area, so we want it as high as possible.

Therefore:

1. Construct the lowest valid `upper`.
2. Construct the highest valid `lower`.

This gives the minimum area for that orientation.

---

## 3. Full solution approach based on the observations

For each of the four orientations:

1. Shift all wells relative to the start.
2. Mirror coordinates according to the orientation.
3. If some well has negative `x` or `y`, this orientation is impossible.
4. Let:

```text
a = max(max_x, 1)
b = max(max_y, 1)
```

5. Construct the upper staircase.

For every column, store the highest well in that column:

```text
need_upper[x] = maximum y among wells with coordinate x
```

Then:

```text
upper[0] = max(1, need_upper[0])

for x = 1 ... a - 1:
    upper[x] = max(upper[x - 1], need_upper[x])
```

Finally, force:

```text
upper[a - 1] = b
```

The value `upper[0] >= 1` ensures that the upper path starts with a north step.

---

6. Construct the lower staircase.

The lower path must satisfy:

```text
lower[0] = 0
```

This ensures the lower path starts with an east step.

For every `x > 0`, we need:

```text
lower[x] <= upper[x - 1] - 1
```

This prevents the two paths from touching at interior vertical grid lines.

Also, for every well strictly to the right of column `x`, we need:

```text
lower[x] <= well_y
```

Otherwise that well would be below the lower boundary.

At the last column, we also need:

```text
lower[a - 1] <= b - 1
```

so that the lower path ends with a north step.

We greedily choose the maximum possible value for `lower[x]`.

---

7. Compute the area:

```text
area = sum(upper[x] - lower[x])
```

8. Build the path:

- Build the upper path from `(0, 0)` to `(a, b)` using `N/E`.
- Build the lower path from `(0, 0)` to `(a, b)` using `N/E`.
- Append the reverse of the lower path, changing:

```text
N -> S
E -> W
```

9. Convert directions back according to the mirroring.

10. Keep the best answer among all four orientations.

If no orientation works, output `-1`.

Complexity is small:

```text
O(4 * (n + a + b))
```

Here `a, b <= 800`, because coordinates are between `-400` and `400`.

---

## 4. 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;
};

int n;
int start_x, start_y;
vector<pair<int, int>> wells;

void read() {
    cin >> n >> start_x >> start_y;
    wells.resize(n);
    for(auto& w: wells) {
        cin >> w;
    }
}

void solve() {
    // Pure implementation. The driver picks two perpendicular directions for
    // phase 1 and the other two for phase 2, so the closed path is bounded by
    // two monotone staircases between the start (treated as origin) and the
    // opposite corner (a, b). The polygon therefore lives in one of the four
    // quadrants relative to the start. For each of the four orientations, we
    // mirror the wells into the first quadrant and look for the smallest
    // staircase polygon containing them.
    //
    // With wells in the first quadrant, set a = max(max_x, 1), b = max(max_y,
    // 1). Describe each staircase by the y-coordinate of its E-step in each
    // column: f_upper(x) for the upper boundary, f_lower(x) for the lower one,
    // both non-decreasing. Wells (xi, yi) require f_upper(xi) >= yi for xi < a
    // (well lies below/on upper path) and f_lower(xi - 1) <= yi for xi > 0
    // (well lies above/on lower path). For the polyline to be simple, the
    // upper path takes its first step N and its last step E (so f_upper(0) >=
    // 1 and f_upper(a - 1) = b), the lower path takes its first step E and
    // its last step N (so f_lower(0) = 0 and f_lower(a - 1) <= b - 1), and
    // for every interior column x in {1, ..., a - 1} the vertical segments
    // do not touch, i.e. f_lower(x) <= f_upper(x - 1) - 1.
    //
    // Greedy is optimal: pick f_upper as the smallest non-decreasing staircase
    // satisfying its lower bounds, then pick f_lower as the largest
    // non-decreasing staircase satisfying its upper bounds (which now include
    // the f_upper-dependent simple-polygon constraint). Increasing f_upper(x -
    // 1) only loosens the constraint on f_lower(x) by the same amount, so it
    // can never decrease the area. Try all four orientations and keep the
    // best; if none works, output -1.

    vector<pair<int, int>> shifted(n);
    for(int i = 0; i < n; i++) {
        shifted[i] = {wells[i].first - start_x, wells[i].second - start_y};
    }

    auto try_orientation = [&](int sx, int sy) -> pair<int64_t, string> {
        vector<pair<int, int>> w(n);
        for(int i = 0; i < n; i++) {
            w[i] = {sx * shifted[i].first, sy * shifted[i].second};
            if(w[i].first < 0 || w[i].second < 0) {
                return {LLONG_MAX, ""};
            }
        }

        int max_x = 0, max_y = 0;
        for(auto p: w) {
            max_x = max(max_x, p.first);
            max_y = max(max_y, p.second);
        }
        int a = max(max_x, 1);
        int b = max(max_y, 1);

        vector<int> max_y_at_col(a, -1);
        for(auto p: w) {
            if(p.first < a) {
                max_y_at_col[p.first] = max(max_y_at_col[p.first], p.second);
            }
        }

        vector<int> min_y_strictly_right(a, INT_MAX);
        for(auto p: w) {
            for(int xp = 0; xp < p.first && xp < a; xp++) {
                min_y_strictly_right[xp] =
                    min(min_y_strictly_right[xp], p.second);
            }
        }

        vector<int> f_upper(a, 0);
        f_upper[0] = max(1, max_y_at_col[0]);
        for(int x = 1; x < a; x++) {
            int wells_here = max(0, max_y_at_col[x]);
            f_upper[x] = max(f_upper[x - 1], wells_here);
        }
        f_upper[a - 1] = max(f_upper[a - 1], b);
        if(f_upper[a - 1] != b) {
            return {LLONG_MAX, ""};
        }

        vector<int> f_lower(a, 0);
        f_lower[0] = 0;
        for(int x = 1; x < a; x++) {
            int ub = f_upper[x - 1] - 1;
            if(min_y_strictly_right[x] != INT_MAX) {
                ub = min(ub, min_y_strictly_right[x]);
            }
            if(x == a - 1) {
                ub = min(ub, b - 1);
            }
            if(ub < f_lower[x - 1]) {
                return {LLONG_MAX, ""};
            }
            f_lower[x] = ub;
        }

        int64_t area = 0;
        for(int x = 0; x < a; x++) {
            area += f_upper[x] - f_lower[x];
        }
        if(area <= 0) {
            return {LLONG_MAX, ""};
        }

        string path;
        int prev = 0;
        for(int x = 0; x < a; x++) {
            for(int i = 0; i < f_upper[x] - prev; i++) {
                path += 'N';
            }
            path += 'E';
            prev = f_upper[x];
        }

        string lower_path;
        prev = 0;
        for(int x = 0; x < a; x++) {
            for(int i = 0; i < f_lower[x] - prev; i++) {
                lower_path += 'N';
            }
            lower_path += 'E';
            prev = f_lower[x];
        }
        for(int i = 0; i < b - prev; i++) {
            lower_path += 'N';
        }
        for(int i = (int)lower_path.size() - 1; i >= 0; i--) {
            path += (lower_path[i] == 'N' ? 'S' : 'W');
        }

        string result;
        for(char c: path) {
            char d = c;
            if(c == 'N') {
                d = (sy == 1 ? 'N' : 'S');
            } else if(c == 'S') {
                d = (sy == 1 ? 'S' : 'N');
            } else if(c == 'E') {
                d = (sx == 1 ? 'E' : 'W');
            } else if(c == 'W') {
                d = (sx == 1 ? 'W' : 'E');
            }
            result += d;
        }

        return {area, result};
    };

    pair<int64_t, string> best = {LLONG_MAX, ""};
    for(int sx: {1, -1}) {
        for(int sy: {1, -1}) {
            auto r = try_orientation(sx, sy);
            if(r.first < best.first) {
                best = r;
            }
        }
    }

    if(best.first == LLONG_MAX) {
        cout << -1 << '\n';
    } else {
        cout << best.first << '\n' << best.second << '\n';
    }
}

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

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

    return 0;
}
```

---

## 5. Python Solution

```python
import sys


def solve():
    # Read all integers from input.
    data = list(map(int, sys.stdin.read().split()))

    # First three integers are n and starting coordinates.
    n = data[0]
    start_x = data[1]
    start_y = data[2]

    # Read well coordinates.
    wells = []
    idx = 3
    for _ in range(n):
        x = data[idx]
        y = data[idx + 1]
        idx += 2
        wells.append((x, y))

    # Shift wells so that the machine start becomes (0, 0).
    shifted = [(x - start_x, y - start_y) for x, y in wells]

    # Large value representing impossible answer.
    INF = 10**30

    def try_orientation(sx, sy):
        """
        Try one orientation.

        sx = 1 means positive x is east.
        sx = -1 means positive x is west.

        sy = 1 means positive y is north.
        sy = -1 means positive y is south.

        After multiplying by sx and sy, we solve only the first-quadrant case.
        """

        # Mirrored coordinates.
        w = []

        for x, y in shifted:
            nx = sx * x
            ny = sy * y

            # In this orientation, all wells must be in the first quadrant.
            if nx < 0 or ny < 0:
                return INF, ""

            w.append((nx, ny))

        # Determine farthest well coordinates.
        max_x = max((x for x, _ in w), default=0)
        max_y = max((y for _, y in w), default=0)

        # Opposite corner of the staircase polygon.
        # Width and height must be at least 1.
        a = max(max_x, 1)
        b = max(max_y, 1)

        # max_y_at_col[x] is the highest well exactly in column x.
        # This constrains the upper path.
        max_y_at_col = [-1] * a

        for x, y in w:
            # Wells at x == a lie on the right boundary.
            if x < a:
                if y > max_y_at_col[x]:
                    max_y_at_col[x] = y

        # min_y_strictly_right[x] is the minimum y among wells with well_x > x.
        # This constrains how high the lower path may be.
        BIG = 10**9
        min_y_strictly_right = [BIG] * a

        for x, y in w:
            # This well restricts every lower-path column strictly to its left.
            limit = min(x, a)
            for xp in range(limit):
                if y < min_y_strictly_right[xp]:
                    min_y_strictly_right[xp] = y

        # Build the lowest valid upper path.
        f_upper = [0] * a

        # Upper path must begin with a north step and cover wells in column 0.
        f_upper[0] = max(1, max_y_at_col[0])

        for x in range(1, a):
            # Required height due to wells in this column.
            wells_here = max(0, max_y_at_col[x])

            # Staircase height cannot decrease.
            f_upper[x] = max(f_upper[x - 1], wells_here)

        # Last upper horizontal step must be at height b.
        f_upper[a - 1] = max(f_upper[a - 1], b)

        # If it became greater than b, impossible.
        if f_upper[a - 1] != b:
            return INF, ""

        # Build the highest valid lower path.
        f_lower = [0] * a

        # Lower path starts with an east move from height 0.
        f_lower[0] = 0

        for x in range(1, a):
            # To avoid touching upper path.
            ub = f_upper[x - 1] - 1

            # To keep wells to the right above or on lower path.
            if min_y_strictly_right[x] != BIG:
                ub = min(ub, min_y_strictly_right[x])

            # Last column must leave space for final north move.
            if x == a - 1:
                ub = min(ub, b - 1)

            # Lower path must be non-decreasing.
            if ub < f_lower[x - 1]:
                return INF, ""

            # Choose highest possible value to minimize area.
            f_lower[x] = ub

        # Compute polygon area.
        area = 0
        for x in range(a):
            area += f_upper[x] - f_lower[x]

        # Non-degenerate polygon must have positive area.
        if area <= 0:
            return INF, ""

        # Construct upper path in normalized N/E coordinates.
        path = []
        prev = 0

        for x in range(a):
            # Move north up to f_upper[x].
            path.extend("N" for _ in range(f_upper[x] - prev))

            # Move east one column.
            path.append("E")

            # Update current height.
            prev = f_upper[x]

        # Construct lower path from (0,0) to (a,b), also using N/E.
        lower_path = []
        prev = 0

        for x in range(a):
            # Move north up to f_lower[x].
            lower_path.extend("N" for _ in range(f_lower[x] - prev))

            # Move east one column.
            lower_path.append("E")

            # Update current height.
            prev = f_lower[x]

        # Finish lower path by moving north to height b.
        lower_path.extend("N" for _ in range(b - prev))

        # Return along the reverse of lower path.
        # Reverse N -> S and E -> W.
        for c in reversed(lower_path):
            if c == "N":
                path.append("S")
            else:
                path.append("W")

        # Convert directions back from normalized orientation.
        result = []

        for c in path:
            if c == "N":
                result.append("N" if sy == 1 else "S")
            elif c == "S":
                result.append("S" if sy == 1 else "N")
            elif c == "E":
                result.append("E" if sx == 1 else "W")
            else:  # c == "W"
                result.append("W" if sx == 1 else "E")

        return area, "".join(result)

    # Try all four orientations.
    best_area = INF
    best_path = ""

    for sx in (1, -1):
        for sy in (1, -1):
            area, path = try_orientation(sx, sy)

            if area < best_area:
                best_area = area
                best_path = path

    # Output answer.
    if best_area == INF:
        print(-1)
    else:
        print(best_area)
        print(best_path)


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