401604: GYM100499 C Grid city

Alpha is a modern and very well-planned city. The city is arranged in a grid shape with all the streets are one-way and parallel to the North-South axis or East-West axis. There are V vertical streets (parallel to North-South axis) and H horizontal streets (parallel to East-West axis). V vertical streets are numbered 1 to V from West to East. H horizontal streets are numbered 1 to H from South to North.

If we represent this city in a 2D plane, the first vertical street is on the line x = 0, the first horizontal street is on the line y = 0. The ith vertical street is VG_i meters from the (i + 1)th vertical street. The jth horizontal street is HG_j meters from the (j + 1)th horizontal street.

Vertical streets are either Northbound (go from South to North) or Southbound (go from North to South). The directions of these vertical streets are given in a string VD where VD_i is either ‘N’ or ‘S’. Horizontal streets are either Westbound (go from East to West) or Eastbound (go from West to East). The directions of these horizontal streets are given in a string HD where HD_j is either ‘W’ or ‘E’.

Given K queries x₁, y₁, x₂, y₂, you are to calculate the shortest path from (x₁, y₁) to (x₂, y₂).

The first line is the number T (T ≤ 20) denotes the number of test cases. Then T test cases follow:

• The first line of each test is integers V, H, K.(1 ≤ V, H ≤ 5000, 1 ≤ K ≤ 1000)
• The second line of each test is VG - an array of length V - 1 (1 ≤ VG_i ≤ 1000)
• The third line of each test is HG - an array of length H - 1 (1 ≤ HG_j ≤ 1000)
• The fourth line of each test is VD - a string of length V
• The fifth line of each test is HD - a string of length H
• Then K queries follow. Each query consists of 4 non-negative integers x₁, y₁, x₂, y₂. It is guarantee that each points lies on a street.

For each query, print the shortest distance. If it is not possible to go from (x₁, y₁) to (x₂, y₂), print -1 instead.

1
6 6 4
1 1 2 1 1
1 1 2 1 1
NNNSSS
WWWEEE
5 4 5 4
2 2 4 4
3 2 3 0
6 6 5 5

0
4
10
14

The city map with directions: