Multigram

Ο Pero είναι παθιασμένος λάτρης των γρίφων. Ο νεότερος τύπος γρίφων που έχει συναντήσει απαιτεί από τον λύτη να ελέγξει αν η δεδομένη λέξη είναι πολύγραμμο.
Ένα πολύγραμμο είναι μια λέξη που αποτελείται από τη σύνδεση δύο ή περισσότερων λέξεων που είναι όλες αμοιβαία αναγραμματισμοί. Η πρώτη από αυτές τις λέξεις ονομάζεται ρίζα του πολυγράμμου. Για παράδειγμα, η λέξη ~bbabab~ είναι ένα πολύγραμμο με τη ρίζα ~bba~ επειδή αποτελείται από αναγραμματισμούς ~bba~ και ~bab~.

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

Σημείωση: Δύο λέξεις είναι αμοιβαία αναγραμματισμοί, εάν η μία από αυτές μπορεί να ληφθεί από την άλλη αλλάζοντας τη σειρά των γραμμάτων.

Είσοδος

Η πρώτη και μοναδική γραμμή εισόδου περιέχει μια λέξη μήκους το πολύ ~100\,000~ πεζών αγγλικών χαρακτήρων.

Έξοδος

Αν η δεδομένη λέξη δεν είναι πολύγραμμο, τυπώστε -1.
Διαφορετικά, τυπώστε τη συντομότερη ρίζα της δεδομένης λέξης σε μία γραμμή.

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

input

aaaa

output

a

Επεξήγηση του 1ου παραδείγματος: Παρατηρήστε ότι η λέξη "~aa~" θα μπορούσε επίσης να είναι η ρίζα, αλλά το "~a~" είναι μικρότερο.

input

ab

output

-1

Επεξήγηση του 2ου παραδείγματος: Η λέξη δεν είναι πολύγραμμο γιατί το "~a~" και το "~b~" δεν είναι αμοιβαία αναγραμματισμοί.

input

bbabab

output

bba