output_description: Print N lines. The i-th line should contain the value f(X_i).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      X
attempt: import heapq as hq
  
  T = int(input())
  for _ in range(T):
      N = int(input())
      camels = [list(map(int, input().split())) for _ in range(N)]
      base = 0
      camels_L = [[] for _ in range(N + 1)]
      camels_R = [[] for _ in range(N + 1)]
      # 左から詰めるラクダと右から詰めるラクダを仕分ける
  for camel in camels:
      if camel[1] >= camel[2]:
          camels_L[camel[0]].append(camel[1] - camel[2])
          base += camel[2]  # LとRの低いほうを加算
      else:
          # Rラクダは右から何列目かを考えるのでN - camel[0]と反転する
          camels_R[N - camel[0]].append(camel[2] - camel[1])
          base += camel[1]  # LとRの低いほうを加算
  
  diff = 0
  
  # Lラクダについて考える
  heap_camels = []
  hq.heapify(heap_camels)
  for i in range(1, N + 1):
      # 左からi番目までが限度のラクダをまとめて追加
      for camel in camels_L[i]:
          hq.heappush(heap_camels, camel)
          # 左からi番目までに入りきらない場合に低いものから除外
      while len(heap_camels) > i:
          hq.heappop(heap_camels)
          # heapqに残ったものがすべての条件を満たしうれしさが最大
      diff += sum(heap_camels)
  
      # Rラクダについても同様
  heap_camels = []
  hq.heapify(heap_camels)
  for i in range(1, N + 1):
      for camel in camels_R[i]:
          hq.heappush(heap_camels, camel)
      while len(heap_camels) > i:
          hq.heappop(heap_camels)
  diff += sum(heap_camels)
  print(diff + base)
  
problem_description: Statement
  
  Let \mathrm{popcount}(n) be the number of `1`s in the binary representation of
  n. For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and
  \mathrm{popcount}(0) = 0.
  
  Let f(n) be the number of times the following operation will be done when we
  repeat it until n becomes 0: "replace n with the remainder when n is divided
  by \mathrm{popcount}(n)." (It can be proved that, under the constraints of
  this problem, n always becomes 0 after a finite number of operations.)
  
  For example, when n=7, it becomes 0 after two operations, as follows:
  
    * \mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.
    * \mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.
  
  You are given an integer X with N digits in binary. For each integer i such
  that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top
  is inverted. Find f(X_1), f(X_2), \ldots, f(X_N).
samples: [{"input": "3\n    011", "output": "2\n    1\n    1\n    \n\n  * X_1 = 7, which will change as follows: 7 \\rightarrow 1 \\rightarrow 0. Thus, f(7) = 2.\n  * X_2 = 1, which will change as follows: 1 \\rightarrow 0. Thus, f(1) = 1.\n  * X_3 = 2, which will change as follows: 2 \\rightarrow 0. Thus, f(2) = 1.\n\n* * *"}, {"input": "23\n    00110111001011011001110", "output": "2\n    1\n    2\n    2\n    1\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    1\n    3"}]