Migrated from Lutece 2180 van游戏

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

eom和moe在van取石子游戏。桌面上有n堆石子，每堆石子有$x_i$个，每次轮到一个人的时候他可以取走一堆石子。石堆的选取顺序给定并正好形成一个有向树，即当前选取的石堆必须是上一个人选取的石堆的儿子，第一个选的人只能选位于树根的石堆。eom和moe的选取策略有所不同，eom希望游戏结束时自己石子尽可能多的情况下moe手中的石子尽可能少，moe则希望eom手中的石子尽可能少的前提下自己手中的石子尽可能多。如果两人都按照最优策略取石子，请你计算出游戏结束时两人手中分别有多少石子。

Input

第一行为一个字符串"eom"或"moe"，表明谁先取。

第二行为一个正整数n(n≤1e6)表示桌面上有多少堆石子。

第三行为n个正整数，第i个表示第i堆共有$x_i$个石子。

接下来n-1行每行两个整数u和v，表示石堆u被取走之后下一个人可以选取石堆v。

Output

在一行中输出两个个整数表示游戏结束时而eom和moe手中分别有多少石子。

Samples

eom
6
1 3 5 3 4 2
1 2
1 3
3 4
3 5
5 6

1 3

Constraints

n≤1e6

$x_i$≤1e9

Resources

2019 UESTC ACM Training for Dynamic Programming