Patkice II

Αφού το Holywood καταπιάστηκε με τη συναρπαστική ιστορία του επιτυχημένου ταξιδιού με ομπρέλα μεταξύ δύο νησιών, τα στελέχη του Netflix αποφάσισαν να κάνουν μια προσαρμογή της σειράς των ταξιδιών των τριών παπιών.

Όπως ίσως θυμάστε από τον πρώτο γύρο του COCI 20/21, οι πάπιες έχουν έναν χάρτη με τα ωκεάνια ρεύματα. Οι πάπιες ταξιδεύουν μαζί. Το νησί όπου ζουν οι πάπιες σημειώνεται με το γράμμα 'ο'. Οι πάπιες μπορούν να ξεκινήσουν το ταξίδι τους προς οποιαδήποτε από τις τέσσερις κατευθύνσεις. Τα ωκεάνια ρεύματα σε αυτές τις θάλασσες κινούνται προς μία από τις τέσσερις κατευθύνσεις και σημειώνονται με τον ακόλουθο τρόπο: δύση-ανατολή '>', ανατολή-δύση '<', βορράς-νότος 'v' και νότος-βόρει '^'. Όταν οι πάπιες βρίσκονται σε ένα τμήμα του ωκεανού με ρεύμα, το τμήμα αυτό θα μετακινηθεί προς την κατεύθυνση του ρεύματος.

Η ήρεμη θάλασσα σημειώνεται με μια τελεία '.'. Εάν τα ρεύματα φέρουν τις πάπιες σε ένα τμήμα με ήρεμη θάλασσα, έξω από τον χάρτη ή πίσω στο αρχικό νησί, θα σταματήσουν το ταξίδι τους. Το νησί που θέλουν να επισκεφτούν οι πάπιες σημειώνεται με 'x'.

Για να κάνει τη σειρά πιο ελκυστική, το Netflix, έκανε μερικές αλλαγές στην ιστορία: η θάλασσα τώρα μπορεί να περιέχει άγριες δίνες (οι πάπιες μπορεί να κολλήσουν σε μία δίνη, δηλαδή έναν κύκλο) και θαλάσσια ρεύματα που μεταφέρουν τις πάπιες έξω από τον χάρτη. ~^*~

Ως εκ τούτου, ο αρχικός χάρτης των ρευμάτων έχει αλλάξει. Αλλά υπό τη μεγάλη πίεση της προθεσμίας, ο σκηνοθέτης έχει κάνει κάποια λάθη: οι πάπιες δεν μπορούν να φτάσουν πια από το αρχικό νησί στο στόχο, μέσω θαλάσσιων ρευμάτων.

Οι σκηνοθέτες του Netflix είναι πολύ σημαντικά πρόσωπα, επομένως δεν ξοδεύουν πραγματικά χρόνο για να σκεφτούν τα κενά της πλοκής. Επομένως, είναι καθήκον σας τώρα να αντικαταστήσετε όσο το δυνατόν λιγότερους χαρακτήρες στον χάρτη, έτσι ώστε οι πάπιες να μπορούν να πάνε από το αρχικό σημείο στο νησί-στόχο.

Για λόγους ιστορίας, τα τμήματα με ('o' και 'x') δεν μπορούν να τροποποιηθούν. Όλα τα άλλα τμήματα είναι είτε θαλάσσια ρεύματα είτε ήρεμη θάλασσα (χαρακτήρες '<>v^.'). Μπορείτε να αντικαταστήσετε χαρακτήρες σε αυτά τα τμήματα με χαρακτήρες από το ίδιο σύνολο '<>v^.'.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~r~ και ~s\;(3 \le r, s \le 2000)~, τον αριθμό των γραμμών και των στηλών του χάρτη.

Κάθε μία από τις ακόλουθες γραμμές ~r~ περιέχει ~s~ χαρακτήρες από το σύνολο 'o<>v^.x', που αντιπροσωπεύουν τον χάρτη των ωκεάνιων ρευμάτων. Θα υπάρχει πάντα ακριβώς ένας χαρακτήρας 'o' και ακριβώς ένας χαρακτήρας 'x' στον χάρτη και δεν θα είναι δίπλα.

Έξοδος

Στην πρώτη γραμμή εξόδου τυπώνετε το ~k~, τον ελάχιστο αριθμό αλλαγών ώστε οι πάπιες να μπορούν να πάνε από το αρχικό σημείο στο νησί-στόχο.

Σε κάθε μία από τις επόμενες γραμμές ~r~, τυπώστε ~s~ χαρακτήρες, που περιγράφουν έναν χάρτη που διαφέρει από τον χάρτη εισόδου σε ακριβώς ~k~ τμήματα, ικανοποιώντας τις απαιτήσεις του προβλήματος. Εάν υπάρχουν πολλοί έγκυροι χάρτες, τυπώστε κάποιον από αυτούς.

~^*~ Οι πάπιες σχηματίζουν επίσης ένα σπαρακτικό ερωτικό τρίγωνο, αλλά αυτό δεν είναι σημαντικό αυτή τη στιγμή.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	30	~3 \le r, s \le 20~
2	80	Κανένας επιπλέον περιορισμός.

Εάν σε όλες τις περιπτώσεις δοκιμής, σε ορισμένα υποπροβλήματα, η πρώτη γραμμή (ελάχιστος αριθμός αλλαγών) είναι σωστή, αλλά ο χάρτης σε κάποια περίπτωση δοκιμής δεν είναι έγκυρος θα λάβετε τους μισούς βαθμούς γι' αυτό το υποπρόβλημα.

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

input

3 3
>vo
vv>
x>>

output

1
>vo
vv>
x<>

input

3 6
>>vv<<
^ovvx^
^<<>>^

output

2
>>vv<<
^o>>x^
^<<>>^

input

4 4
x.v.
.>.<
>.<.
.^.o

output

4
x<<.
.>^<
>.<^
.^.o