const int N = 20;

int bit_n[1 << N];

forn(i, 1 << N)
  bit_n[i] = bit_n[i >> 1] + (i & 1);

forn(i, 1 << N)
  ; // A \subset B : как числа A <= B

int w[N];
int sum[1 << N]; // sum[A] = w[a1] + ... + w[ak] (ai \in A)

int bit = 0;
for (int i = 1; i < (1 << N); i++) { // O(2^N)
  // i   = 0000010000000
  // i-1 = 0000001111111
  // if (!(i & (i - 1))) // i -- степень двойки
  //   bit++;
  if ((1 << (bit + 1)) <= i) // bit = max число : 2^{bit} <= i
    bit++;
  sum[i] = sum[i ^ (1 << bit)] + w[bit];
}

forn(i, n)
  sum[1 << i] = w[i];
for (int i = 1; i < (1 << N); i++)  {
  int L = i & ~(i - 1); // 2^{младший бит}
  sum[i] = sum[i ^ L] + sum[L];
}