Problem: Imagine an n × m grid with some blocked cells. The top left cell in the grid has coordinates (1, 1) and the bottom right cell has coordinates (n, m). There are k blocked cells in the grid and others are empty. You flash a laser beam from the center of an empty cell (xs, ys) in one of the diagonal directions (i.e. north-east, north-west, south-east or south-west). If the beam hits a blocked cell or the border of the grid it will reflect. The behavior of the beam reflection in different situations is depicted in the figure below. 

<image>

After a while the beam enters an infinite cycle. Count the number of empty cells that the beam goes through at least once. We consider that the beam goes through cell if it goes through its center.

Input

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 105). Each of the next k lines contains two integers xi and yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) indicating the position of the i-th blocked cell. 

The last line contains xs, ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) and the flash direction which is equal to "NE", "NW", "SE" or "SW". These strings denote directions ( - 1, 1), ( - 1, - 1), (1, 1), (1, - 1).

It's guaranteed that no two blocked cells have the same coordinates.

Output

In the only line of the output print the number of empty cells that the beam goes through at least once.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3 3 0
1 2 SW


Output

6


Input

7 5 3
3 3
4 3
5 3
2 1 SE


Output

14

Solution (in JAVA):

Solution:
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AlexFetisov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE_Mirrors solver = new TaskE_Mirrors();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE_Mirrors {
        private TreeSet<TaskE_Mirrors.Point>[][] diagonals;
        private int height;
        private int width;
        private boolean hadFullAngle;
        HashSet<Long> allPoints;
        int otherDir;
        final static String[] directions = new String[]{"NE", "NW", "SE", "SW"};
        final static int[] searchIn = new int[]{1, 0, 0, 1};
        final static int[] dd = new int[]{0, 0, 1, 1};
        final static int[][] dx = new int[2][2];
        final static int[][] dy = new int[2][2];

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            dx[0][0] = -1;
            dy[0][0] = -1;
            dx[0][1] = 1;
            dy[0][1] = 1;

            dx[1][0] = -1;
            dy[1][0] = 1;
            dx[1][1] = 1;
            dy[1][1] = -1;

            height = in.nextInt();
            width = in.nextInt();
            int countObstacles = in.nextInt();

            diagonals = new TreeSet[2][height + width + 5];
            allPoints = new HashSet<Long>();
            for (int j = 0; j < height + width + 5; ++j) {
                diagonals[0][j] = new TreeSet<TaskE_Mirrors.Point>(new Comparator<TaskE_Mirrors.Point>() {

                    public int compare(TaskE_Mirrors.Point o1, TaskE_Mirrors.Point o2) {
                        return o1.x - o2.x;
                    }
                });
                diagonals[1][j] = new TreeSet<TaskE_Mirrors.Point>(new Comparator<TaskE_Mirrors.Point>() {

                    public int compare(TaskE_Mirrors.Point o1, TaskE_Mirrors.Point o2) {
                        return o1.x - o2.x;
                    }
                });
            }

            for (int i = 0; i < countObstacles; ++i) {
                int x = in.nextInt();
                int y = in.nextInt();

                int diagonalCoordinate = height + 1 - x + y;
                int reverseDiagonalCoordinate = x + y;

                allPoints.add((long) x * (width + 2) + y);
                TaskE_Mirrors.Point pp = new TaskE_Mirrors.Point(x, y);
                diagonals[0][diagonalCoordinate].add(pp);
                diagonals[1][reverseDiagonalCoordinate].add(pp);
            }

//        for (int x = 0; x <= height + 1; ++x) {
//            int y = 0;
//
//            int diagonalCoordinate = height + 1 - x + y;
//            int reverseDiagonalCoordinate = x + y;
//
//            Point pp = new Point(x, y);
//            long cc = (long) x * (width + 2) + y;
//
//            allPoints.add(cc);
//            diagonals[0][diagonalCoordinate].add(pp);
//            diagonals[1][reverseDiagonalCoordinate].add(pp);
//
//            y = width + 1;
//
//            pp = new Point(x, y);
//            cc = (long) x * (width + 2) + y;
//
//            diagonalCoordinate = height + 1 - x + y;
//            reverseDiagonalCoordinate = x + y;
//
//            allPoints.add(cc);
//            diagonals[0][diagonalCoordinate].add(pp);
//            diagonals[1][reverseDiagonalCoordinate].add(pp);
//        }
//
//        for (int y = 1; y <= width; ++y) {
//            int x = 0;
//
//            int diagonalCoordinate = height + 1 - x + y;
//            int reverseDiagonalCoordinate = x + y;
//
//            Point pp = new Point(x, y);
//            long cc = ((long) x * (width + 2)) + y;
//
//            allPoints.add(cc);
//            diagonals[0][diagonalCoordinate].add(pp);
//            diagonals[1][reverseDiagonalCoordinate].add(pp);
//
//            x = height + 1;
//
//            pp = new Point(x, y);
//            cc = (long) x * (width + 2) + y;
//
//            diagonalCoordinate = height + 1 - x + y;
//            reverseDiagonalCoordinate = x + y;
//
//            allPoints.add(cc);
//            diagonals[0][diagonalCoordinate].add(pp);
//            diagonals[1][reverseDiagonalCoordinate].add(pp);
//        }

            int x = in.nextInt();
            int y = in.nextInt();
            int sx = x;
            int dirId = getDirection(in.nextString());
            otherDir = dd[dirId];
            int dir = searchIn[dirId];

            hadFullAngle = false;
            int firstX = -1, firstY = -1, firstD = dir, firstODir = otherDir;
            long res = 0;

            while (true) {
                int[] nxy = getNext(x, y, dir);
                int nx = nxy[0];
                int ny = nxy[1];
                if (firstX == nx && firstY == ny && firstD == dir && firstODir == otherDir) {
                    res += getDst(x, sx);
                    break;
                }
                if (firstX == -1) {
                    firstX = nx;
                    firstY = ny;
                }

                res += getDst(x, nx);
                int[] newAll = getNewDir(nx, ny, dir, nxy[2], nxy[3]);
                x = newAll[0];
                y = newAll[1];
                dir = newAll[2];
            }
            --res;
            if (hadFullAngle) {
                res /= 2;
            }
            out.println(res);
        }

        private int[] getNewDir(int nx, int ny, int dir, int ox, int oy) {
            boolean hasOther1 = allPoints.contains(nx * 1L * (width + 2) + oy);
            boolean hasOther2 = allPoints.contains(ox * 1L * (width + 2) + ny);
            hasOther1 |= isBorder(nx, oy);
            hasOther2 |= isBorder(ox, ny);

            if ((hasOther1 && hasOther2) || (!hasOther1 && !hasOther2)) {
                otherDir = 1 - otherDir;
                hadFullAngle = true;
                return new int[]{nx, ny, dir};
            }

            if (!hasOther1) {
                otherDir = 1 - otherDir;
                int px = nx;
                int py = oy;
                int newDir = 1 - dir;
                return new int[]{px, py, newDir};
            } else {
                int px = ox;
                int py = ny;
                int newDir = 1 - dir;
                return new int[]{px, py, newDir};
            }
        }

        private boolean isBorder(int x, int y) {
            return x == 0 || y == 0 || x == height + 1 || y == width + 1;
        }

        private int[] getNext(int x, int y, int dir) {
            int id = height + 1 - x + y;
            if (dir == 1) {
                id = x + y;
            }
            TaskE_Mirrors.Point next;
            if (otherDir == 1) {
                next = diagonals[dir][id].higher(new TaskE_Mirrors.Point(x, y));
            } else {
                next = diagonals[dir][id].lower(new TaskE_Mirrors.Point(x, y));
            }

            if (next == null) {
                int[] nn = getBorder(x, y, dir, otherDir);
                next = new TaskE_Mirrors.Point(nn[0], nn[1]);
            }

            int[] res = new int[4];
            res[2] = next.x;
            res[3] = next.y;

            res[0] = next.x - dx[dir][otherDir];
            res[1] = next.y - dy[dir][otherDir];

            return res;
        }

        private long getDst(int x, int nx) {
            return Math.abs(x - nx) + 1;
        }

        int getDirection(String d) {
            for (int i = 0; i < 4; ++i) {
                if (d.compareTo(directions[i]) == 0) {
                    return i;
                }
            }
            return -1;
        }

        int[] getBorder(int x, int y, int dir, int otherDir) {
            if (otherDir == 1) {
                if (dir == 0) {
                    int addLen = Math.min(height + 1 - x, width + 1 - y);
                    x += addLen;
                    y += addLen;
                } else {
                    int addLen = Math.min(height + 1 - x, y);
                    x += addLen;
                    y -= addLen;
                }
            } else {
                if (dir == 0) {
                    int addLen = Math.min(x, y);
                    x -= addLen;
                    y -= addLen;
                } else {
                    int addLen = Math.min(x, width + 1 - y);
                    x -= addLen;
                    y += addLen;
                }
            }
            return new int[]{x, y};
        }

        class Point {
            int x;
            int y;

            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }

        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }
}