Hai bạn Paula và Marin đang chơi một trò chơi trên cây. Không phải là trên cây thật, đương nhiên rồi vì điều đó khá nguy hiểm. Tuy vậy, ai có thể đảm bảo rằng một đồ thị liên thông gồm ~n~ đỉnh được đánh số bằng các số nguyên từ ~1~ tới ~n~, và ~n - 1~ cạnh là hoàn toàn an toàn?

Trước khi trò chơi bắt đầu, Paula sẽ tô một số cạnh với màu xanh dương, và Marin sẽ tô một số cạnh với màu đỏ. Nếu cạnh nào đó được tô bởi cả hai, thì màu của cạnh đó sẽ là tím. Tất cả các cạnh đều sẽ được tô một trong ba màu.

Bắt đầu trò chơi, Paula sẽ đứng ở đỉnh ~a~ và Marin sẽ đứng ở đỉnh ~b~. Hai bạn sẽ luân phiên di chuyển, với Paula đi trước. Trong một lượt chơi, bạn đó phải di chuyển sang một đỉnh kề với đỉnh hiện tại mà không chứa đối thủ. Đồng thời, Paula không thể sử dụng các cạnh màu đỏ, và Marin không thể sử dụng các cạnh màu xanh dương, nhưng cả hai có thể dùng các cạnh màu tím. Bạn nào không thể thực hiện một bước đi sẽ thua.

Paula và Marin sẽ chơi một cách tối ưu. Nếu hai bạn nhận ra rằng trò chơi có thể diễn ra mãi mãi, một kết quả hòa sẽ được đưa ra. Hãy giúp hai bạn xác định kết quả của trò chơi.

Input

Dòng thứ nhất chứa một số nguyên ~n\,(2 \le n \le 100\,000)~, thể hiện số đỉnh.

Dòng thứ hai chứa các số nguyên ~a~ và ~b~ ~(1 \le a, b \le n, a \neq b)~, thể hiện vị trí ban đầu của Paula và Marin.

~n - 1~ dòng tiếp theo miêu tả các cạnh. Mỗi dòng có dạng "~x~ ~y~ màu", với ~x~ và ~y~ ~(1 \le x, y \le n)~ là hai đầu mút, và màu là plava (màu xanh dương trong tiếng Croatia), crvena (màu đỏ trong tiếng Croatia) hoặc magenta (màu tím trong tiếng Anh).

Output

In ra Paula nếu như Paula sẽ thắng, Marin nếu Marin sẽ thắng, hoặc Magenta nếu có một kết quả hòa.

Sample 1

Input

3
1 3
3 2 magenta
2 1 magenta

Output

Paula

Giải thích

Paula trong lượt đầu tiên sẽ di chuyển đến đỉnh ~2~. Khi này, Marin không thể di chuyển sang bất kì đỉnh nào.

Sample 2

Input

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

Output

Marin

Giải thích

Paula bắt buộc phải di chuyển tới đỉnh ~1~, sau đó Marin di chuyển tới đỉnh ~2~. Khi này, Paula không thể di chuyển tới đỉnh ~2~ vì Marin đang đứng ở đó, nên bạn ấy phải quay trở lại đỉnh ~3~. Marin sẽ di chuyển tới đỉnh ~1~ và chiến thắng.

Sample 3

Input

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

Output

Magenta

Ràng buộc

• ~13~ test đầu tiên thỏa mãn ~2 \le n \le 100~.
• ~8~ test tiếp theo thỏa mãn tất cả các cạnh có màu là magenta.
• ~13~ test còn lại không có thêm ràng buộc gì.