PEG Judge - NOI '04

National Olympiad in Informatics, China, 2004

Day 1, Problem 3 - Manhattan

City P is a famous tourist attraction in country M. Under the leadership of Mayor G, the people live and work peacefully in the thriving city. However, Mayor G has not once been carried away by his achievements. His clear head is very aware that there are still some issues that exist in the governance of the city. One of these issues is traffic problems.

City P has m horizontal and n vertical streets. The horizontal streets run east-west, and the vertical streets run north-south, forming the traffic network of city P (as depicted below).

Due to the narrow streets, each street is only one-way. The direction of each street is predetermined. The direction of a horizontal street can only be either east or west. The direction of a vertical street can only be north or south. Going against the designated direction of a street is strictly prohibited.

This limitation is a major inconvenience for traffic. As can be seen in the above figure, tourists may, for example, wish to go from their hotel to the shopping center. However, due to the one-way streets, they have to travel in a big circle to reach their destination.

This problem has been puzzling Mayor G for a while now. Every day, he will receive many letters from tourists, complaining about city P's unreasonable traffic system. Due to the large number of streets, he and his councilmen are still unable to solve this problem.

Fortunately, this problem can soon be resolved. This is because recently, he has paid good money to hire the world-renowned traffic engineer, Mr. B, to renovate city P's traffic system for efficiency.

Mr. B knows that the problem cannot be solved through expanding the width of the streets, since this will impact the various tourist attractions located along each side of the streets. So, he prepares to reassign the directions of some one-way streets to maximize the satisfaction of everyone.

Mr. B assigned labels to each street in city P. The horizontal streets are labeled with the numbers 1, 2, …, m, in order from north to south. The vertical streets are labeled with the numbers 1, 2, …, n, in order from west to east. This way, the position of any intersection can be represented using a pair of integers, where the first integer is the number of the horizontal street at that intersection and the second integer is the number of the vertical street at that intersection. This pair shall be known as the coordinates of this intersection. In the figure above, the hotel's coordinates would therefore be (2, 3).

After a long period of research, he has assembled some requests made collectively by tourists. Each request can be written in the following form: the length of the shortest path from one intersection to another intersection must be equal to the Manhattan distance between the intersections. The Manhattan distance between two intersections refers to the sum of their horizontal and their vertical distances. Two intersections with coordinates (x₁, y₁) and (x₂, y₂) has a Manhattan distance of |x₁ − x₂| + |y₁ − y₂|.

Mr. B already knows the directions of all the streets in city P as well as the requests collectively made by the tourists. Can he reassign the directions of streets to fulfill all of the requests?

Additionally, changing the direction of each street requires a fixed working cost. The size of working costs depend on the streets. Mr. B not only wants to find a valid plan, he also wants the total working cost of this plan to be minimized. Can you help him?

Input Format

The first line of input contains two integers m and n, representing the number of horizontal and vertical streets, respectively.
The second line of input contains a sequence of characters of length m, the directions of the m horizontal streets before the reassignments are made, in order from north to south. E signifies an eastbound street and W signifies a westbound street.
The third line of input contains a sequence of characters of length n, the directions of the n vertical streets before the reassignments are made, in order from west to east. N signifies an northbound street and S signifies a southbound street.
The fourth line contains m nonnegative integers, the working costs to change each of the horizontal streets, in order from north to south.
The fourth line contains n nonnegative integers, the working costs to change each of the vertical streets, in order from west to east.
The sixth line contains a single positive integer k, representing the number of requests made by the tourists.
The next k lines each contain four positive integers x₁, y₁, x₂, and y₂, each describing one request. A request indicates that the tourists wish for the length of the shortest path from intersection (x₁, y₁) to intersection (x₂, y₂) to equal the Manhattan distance between the two intersection.

Output Format

The first line of output should contain one string, either "possible" or "impossible" (without quotes). Output "possible" to indicate that there is a way to reassign directions to streets such that all the requests in the input are satisfied. Output "impossible" to indicate that no matter how directions are reassigned, there is no way to satisfy all the requests.

If the first output is "possible", then the second line should contain a single integer representing the minimum total working cost, the third line should contain a string of length m representing the revised directions of the horizontal streets in order from north to south (output E for east, W for west), and the fourth line should contain a string of length n representing the revised directions of the vertical streets in order from west to east (output N for north, S for south).

Constraints

m ≤ 10
n ≤ 100
k ≤ 100
The working cost to change the direction of any street will not exceed 10000.

Sample Input

Sample Output

possible
9
WW
NNS

Scoring

Your score out of 10 for each test case is determined as follows:

If the first line of your program's output is "impossible":
- If there is actually no solution, then you will score full points.
- If there is actually a solution, then you will score 0 points.
If the first line of your program's output is "possible":
- If the remaining lines are incorrectly formatted, your strategy is infeasible, or your total working cost is incorrect in relation to your strategy, then you will score 0 points.
- If your strategy is feasible, but total working cost is not optimal, then you will score 4 points.
- If your strategy is both feasible and optimal, then you will score full points.
Otherwise, your score will be 0 points.