<|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++ implementation with detailed comments

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

const int INF = 1e9;

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

    int n;
    int x0, y0;
    cin >> n >> x0 >> y0;

    vector<pair<int, int>> wells(n);

    for (int i = 0; i < n; i++) {
        cin >> wells[i].first >> wells[i].second;
    }

    // Shift wells so that the machine starts at (0, 0).
    vector<pair<int, int>> shifted(n);

    for (int i = 0; i < n; i++) {
        shifted[i] = {
            wells[i].first - x0,
            wells[i].second - y0
        };
    }

    /*
        Try one orientation.

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

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

        After applying these signs, we solve the normalized case:
        first phase uses N/E, second phase uses S/W.
    */
    auto try_orientation = [&](int sx, int sy) -> pair<long long, string> {
        vector<pair<int, int>> p(n);

        for (int i = 0; i < n; i++) {
            int x = sx * shifted[i].first;
            int y = sy * shifted[i].second;

            // All wells must lie in the first quadrant.
            if (x < 0 || y < 0) {
                return {LLONG_MAX, ""};
            }

            p[i] = {x, y};
        }

        int max_x = 0;
        int max_y = 0;

        for (auto [x, y] : p) {
            max_x = max(max_x, x);
            max_y = max(max_y, y);
        }

        // Opposite corner of the staircase polygon.
        int a = max(max_x, 1);
        int b = max(max_y, 1);

        /*
            need_upper[x] stores the highest well in column x.

            If a well has x == a, it lies on the right border,
            so it does not force an upper horizontal step.
        */
        vector<int> need_upper(a, -1);

        for (auto [x, y] : p) {
            if (x < a) {
                need_upper[x] = max(need_upper[x], y);
            }
        }

        /*
            For lower path constraints, we need to know:

            min_y_strictly_right[x] =
                minimum y among wells with well_x > x

            We compute this using suffix minima.
        */
        vector<int> min_y_at_x(a + 1, INF);

        for (auto [x, y] : p) {
            // x is always between 0 and a.
            min_y_at_x[x] = min(min_y_at_x[x], y);
        }

        vector<int> suffix_min(a + 2, INF);

        for (int x = a; x >= 0; x--) {
            suffix_min[x] = min(min_y_at_x[x], suffix_min[x + 1]);
        }

        // Construct the lowest possible upper path.
        vector<int> upper(a, 0);

        // Upper path must start with a north step.
        upper[0] = max(1, need_upper[0]);

        for (int x = 1; x < a; x++) {
            int required = max(0, need_upper[x]);
            upper[x] = max(upper[x - 1], required);
        }

        // The last east step of the upper path must be at height b.
        upper[a - 1] = max(upper[a - 1], b);

        // If it exceeded b, ending at (a, b) would be impossible.
        if (upper[a - 1] != b) {
            return {LLONG_MAX, ""};
        }

        // Construct the highest possible lower path.
        vector<int> lower(a, 0);

        // Lower path must start with an east step.
        lower[0] = 0;

        for (int x = 1; x < a; x++) {
            /*
                To avoid touching the upper path at vertical line x:

                lower[x] <= upper[x - 1] - 1
            */
            int ub = upper[x - 1] - 1;

            /*
                Wells strictly to the right of x must not lie below
                the lower path.
            */
            int min_right = suffix_min[x + 1];

            if (min_right != INF) {
                ub = min(ub, min_right);
            }

            // Last column must leave room for a final north step.
            if (x == a - 1) {
                ub = min(ub, b - 1);
            }

            // lower must be non-decreasing.
            if (ub < lower[x - 1]) {
                return {LLONG_MAX, ""};
            }

            // Choose the maximum possible value to minimize area.
            lower[x] = ub;
        }

        // Compute area.
        long long area = 0;

        for (int x = 0; x < a; x++) {
            area += upper[x] - lower[x];
        }

        if (area <= 0) {
            return {LLONG_MAX, ""};
        }

        // Build upper path from (0, 0) to (a, b).
        string path;
        int current_y = 0;

        for (int x = 0; x < a; x++) {
            while (current_y < upper[x]) {
                path += 'N';
                current_y++;
            }

            path += 'E';
        }

        // Build lower path from (0, 0) to (a, b).
        string lower_path;
        current_y = 0;

        for (int x = 0; x < a; x++) {
            while (current_y < lower[x]) {
                lower_path += 'N';
                current_y++;
            }

            lower_path += 'E';
        }

        // Finish lower path by moving north to height b.
        while (current_y < b) {
            lower_path += 'N';
            current_y++;
        }

        /*
            Return along the reverse of the lower path.

            Reverse directions:
            N -> S
            E -> W
        */
        for (int i = (int)lower_path.size() - 1; i >= 0; i--) {
            if (lower_path[i] == 'N') {
                path += 'S';
            } else {
                path += 'W';
            }
        }

        // Convert normalized directions back to the original orientation.
        string result;

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

        return {area, result};
    };

    long long best_area = LLONG_MAX;
    string best_path;

    // Try all four quadrant orientations.
    for (int sx : {1, -1}) {
        for (int sy : {1, -1}) {
            auto [area, path] = try_orientation(sx, sy);

            if (area < best_area) {
                best_area = area;
                best_path = path;
            }
        }
    }

    if (best_area == LLONG_MAX) {
        cout << -1 << '\n';
    } else {
        cout << best_area << '\n';
        cout << best_path << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    data = list(map(int, sys.stdin.read().split()))

    n = data[0]
    x0 = data[1]
    y0 = data[2]

    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 starts at (0, 0).
    shifted = [(x - x0, y - y0) for x, y in wells]

    INF = 10**30

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

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

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

        After applying signs, we solve the normalized case:
        first phase uses N/E, second phase uses S/W.
        """

        points = []

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

            # All wells must lie in the first quadrant.
            if nx < 0 or ny < 0:
                return INF, ""

            points.append((nx, ny))

        max_x = max(x for x, _ in points)
        max_y = max(y for _, y in points)

        # Opposite corner of the staircase polygon.
        a = max(max_x, 1)
        b = max(max_y, 1)

        # need_upper[x] is the highest well in column x.
        need_upper = [-1] * a

        for x, y in points:
            # Wells at x == a lie on the right boundary.
            if x < a:
                need_upper[x] = max(need_upper[x], y)

        """
        For lower path constraints, compute:

        suffix_min[x] =
            minimum y among wells with coordinate >= x

        Then wells strictly to the right of column x have:
            suffix_min[x + 1]
        """
        BIG = 10**9

        min_y_at_x = [BIG] * (a + 1)

        for x, y in points:
            min_y_at_x[x] = min(min_y_at_x[x], y)

        suffix_min = [BIG] * (a + 2)

        for x in range(a, -1, -1):
            suffix_min[x] = min(min_y_at_x[x], suffix_min[x + 1])

        # Construct the lowest possible upper path.
        upper = [0] * a

        # Upper path must start with a north step.
        upper[0] = max(1, need_upper[0])

        for x in range(1, a):
            required = max(0, need_upper[x])
            upper[x] = max(upper[x - 1], required)

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

        if upper[a - 1] != b:
            return INF, ""

        # Construct the highest possible lower path.
        lower = [0] * a

        # Lower path must start with an east step.
        lower[0] = 0

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

            # Wells strictly to the right must not be below lower[x].
            min_right = suffix_min[x + 1]

            if min_right != BIG:
                ub = min(ub, min_right)

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

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

            # Choose the maximum possible value to minimize area.
            lower[x] = ub

        # Compute area.
        area = sum(upper[x] - lower[x] for x in range(a))

        if area <= 0:
            return INF, ""

        # Build upper path from (0, 0) to (a, b).
        path = []
        current_y = 0

        for x in range(a):
            while current_y < upper[x]:
                path.append("N")
                current_y += 1

            path.append("E")

        # Build lower path from (0, 0) to (a, b).
        lower_path = []
        current_y = 0

        for x in range(a):
            while current_y < lower[x]:
                lower_path.append("N")
                current_y += 1

            lower_path.append("E")

        # Finish lower path by moving north to height b.
        while current_y < b:
            lower_path.append("N")
            current_y += 1

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

        # Convert normalized directions back to original directions.
        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:
                result.append("W" if sx == 1 else "E")

        return area, "".join(result)

    best_area = INF
    best_path = ""

    # Try all four possible quadrant orientations.
    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

    if best_area == INF:
        print(-1)
    else:
        print(best_area)
        print(best_path)


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