Labirint

Τι είναι EJOI για εσάς;
Αίθουσα παιχνιδιών!

Η Τίο αναζητά την κροατική ομάδα EJOI! Έχει ήδη βρει τον Γκάμπριελ, αλλά εξακολουθεί να ψάχνει τον Βίτο, τον Ντίνο και τον Ίβο.

Η Τίο και η ομάδα EJOI βρίσκονται σε έναν λαβύρινθο που αποτελείται από ~n \times m~ δωμάτια, όλα του ίδιου μεγέθους. Τα δωμάτια σχηματίζουν ένα πλέγμα. Το πάνω αριστερά δωμάτιο έχει την ένδειξη ~(1,\;1)~ και το κάτω δεξιά δωμάτιο την ένδειξη ~(n,\;m)~. Μεταξύ κάθε ζεύγους γειτονικών δωματίων, υπάρχει μια πόρτα χρωματισμένη με ένα από τα τέσσερα χρώματα: μπλε (σημειωμένο με "~P~"), κόκκινο (σημειωμένο με "~C~"), πράσινο (σημειωμένο με "~Z~") και πορτοκαλί (σημειωμένο με "~N~").

Κάποια στιγμή, ο Γκάμπριελ λέει: Ξέρω πού βρίσκεται η υπόλοιπη ομάδα, αλλά θα σου το πω μόνο αν μπορέσεις να απαντήσεις σε όλες μου τις ερωτήσεις.

Οι ερωτήσεις του Γκάμπριελ είναι οι εξής: Εάν βρισκόμαστε αυτή τη στιγμή στο δωμάτιο ~(a_{i},\;b_{i})~ και η υπόλοιπη ομάδα βρίσκεται στο δωμάτιο ~(c_{i},\;d_{i})~, ποιος είναι ο ελάχιστος αριθμός χρωμάτων από πόρτες που πρέπει να περάσουμε για να τους φτάσουμε;

Η Τίο είναι πολύ καλή στο να απαντά στις ερωτήσεις του Γκάμπριελ, αλλά είναι απλά πάρα πολλές. Δεν έχει πολύ χρόνο (το λεωφορείο φεύγει σύντομα), γι' αυτό σας ζητάει να τη βοηθήσετε να απαντήσει σε ~q~ από τις ερωτήσεις του Γκάμπριελ!

Είσοδος

Η πρώτη γραμμή θα περιέχει τους ακέραιους αριθμούς ~n~ και ~m\;(1 \le n, m \le 100,\;1 < n \times m)~, τον αριθμό των δωματίων.

Η ~i~-οστή από τις επόμενες ~n~ γραμμές θα περιέχει ~m - 1~ χαρακτήρες ("~P~", "~C~", "~Z~" ή "~N~"), όπου ο ~j~-οστός χαρακτήρας σηματοδοτεί το χρώμα της πόρτας που συνδέει τα δωμάτια ~(i,\;j)~ και ~(i,\;j + 1)~.

Η ~i~-οστή από τις επόμενες ~n - 1~ γραμμές θα περιέχει ~m~ χαρακτήρες ("~P~", "~C~", "~Z~" ή "~N~"), όπου ο ~j~-οστός χαρακτήρας σηματοδοτεί το χρώμα της πόρτας που συνδέει τα δωμάτια ~(i,\;j)~ και ~(i + 1,\;j)~.

Η επόμενη γραμμή θα περιέχει τον ακέραιο αριθμό ~q\;(1 \le q \le 100)~, τον αριθμό των ερωτήσεων του Γκάμπριελ.

Στην ~i~-οστή από τις επόμενες ~q~ γραμμές, θα υπάρχουν τέσσερις ακέραιοι αριθμοί ~a_{i}~, ~b_{i}~, ~c_{i}~ , ~d_{i}\;(1 \le a_{i}, c_{i} \le n, 1 \le b_{i}, d_{i} \le m, (a_{i},\;b_{i} ) \neq (c_{i},\;d_{i} ))~, η περιγραφή της ~i~-οστής ερώτησης του Γκάμπριελ.

Έξοδος

Στην ~i~-οστή από τις ~q~ γραμμές, δώστε την απάντηση στην ~i~-οστή ερώτηση του Γκάμπριελ.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	11	~n = 1~
2	13	Όλες οι πόρτες που συνδέουν τα δωμάτια ~(i,\;j)~ με τα δωμάτια ~(i,\;j + 1)~ είναι μπλε και όλες οι πόρτες που συνδέουν τα δωμάτια ~(i,\;j)~ με τα ~(i + 1,\;j)~ είναι κόκκινες.
3	24	Κάθε πόρτα είναι είτε κόκκινη είτε μπλε.
4	22	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

1 8
CPZNCCP
4
1 1 1 8
1 3 1 5
1 8 1 4
1 2 1 3

output

4
2
3
1

input

3 3
PP
PP
PP
CCC
CCC
3
1 1 3 3
3 3 2 2
1 1 1 3

output

2
2
1

input

4 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 1

output

1
2
1
3

Επεξήγηση του τρίτου παραδείγματος:

Το τρίτο παράδειγμα απεικονίζεται στο κείμενο.

Για την πρώτη ερώτηση, η Τίο και ο Γκάμπριελ μπορούν να χρησιμοποιήσουν μόνο μπλε πόρτες και να φτάσουν στην υπόλοιπη ομάδα- για την δεύτερη ερώτηση, μπορούν να χρησιμοποιήσουν μπλε και πράσινες πόρτες- για την τρίτη και πάλι μόνο η μπλε είναι αρκετές- και για την τέταρτη, μπορούν να χρησιμοποιήσουν μπλε, πράσινες και κόκκινες πόρτες.