P5747 [NOI2004] Manhattan

City P is a famous tourist city in country M. Under Mayor Mr. G’s governance, people live and work in peace, and the city is thriving. However, Mayor G was not blinded by his achievements. He clearly realized that there were still some problems in managing the city, one of which was transportation. City P has $m$ horizontal streets and $n$ vertical streets. The horizontal streets run from west to east, and the vertical streets run from north to south, forming a neat transportation network in City P (as shown in Figure 1).  Because the streets are narrow, each street allows traffic in only one direction, and the direction is set in advance. A horizontal street can only go east or west, and a vertical street can only go south or north. Driving in the opposite direction is strictly forbidden. This restriction causes great inconvenience to transportation. As in Figure 1, many tourists want to go from the hotel to the shopping center, but due to the street directions, they have to take a big detour to reach it. This problem has been troubling Mayor G for a long time. Every day he receives many letters from tourists, complaining about City P’s unreasonable traffic design. But because there are too many streets, he and his staff have never been able to solve this problem. Fortunately, this problem may be solved soon. Recently, they hired the famous traffic planning expert Mr. B with a large payment, asking him to carry out an effective and reasonable reconstruction of City P’s traffic. Mr. B knows that widening streets cannot solve the problem, because that would inevitably affect the tourist attractions along the streets, which nobody wants to see. So he plans to redesign the driving direction of each street (the direction of the whole street), so as to satisfy people’s needs as much as possible. Mr. B first numbered the streets of City P. The horizontal streets are numbered $1,2,\ldots,m$ from north to south, and the vertical streets are numbered $1,2,\ldots,n$ from west to east. Then, the position of any intersection can be represented by a pair of positive integers: the first number is the index of the horizontal street it lies on, and the second number is the index of the vertical street it lies on. This pair of integers is called the coordinate of the intersection. For example, in Figure 1, the coordinate of the intersection where the hotel is located is $(2,3)$. After a long investigation, he summarized some requirements that tourists mentioned most often. Each requirement can be written in the following form: the length of the shortest path from one intersection to another must be equal to the Manhattan distance between them. The so-called Manhattan distance is the distance in the east-west direction plus the distance in the north-south direction. For two intersections with coordinates $(x_1,y_1)$ and $(x_2,y_2)$, their Manhattan distance is $|x_1-x_2|+|y_1-y_2|$. Now, Mr. B already knows the current driving directions of all streets in City P and the tourists’ common requirements. Can he redesign the street directions to satisfy all requirements? Also, changing the driving direction of each street requires some amount of work, and the amount varies by street. Mr. B not only wants to find a feasible reconstruction plan, but also hopes that the total amount of work is as small as possible. Can you help him?

The first line contains two positive integers $m$ and $n$, representing the numbers of horizontal streets and vertical streets. The second line is a string of length $m$, listing from north to south the driving directions of the $m$ horizontal streets before reconstruction. `E` means east, and `W` means west. The third line is a string of length $n$, listing from west to east the driving directions of the $n$ vertical streets before reconstruction. `S` means south, and `N` means north. The fourth line contains $m$ non-negative integers, listing from north to south the amount of work needed to change the direction of each horizontal street. The fifth line contains $n$ non-negative integers, listing from west to east the amount of work needed to change the direction of each vertical street. The sixth line contains a positive integer $k$, the number of common requirements proposed by tourists. The next $k$ lines each contain four positive integers $x_1$, $y_1$, $x_2$, $y_2$, describing one requirement. The requirement is that the length of the shortest path from the intersection at $(x_1,y_1)$ to the intersection at $(x_2,y_2)$ must equal the Manhattan distance between these two intersections.

The first line is a string, either `possible` or `impossible`. Output `possible` if it is possible to satisfy all requirements in the input by changing street directions. Output `impossible` if it is impossible to satisfy all requirements no matter how you redesign the directions. If the first line is `possible`, then output an integer on the second line, the minimum total amount of work. On the third line, output a string of length $m$, listing from north to south the driving directions of the $m$ horizontal streets after reconstruction, where `E` means east and `W` means west. On the fourth line, output a string of length $n$, listing from west to east the driving directions of the $n$ vertical streets after reconstruction, where `S` means south and `N` means north.

#### Constraints For all data, $m\le 10$, $n\le 100$, $k\le 100$. The amount of work to change the direction of one street does not exceed $10000$. #### Scoring - If the first line of your output file is `impossible`: - If there is indeed no solution, you get full marks for this test point. - If there is actually a solution, you get $0$ points for this test point. - If the first line of your output file is `possible`: - If the plan output by your program is infeasible, you get $0$ points for this test point. - If the total amount of work output by your program does not match the actual total amount of work, you get $0$ points for this test point. - If the plan output by your program is feasible but the total amount of work is not minimal, you get $4$ points for this test point. - If the plan output by your program is feasible and the total amount of work is minimal, you get full marks for this test point. Translated by ChatGPT 5