FRND - FRIENDSHIP!!!

Q[b] has recently been visited by extra-terrestrials from planet Quan_Lank, where everyone’s name is a positive integer. All residents of the planet know each other. Two Quan_Lank-ians calculate the strength of their friendship by converting their names to binary, aligning them one under the other, and writing a digit in each column: 0 if the two binary digits in that column are equal, 1 if they differ. The binary result is then converted back to the decimal system.

For example, the friendship value of 19 and 10 equals 25:

1   0   0   1   1   =  19
0   1   0   1   0   =  10
-------------------------
1   1   0   0   1   =  25

The value of a planet in the Universe is defined as the sum of all friendship values. Q[b] has asked you to help him compute the value of planet Quan_Lank!

Input

The first line of input contains the positive integer N (the number of residents of planet Quan_Lank , 1<=N<=10^6).
The next N lines contain the names of residents - positive integers smaller than 10^6, one per line.

Output

The only line of output must contain the value of planet Quan_Lank.

Sample

Input:
2
19
10
Output:
25
Input:
3
7
3
5
Output:
12

Second sample description: The friendship value of residents 1 and 2 equals 4, for residents 1 and 3 it equals 2, and for residents 2 and 3 it equals 6. The solution is 4 + 2 + 6 = 12.


Added by:BLANKRK
Date:2014-01-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2016-08-11 15:11:47
array of bitset leads to RTE
2016-08-03 21:26:32 zany
submitted code in C++ A.C same code in python giving TLE!
2016-06-22 21:38:55
very good ques.!! bit but u have to think more than a bit :-P
2016-05-11 15:21:06
getting wrong answer in 10th test case :(
though I used unsigned long long int

Last edit: 2016-05-11 15:21:50
2016-01-20 18:19:09 DHEERAJ KUMAR
Try http://www.spoj.com/problems/BITDIFF/ before doing this. Concept is somewhat same :)
2016-01-20 18:13:47 DHEERAJ KUMAR
Use long long for bit computation. Easy one :)
2015-12-06 11:56:17 Filip Sollar
can u check please submission 15791805? no idea why getting wa my solution is O(nk) or someone give me an additional test case tried using long long and even long long unsigned

Last edit: 2015-12-06 11:57:41
2015-11-07 20:47:35 :.Mohib.:
A very nice que.....!!
2015-09-07 14:58:21 Parul Yadav
great q!
2015-06-14 01:12:44 hackab
For n==1, ans!=0
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.