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
2015-06-03 16:34:10 vivek
getting WA in 5th case :(
2015-05-27 15:10:58 Samar Holkar
use unsigned long long , long long gave wa
2015-02-23 18:39:58 Soumik Chatterjee
getting TLE in 10th case.. will the bitwise xor work? help please
2015-01-12 17:26:55 Jugal kishor sahu
AC in one go......waooooooooo
2014-12-14 11:55:33 Deepak Gupta
For n==1, ans=0
2014-10-12 15:05:21 Raj Kumar
What will be the output when N=1 ???
2014-07-05 07:04:54 `Ak
<snip> why giving tle :(

Last edit: 2022-08-17 17:42:53
2014-06-29 10:24:11 .:frUstrAteD:.
150 :) gud question
2014-06-18 10:08:43 Amitayush Thakur
int cost me 6 WAs so use long long :D
2014-02-20 14:34:00 Flago
Could you check my submissions 11101726 and 11101722 and tell me why one pass and the other don't ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.