Farmer John's Cow Bell Search

Farmer John has lost his favorite cow bell and Bessie the cow is on the case! They start at different locations and follow distinct paths on the farm. At each time step, either can move one step in the direction indicated by their respective path or choose to wait. Their radios consume energy at each time step (except at the very beginning) equal to the square of the Euclidean distance between them.

The energy consumed at a step is given by \( (x_F - x_B)^2 + (y_F - y_B)^2 \), where \( (x_F, y_F) \) and \( (x_B, y_B) \) are the coordinates of Farmer John and Bessie, respectively.

Your task is to plan a joint movement strategy so that both reach the end of their paths while minimizing the total energy consumed.

inputFormat

The input consists of five lines:

• The first line contains two integers \(N\) and \(M\), representing the number of steps in Farmer John's and Bessie's paths, respectively.
• The second line contains two integers \(f_x\) and \(f_y\), the starting coordinates of Farmer John.
• The third line contains two integers \(b_x\) and \(b_y\), the starting coordinates of Bessie.
• The fourth line contains a string of length \(N\) consisting solely of the characters 'N', 'E', 'S', 'W', representing Farmer John's path.
• The fifth line contains a string of length \(M\) consisting solely of the characters 'N', 'E', 'S', 'W', representing Bessie's path.

outputFormat

Output a single integer representing the minimum total energy consumed when both Farmer John and Bessie reach the final positions on their respective paths. Energy at each step is computed as ( (x_F - x_B)^2 + (y_F - y_B)^2 ).

sample

2 2
0 0
0 1
NE
EE

2