Paula 和 Marin 正在一棵树上玩游戏。当然，不是在真正的树上，那太危险了。不过，谁又能说一个拥有 $n$ 个节点（用 $1$ 到 $n$ 的整数标记）和 $n - 1$ 条边的连通图就是完全安全的呢？

在游戏开始前，Paula 将一些边染成了蓝色，Marin 将一些边染成了红色。如果某条边被两人都染了色，它的最终颜色就是洋红色（magenta）。所有边都至少被他们中的一人染了色。

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 color，其中 $x$ 和 $y$（$1 \le x, y \le n$）是端点，color 是 plava（克罗地亚语中的蓝色）、crvena（克罗地亚语中的红色）或 magenta（洋红色）。

输出格式

如果 Paula 获胜，输出 Paula；如果 Marin 获胜，输出 Marin；如果是平局，输出 Magenta。

数据范围

样例

输入样例 1

3
1 3
3 2 magenta
2 1 magenta

输出样例 1

Paula

输入样例 2

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

输出样例 2

Marin

输入样例 3

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

输出样例 3

Magenta

说明

样例 1 说明

Paula 将移动到节点 2，然后 Marin 无法进行移动。

样例 2 说明

Paula 必须移动到节点 1，然后 Marin 将移动到节点 2。Paula 现在无法移动到节点 2（因为 Marin 在那里），所以她必须返回节点 3。Marin 移动到节点 1 并获胜。