Problem 2 - Candies

Little Michael loves candies. Most of all, he likes chocolate, strawberry and banana flavored ones. No wonder that he has candy bags everywhere - there are at least four bags on his table, one or two in the pockets of his jeans, and one under his bed (just in case). Each bag contains some candies of all three flavors. Whenever he wants to eat a candy, he finds the nearest bag (which is usually is not very far because he has really A LOT of them) and eats the candy he wants.

Yesterday, he wanted a strawberry one, so he opened one of his bags and... It is almost impossible to describe how great his disappointment was when he found out that there were no strawberry candies left in that bag. To make the matters worse, there were also none in the second bag he found. He was sure that he had lots of strawberry candies left, but he didn't know in which bags they were. Therefore, he decided to reorganize his candies, and keep the candies of the three different flavors in three distinct bags. He brought all his bags into the center of his room and realized, that there are really an awful lot of them.

Michael has N bags full of candies. He knows the number of candies of each flavor in each bag. He wants to put all chocolate ones into one bag, all strawberry ones into another bag and all banana ones into yet another bag. He has to move the candies one-by-one, because he always has to look at it to determine its flavor. Moving one candy from one bag into another takes 1 second. Your task is to select the bag for each flavor, so that the total time required for Michael to move all the candies into their bags would be minimal.

Input file specification

The first line of the input file contains a single positive integer N <10,000 - the number of bags. Each of the following N lines consists of three numbers c_i, s_i, b_i - the numbers of chocolate, strawberry and banana candies in the i-th bag. All numbers are in the range of [0, 1,000,000]. The bags are numbered from 1 to N in the order in which they appear in the input.

Output file specification

Output file should contain three lines with the following text:

Bag for chocolate candies: C
Bag for strawberry candies: S
Bag for banana candies: B

The numbers C, S, B have to be such that the total number of the required moves is minimal. If there are more solutions, you may choose any of them.

Example

Input file:

5
10 10 10
40 39 40
10 20 30
30 20 10
1 2 27

Output file:

Bag for chocolate candies: 4
Bag for strawberry candies: 2
Bag for banana candies: 3

Note: In this case Michael has to move 200 candies. If the bags for the different flavors were chosen in any other way, he would have to move more than 200 candies.

---

e-mails

questions: ipscreg(at)ksp(dot)sk

webmaster: webmaster(at)ksp(dot)sk