Description

北极探险队有新收获了！！！

北极探险队发现了$N$条长度不一的冰柱，由于冰柱里封存有价值的生物，现在需要两名生物学家小A和小B对冰柱进行分析，公平起见，探险队将每条冰柱都均分成长度为1的冰块，现在规定两位生物学家开始轮流选择冰块，小A先选，每次选择小A只能在任意一条没被选空的冰柱的最左边选择一个长度为1的冰块，而小B只能在任意一条没被选空的冰柱的最右边选择一个长度为1的冰块；

依据题意，上述这条冰柱，小A会选择左边四个冰块 价值为$33 + 17 + 2 + 6 = 58，$ 同理小B选择右边三个的价值为$11 + 18 + 19 = 48.$

问：若两位生物学家都采用最优策略，那么 小A 和 小B 的能选到的冰块价值最后分别是多少？

Format

Input

第一行输入一个$n(1 \leq n \leq 10^5)$, 表示冰柱数量。
接下来$n$行，
每行第一个数字$x$,表示将冰柱分成$x$个冰块，紧接着输入$x$个数字$a_i$，每个数$a_i(1 \leq a_i \leq 10^9)$表示每个冰块的价值。

Output

分别输出 小A的分数 和 小B的分数。

Samples

1
7 33 17 2 6 11 18 19

58 48

3
4 15 18 17 16
2 1 3
1 20

54 36

Hint