Problem: River

Want to try solving this problem? You can submit your code online if you log in or register.

River

Time Limit: 0.2 second
Memory Limit: 10 Mb

A lush, beautiful and uninhabited island has been discovered in a remote patch of the Pacific Ocean. Several foreigners are planning to migrate to this little piece of paradise, and you have found yourself in charge of planning the main town.

As it happens, most of the migrants are French and Australian. Unfortunately none of the Australians ever learned French, and none of the French can understand the thick Australian accents.

You have therefore decided to split the town into two sectors. A wide river flows through the centre of the island, and so you plan to form a French sector on one side of the river and an Australian sector on the other. In the middle of the river, a few floating restaurants will open up so that the different nationalities can meet and speak the universal language of coffee.

You must be very careful about how you build this town. The residents wish to keep the sectors as equal as possible, so that one nationality does not dominate the other. They keep careful track of how much area has been developed on each side of the river, and they tax you (the town planner) according to how large the difference is.

Specifically, each time you construct a new building, the residents measure the total area of buildings on the French side and the total area of buildings on the Australian side (in square metres). They then calculate the difference between these two areas, and tax you by this same amount in drachmas (the only form of currency that both countries can agree upon).

The residents are also quite fussy about which buildings they want constructed. You have been given an exact list of which buildings must be built, though you are allowed to build them in any order and on any side of the river. Your task is to choose when and where to construct these buildings so that you pay less tax in total.

Example

Suppose that you are asked for three buildings of areas 2, 3 and 4. The tables below illustrate two different ways in which you might construct these buildings.

New Building	Area (Aus.)	Area (Fr.)	Tax
Area 2, French side	0	2	2
Area 3, French side	0	5	5
Area 4, Australian side	4	5	1
Total tax			8

New Building	Area (Aus.)	Area (Fr.)	Tax
Area 3, Australian side	3	0	3
Area 4, French side	3	4	1
Area 2, Australian side	5	4	1
Total tax			5

The second method is better than the first, since it gives a lower total tax of 5 drachmas.

Constraints

1 <= N <= 100, where N is the number of buildings that are required;
1 <= A <= 100,000, where A is the area of a building (measured in square metres).

Furthermore, for 30% of the available marks, no building will have an area greater than 100.

Input

Your program must read from standard input. The first line will be a single integer N, denoting the total number of buildings that are required.

Following this will be N lines each describing a single building. Each of these lines will contain a single integer representing the area of the building (in square metres). Note that there may be several buildings each having the same area.

Output

Your program must write the best solution it can find to standard output. Your output should begin with N lines describing the N buildings in the order in which you construct them. Each of these lines should have the form A S, where A is the area of the building and S denotes which side of the river it is built on. The area A must be an integer (measured in square metres), and S must be a single lower-case letter "a" or "f", denoting the Australian or French side respectively.

After the buildings have been written, your program must write one additional line of output. This line must contain a single integer representing the total tax paid (in drachmas).

Sample Input

Sample Output

3 a
4 f
2 a
5

Scoring

There is no particular "best solution" that you are required to achieve. Instead, your score will be determined relative to the other contestants whom you are competing against (as well as the judges' solution).

For each input scenario, the contestant who achieves the least total tax will be identified. Suppose that this contestant obtains a total tax of T. Furthermore, let the average building area for the input scenario be M (so that M is the sum of all building areas divided by N). Your score for this input scenario will then be:

100% if your program finds a solution with this same least total tax T;
10% if your program finds a solution whose total tax is T + M or greater;
0% if your program generates an incorrect solution (e.g., you miss a building, construct a building more than once, or incorrectly calculate the total tax);
otherwise determined by a linear scale according to your total tax, with the 100% and 10% marks on the scale corresponding to the solutions described above.

For example, consider an input scenario for which the average building area is M = 90. If the best solution found by any contestant (or the judges) has a total tax of 400, then the scoring scale for a correct solution would be as follows:

Total tax	400	420	440	460	480	490	500	510
Score	100%	80%	60%	40%	20%	10%	10%	10%