1390. Sum of All XOR Triplets in Array

Given an array of non-negative integers, consider every triplet of indices (i, j, k) with i < j < k and compute nums[i] XOR nums[j] XOR nums[k]. Return the sum of these values over all triplets.

Input: A JSON object {"nums": [<non-negative integers>]}.

Output: Return the sum of the XOR over all triplets.

Examples

Input: {"nums":[1,2,3,4]}
Output: 18
Explanation: The four triplet XORs sum to 18.

Input: {"nums":[1,3,5]}
Output: 7
Explanation: The single triplet 1 XOR 3 XOR 5 = 7.

Constraints

• 3 <= len(nums) <= 10^5
• 0 <= nums[i] < 2^20

Asked by