Donation King's Nim Game

Time limit1sMemory limit1024 MB

Summary

For each three-pile Nim position, find how many stones each player takes when both play optimally, with the winner taking as many stones as possible.

Level: Medium6 of 10
Topics: Game theory, Dynamic programming
Solved: No attempts yet

Problem

Gibu and Taekgu want to make the world a better place by donating. Ordinary donations are dull, so they decide to donate by playing Nim, a well-known game.

In Nim, several piles of stones are given, and two players take turns choosing one pile and removing at least one stone from it, as many as they like. The player who takes the last stone of the whole set of piles wins.

The two players play Nim with exactly three piles. Because this game is for donations, each stone taken earns the player who takes it a donation of $10\,000$ won. Both players know the optimal strategy of Nim, and with great sportsmanship, neither ever loses on purpose a game they could win. Each player wants to donate as much money as possible. Find the donation amounts of the two players after the game ends.

The game always starts with Gibu.

Input

The first line contains the number of games $T$ . $(1\le T \le 100\,000)$

Each of the next $T$ lines contains the stone counts $x$ , $y$ , and $z$ of the three piles used in one game, separated by spaces. $(1\le x,y,z \le 200)$

Output

For each game, print the donation amounts of Gibu and Taekgu separated by a space, one game per line.

Examples2

Example 1
Input
```
1
1 4 5
```
Expected output
```
70000 30000
```

Example 2

Input

2
3 3 3
103 64 171

Expected output

60000 30000
1450000 1930000