URI Online Judge | 2239

Hex Statistics

By Maratona de Programação da SBC – 2016 BR Brazil

Timelimit: 1

Given a sequence of positive integers in hexadecimal, for example, S = [9af47c0b, 2,545,557, ff6447979], we define the sum (S) as the sum of all elements S. Now consider some permutation of the 16 hexadecimal digits, e.g. p = [4, 9; 5, 0, c, f, 3 d, 7, 8, b, 1, 2, 6, and]. From the S base sequence, we can define a transformed S[4] sequence, which is obtained by removing all ocorrêcias hexadecimal digit 4 of all integers of S, S[4] = [9af7c0b, 255557, ff67979]. Then we can remove the digit 9 and get S[4,9] = [af7c0b, 255557, ff677]. Following the order of the digits in the permutation p, we can define this way 16 sequences: S[4] , S[4,9] , S[4,9,5] ,...,S[4,9,5,a,0,c,f,3,d,7,8,b,1,2,6,e]. We are interested in adding all the elements of these 16 sequences:

total (S, p) = sum (S [4]) + sum (S [4,9]) + sum (S [4,9,5]) + ··· + sum (S [4,9,5 , a, 0, c, f, 3, d, 7.8, b, 1,2,6, e])

Clearly, all this depends on the permutation p used in subsequent removal. Given a positive integer N sequence in hex, your program must compute, considering all the possible permutations of the 16 hexadecimal digits: the minimum total, the maximum total and the sum of the total of all permutations. For the sum total of all the permutations, print the result 3b9aca07 module (109 + 7 in base 10).

Input

The first line of input contains an integer N, 1 ≤ N ≤ 3f, representing the size of the sequence. The following N lines contain each a positive integer P, 0 ≤ P ≤ fffffffff setting the initial sequence S integers. All numbers in the input are in hexadecimal, with lowercase letters.

Output

Your program should produce a single line in the output containing three positive integers in hexadecimal with lowercase letters, representing the total minimum, the maximum total and the total sum of considering all the possible permutations of the 16 hexadecimal digits.

Exemplos de Entrada Exemplos de Saída

3
9af47c0b
2545557
ff6447979

1312c99c b4e87e9387 5bb5fc

1
fffffffff

0 effffffff1 15dac189