J. ACM
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The ACM team of BNU is recruiting new members!

After multiple rounds of selection, all candidates have successfully joined the team, except wzj and xyz, whose final spots are still pending.

You decide to team up with them for an ACM contest to evaluate their coding skills. The three of you share one computer during the contest. The problems are fairly easy, so you solve all of them effortlessly and assign a score to each problem. Then you let wzj and xyz take turns to write code for the problems. wzj moves first, and xyz moves second. Both of them hope to win your recognition, so they try to maximize their own total scores to show their ability.

There are $$$n$$$ problems in total, and each problem belongs to one of the following two types:

  • Single-part problem: This problem has only one part, with a score of $$$h$$$.
  • Two-part problem: It contains two subproblems (the first part and the second part), whose scores are $$$h_1$$$ and $$$h_2$$$ respectively. The second part can only be completed after the first part is finished. Note that these two parts can be completed by different players.

wzj and xyz take turns to make moves, with wzj moving first. On each turn, the current player must select and complete one problem from all currently available problems, and gain the score of that problem.

Definition of available problems:

  • For a single-part problem: It is always available as long as it has not been completed.
  • For the first part of a two-part problem: It is available if this part has not been completed.
  • For the second part of a two-part problem: It becomes available only if the corresponding first part has been completed (by either player) and the second part itself remains unfinished.

The game ends after all problems are completed.

Both players aim to maximize their own total score. Given that both of them adopt optimal strategies, please calculate the final scores of wzj and xyz.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$, denoting the number of problems (each problem is either single-part or two-part).

The following $$$n$$$ lines each describe one problem:

  • If it is a single-part problem, the line contains an integer $$$1$$$ followed by an integer $$$h$$$ $$$(1 \le h \le 10^9)$$$, representing its score.
  • If it is a two-part problem, the line contains an integer $$$2$$$ followed by two integers $$$h_1, h_2$$$ $$$(1 \le h_1, h_2 \le 10^9)$$$, representing the scores of the first subproblem and the second subproblem respectively.
Output

Output two integers separated by a single space on one line, which are the total scores of wzj and xyz under optimal strategies.

Example
Input
3
2 1 100
2 6 5
1 3
Output
109 6