Roboti

Ο Κιλ, ένας λάτρης των επιτραπέζιων παιχνιδιών, ανακάλυψε πρόσφατα το παιχνίδι Robots. Το παιχνίδι αυτό αποτελείται από έναν πίνακα με ~n~ γραμμές και ~m~ στήλες και ένα ρομπότ. Το κελί ~(1,\;1)~ είναι το κελί που βρίσκεται στην επάνω αριστερή γωνία του πίνακα, ενώ το κελί ~(n,\;m)~ είναι το κελί στην κάτω δεξιά γωνία.

Στην αρχή, το ρομπότ τοποθετείται σε κάποιο κελί ~(x,\;y)~ (~x~-οστή γραμμή, ~y~-οστή στήλη), και ο παίκτης μπορεί να το κατευθύνει προς μία από τις τέσσερις κατευθύνσεις: πάνω, κάτω, αριστερά ή δεξιά. Ανάλογα με την επιλεγμένη κατεύθυνση, το ρομπότ θα κινηθεί προς αυτήν την κατεύθυνση μέχρι να συναντήσει τον στόχο του ή ένα ειδικό κελί στον πίνακα. Εάν, σε κάποιο σημείο, το ρομπότ επιχειρήσει να βγει από τον πίνακα, επιστρέφει στην άλλη πλευρά του πίνακα (wraps around). Για παράδειγμα, αν βρίσκεται στο κελί ~(n,\;3)~ και θέλει να κινηθεί προς τα κάτω, θα φτάσει στο κελί ~(1,\;3)~.

Ο πίνακας έχει τρία είδη κελιών:

• Κενό κελί - το ρομπότ συνεχίζει να κινείται προς την ίδια κατεύθυνση
• Κελί στροφής αριστερά - όταν το ρομπότ πατήσει σε αυτό το κελί, θα στραφεί αριστερά κατά 90° και θα συνεχίσει την κίνησή του
• Κελί στροφής δεξιά - όταν το ρομπότ πατήσει σε αυτό το κελί, θα στραφεί δεξιά κατά 90° και θα συνεχίσει την κίνησή του

Τα περισσότερα κελιά στον πίνακα είναι κενά, μόνο ~k~ από αυτά είναι κελιά αριστερής ή δεξιάς στροφής.

Το παιχνίδι αποτελείται από ~q~ γύρους. Στον ~i~-οστό γύρο του παιχνιδιού, το ρομπότ θα τοποθετηθεί στο κελί ~(a_{i},\;b_{i})~. Ο στόχος είναι να φτάσει στο κελί ~(c_{i},\; d_{i})~ χρησιμοποιώντας το ελάχιστο πλήθος στροφών, ή να καθορίσει ότι είναι αδύνατο να φτάσει εκεί. Αφού έπαιξε αυτό το παιχνίδι αρκετές φορές, ο Κιλ συνειδητοποίησε ότι είναι πιο απαιτητικό απ'όσο νόμιζε στην αρχή. Γι' αυτό χρειάζεται τώρα τη βοήθειά σας. Βοηθήστε τον να καθορίσει το ελάχιστο πλήθος στροφών που απαιτείται για κάθε γύρο του παιχνιδιού!

Σημείωση: Εάν το ρομπότ ξεκινά ή τελειώνει τη διαδρομή του σε κελί αριστερής ή δεξιάς στροφής, αυτή η στροφή δεν υπολογίζεται.

Είσοδος

Η πρώτη γραμμή θα περιέχει τους ακέραιους ~n~, ~m~ και ~k\;(1 \le n,m \le 10^{6},\; 0 \le k \le 10^{5})~, τον αριθμό των σειρών, των στηλών και των μη κενών κελιών στον πίνακα.

Η ~i~-οστή από τις επόμενες ~n~ γραμμές θα περιέχει τους ακέραιους ~x_{i}~, ~y_{i}~ και το χαρακτήρα ~s_{i}\;(1 \le x_{i} \le n,\; 1 \le y_{i} \le m,\;~ ~s_{i} = 'L'~ ή ~s_{i} = 'R'~), τη γραμμή και στήλη του ~i~-οστού κελιού στροφής και τον τύπο στροφής. Αν ~s_{i} = 'L'~, τότε είναι κελί αριστερής στροφής. Αν ~s_{i} = 'R'~, τότε είναι κελί δεξιάς στροφής.

Η επόμενη γραμμή θα περιέχει τον ακέραιο ~q\;(1 \le q \le 3 \cdot 10^{5})~, τον αριθμό των γύρων.

Η ~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)~, την αρχική θέση και τον στόχο.

Έξοδος

Στην ~i~-οστή από τις επόμενες ~q~ γραμμές εκτυπώστε τον ελάχιστο αριθμό στροφών για τον ~i~-οστό γύρο του παιχνιδιού ή ~'-1'~ αν είναι αδύνατο να φτάσει στον στόχο.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~10~	~k = 0~
~2~	~13~	~n,m \le 300,\;q \le 10~
~3~	~49~	~n,m \le 300~
~4~	~38~	Κανένας επιπλέον περιορισμός

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

input

2 2 2
1 1 L
2 2 R
5
1 1 2 2
2 1 1 2
1 1 1 2
2 1 1 1
2 2 2 1

output

-1
1
0
0
0

input

3 3 4
1 1 L
1 3 L
2 1 L
3 3 L
7
1 1 3 3
3 3 2 1
3 1 2 2
2 3 1 2
2 3 3 1
1 2 3 2
3 3 2 2

output

1
2
1
1
1
0
3

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

Πρώτος γύρος: Ξεκινάμε από το ~(1,\;1)~. Αν κατευθύνουμε το ρομπότ προς τα αριστερά, στο επόμενο βήμα θα φτάσει στο ~(1,\;3)~ επειδή ήθελε να βγει από τον πίνακα, οπότε "τυλίγεται" στην άλλη πλευρά. Το κελί ~(1,\;3)~ είναι κελί αριστερής στροφής, οπότε το ρομπότ κατευθύνεται προς τα κάτω. Μετά από ακόμη δύο βήματα, θα βρίσκεται στον επιθυμητό στόχο ~(3,\;3)~.

Δεύτερος γύρος: Ξεκινάμε από το ~(3,\;3)~. Αν κατευθύνουμε το ρομπότ προς τα επάνω, θα φτάσει στο ~(1,\;3)~ σε δύο βήματα, όπου θα κατευθυνθεί προς τα αριστερά λόγω του κελιού αριστερής στροφής. Μετά από δύο βήματα, θα βρίσκεται στο κελί ~(1,\;1)~, το οποίο είναι επίσης καλί αριστερής στροφής, επομένως θα κατευθυνθεί προς τα κάτω. Στο επόμενο βήμα, θα βρίσκεται στον επιθυμητό στόχο ~(2,\;1)~.

input

4 4 8
1 1 R
1 3 L
2 2 R
2 4 L
3 1 L
3 3 L
4 2 L
4 4 L
7
1 2 1 4
2 2 3 4
4 4 3 2
4 1 4 4
4 2 3 1
1 2 2 3
2 4 2 3

output

2
1
1
0
-1
5
0