Magenta

Η Paula και ο Marin παίζουν ένα παιχνίδι σε ένα δέντρο. Όχι σε πραγματικό δέντρο, φυσικά. Αυτό θα ήταν επικίνδυνο*. Αν και, ποιός μπορεί να πει ότι ένα συνδεδεμένο γράφημα με ~n~ κόμβους, που συμβολίζονται με ακέραιους αριθμούς από το 1 έως το ~n~, και ~n - 1~ άκρες, είναι απολύτως ασφαλές;

Πριν ξεκινήσει το παιχνίδι, η Paula χρωμάτισε μερικές άκρες μπλε και ο Marin χρωμάτισε κάποιες κόκκινες. Αν κάποια άκρη χρωματίστηκε και από τα δύο χρώματα, το τελικό του χρώμα είναι μωβ. Όλες οι άκρες χρωματίστηκαν από τουλάχιστον ένα από τα χρώμα.

Η Paula ξεκινά το παιχνίδι, με το κομμάτι της, από τον κόμβο ~a~ και ο Marin, με το κομμάτι του, από τον κόμβο ~b~. Οι παίκτες παίζουν εναλλάξ και η Paula παίζει πρώτη. Όταν έρθει η σειρά του κάθε παίκτη, ο παίκτης πρέπει να μετακινήσει το κομμάτι του σε κάποιον παρακείμενο κόμβο που δεν περιέχει το κομμάτι του αντιπάλου. Επίσης, η Paula δεν μπορεί να χρησιμοποιήσει κόκκινους κόμβους και ο Marin δεν μπορεί να χρησιμοποιήσει μπλε κόμβους, ενώ και οι δύο μπορούν να χρησιμοποιήσουν τους μωβ κόμβους. Ο παίκτης που δεν μπορεί να κάνει κίνηση χάνει.

Η Paula και ο Marin παίζουν με τον βέλτιστο τρόπο. Αν καταλάβουν ότι το παιχνίδι μπορεί να μην τερματίσει ποτέ, θα δηλώσουν ισοπαλία. Προσδιορίστε το αποτέλεσμα του παιχνιδιού!

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~n\;(2 \le n \le 100\,000)~, τον αριθμό των κόμβων.

Η δεύτερη γραμμή περιέχει ακέραιους αριθμούς ~a~ και ~b\;(1 \le a, b \le n, a \ne b)~, τους αρχικούς κόμβους της Paula και του Marin.

Οι επόμενες ~n - 1~ γραμμές περιγράφουν τις ακμές. Κάθε γραμμή έχει τη μορφή "~x\;y~ χρώμα", όπου ~x~ και ~y\;(1 \le x, y \le n)~ είναι τα τελικά σημεία και το χρώμα είναι plava (το μπλε στα Κροατικά), crvena (το κόκκινο στα Κροατικά) ή magenta (μωβ).

Έξοδος

Μία γραμμή εξόδου στην οποία θα τυπώνετε Paula, αν η Paula νικήσει, Marin, αν ο Marin νικήσει ή Magenta αν είναι ισοπαλία.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	30	~2 \le n \le 100~
2	30	Όλα τα χρώματα είναι μωβ.
3	50	Κανένας επιπλέον περιορισμός.

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

input

3
1 3
3 2 magenta
2 1 magenta

output

Paula

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

Η Paula θα μετακινηθεί στον κόμβο 2 και τότε ο Marin δεν μπορεί να κάνει κίνηση.

input

5
3 5
1 2 magenta
1 3 magenta
2 4 plava
2 5 crvena

output

Marin

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

Η Paula πρέπει να μετακινηθεί στον κόμβο 1 και, στη συνέχεια, ο Marin θα μετακινηθεί στον κόμβο 2. Η Paula τώρα δεν μπορεί να μετακινηθεί στον κόμβο 2, αφού ο Marin είναι εκεί, επομένως πρέπει να επιστρέψει στον κόμβο 3. Ο Marin μετακινείται στον κόμβο 1 και κερδίζει.

input

5
1 4
2 1 plava
1 3 crvena
5 2 plava
4 1 magenta

output

Magenta