{"problem":{"name":"More Realistic Manhattan Distance","description":{"content":"In Takaha-shi, the capital of Republic of AtCoder, there are $N$ roads extending east and west, and $M$ roads extending north and south. There are no other roads. The $i$\\-th east-west road from the n","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"exawizards2019_f"},"statements":[{"statement_type":"Markdown","content":"In Takaha-shi, the capital of Republic of AtCoder, there are $N$ roads extending east and west, and $M$ roads extending north and south. There are no other roads. The $i$\\-th east-west road from the north and the $j$\\-th north-south road from the west cross at the intersection $(i, j)$. Two east-west roads do not cross, nor do two north-south roads. The distance between two adjacent roads in the same direction is $1$.\nEach road is one-way; one can only walk in one direction. The permitted direction for each road is described by a string $S$ of length $N$ and a string $T$ of length $M$, as follows:\n\n*   If the $i$\\-th character in $S$ is `W`, one can only walk westward along the $i$\\-th east-west road from the north;\n*   If the $i$\\-th character in $S$ is `E`, one can only walk eastward along the $i$\\-th east-west road from the north;\n*   If the $i$\\-th character in $T$ is `N`, one can only walk northward along the $i$\\-th north-south road from the west;\n*   If the $i$\\-th character in $T$ is `S`, one can only walk southward along the $i$\\-th south-west road from the west.\n\nProcess the following $Q$ queries:\n\n*   In the $i$\\-th query, $a_i, b_i, c_i$ and $d_i$ are given. What is the minimum distance to travel to reach the intersection $(c_i, d_i)$ from the intersection $(a_i, b_i)$ by walking along the roads?\n\n## Constraints\n\n*   $2 \\leq N \\leq 100000$\n*   $2 \\leq M \\leq 100000$\n*   $2 \\leq Q \\leq 200000$\n*   $|S| = N$\n*   $S$ consists of `W` and `E`.\n*   $|T| = M$\n*   $T$ consists of `N` and `S`.\n*   $1 \\leq a_i \\leq N$\n*   $1 \\leq b_i \\leq M$\n*   $1 \\leq c_i \\leq N$\n*   $1 \\leq d_i \\leq M$\n*   $(a_i, b_i) \\neq (c_i, d_i)$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$S$\n$T$\n$a_1$ $b_1$ $c_1$ $d_1$\n$a_2$ $b_2$ $c_2$ $d_2$\n$:$\n$a_Q$ $b_Q$ $c_Q$ $d_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"exawizards2019_f","tags":[],"sample_group":[["4 5 4\nEEWW\nNSNNS\n4 1 1 4\n1 3 1 2\n4 2 3 2\n3 3 3 5","6\n11\n5\n4\n\nThe permitted direction for each road is shown in the following figure (north upward):\n![image](https://img.atcoder.jp/exawizards2019/bfb8c54cc4098353946320d8c263807e.png)\nFor each of the four queries, a route that achieves the minimum travel distance is as follows:\n![image](https://img.atcoder.jp/exawizards2019/d1918596004a23a20aa138e591e0ee99.png)"],["3 3 2\nEEE\nSSS\n1 1 3 3\n3 3 1 1","4\n-1\n\nThe travel may be impossible."],["9 7 10\nEEEEEWEWW\nNSSSNSN\n4 6 9 2\n3 7 6 7\n7 5 3 5\n1 1 8 1\n4 3 5 4\n7 4 6 4\n2 5 8 6\n6 6 2 7\n2 4 7 5\n7 2 9 7","9\n-1\n4\n9\n2\n3\n7\n7\n6\n-1"]],"created_at":"2026-03-03 11:01:14"}}