Evolution of molecules (2) X62507

In an experiment with n molecules of several integer weights, a curious phenomenon has been detected. Repeatedly, the two heaviest molecules are combined, they disappear, and generate a new molecule. If the heaviest molecule has weight x, and the second heaviest has weight y, there are two possibilities. If the last digit of x and y is the same, a fusion of type A takes place and the new molecule will have weight x − ⌊ y/2 ⌋. If their last digit is different, a fusion of type B happens and the new molecule will have weight x − ⌊ y/4 ⌋. The process finishes when only one molecule exists.

For example, if the initial weights are 21, 6, 3 and 20, first of all 21 and 20 are combined with a fusion of type B and generate a molecule with weight 21 − ⌊ 20/4 ⌋ = 21 − 5 = 16. We now have 6, 3 and 16, and 16 and 6 are combined via a type A fusion, generating 16 − ⌊ 6/2 ⌋ = 16 − 3 = 13. We now have 3 and 13, that are combined with a fusion of type A and generate 13 − ⌊ 3/2 ⌋ = 13 − 1 = 12, that is the weight of the final molecule. In the overall process, two fusions of type A and one fusion of type B have occurred.

Write a program that efficiently simulates this process and writes the weight of the last molecule and the number of fusions of each type.

Input

The input consists of several cases. Each case begins with the number of molecules n, followed by n weights, which are integers between 1 and 10⁹. You can assume that 1 ≤ n ≤ 10⁵.

Output

For each case, write the weight of the last molecule, followed by the number of fusions of type A and the number of fusions of type B.

Observation

We advise you not to use multisets to solve this problem.