#exawizards2019f. [exawizards2019_f]More Realistic Manhattan Distance
[exawizards2019_f]More Realistic Manhattan Distance
Problem Statement
In Takaha-shi, the capital of Republic of AtCoder, there are roads extending east and west, and roads extending north and south. There are no other roads. The -th east-west road from the north and the -th north-south road from the west cross at the intersection . Two east-west roads do not cross, nor do two north-south roads. The distance between two adjacent roads in the same direction is .
Each road is one-way; one can only walk in one direction. The permitted direction for each road is described by a string of length and a string of length , as follows:
- If the -th character in is
W
, one can only walk westward along the -th east-west road from the north; - If the -th character in is
E
, one can only walk eastward along the -th east-west road from the north; - If the -th character in is
N
, one can only walk northward along the -th north-south road from the west; - If the -th character in is
S
, one can only walk southward along the -th south-west road from the west.
Process the following queries:
- In the -th query, and are given. What is the minimum distance to travel to reach the intersection from the intersection by walking along the roads?
Constraints
- consists of
W
andE
. - consists of
N
andS
.
Input
Input is given from Standard Input in the following format:
Output
In the -th line, print the response to the -th query. If the intersection cannot be reached from the intersection by walking along the roads, print -1
instead.
Sample Input 1
Sample Output 1
The permitted direction for each road is shown in the following figure (north upward):
For each of the four queries, a route that achieves the minimum travel distance is as follows:
Sample Input 2
Sample Output 2
The travel may be impossible.