class Solution { private:  template <class Monoid, class OperatorMonoid>  struct lazy_propagation_segment_tree { // on monoids    static_assert (std::is_same<typename Monoid::value_type, typename OperatorMonoid::target_type>::value, "");    typedef typename Monoid::value_type value_type;    typedef typename OperatorMonoid::value_type operator_type;    const Monoid mon;    const OperatorMonoid op;    int n;    std::vector<value_type> a;    std::vector<operator_type> f;    lazy_propagation_segment_tree() = default;#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))    lazy_propagation_segment_tree(int a_n, value_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid(), OperatorMonoid const & a_op = OperatorMonoid())        : mon(a_mon), op(a_op) {      n = 1; while (n <= a_n) n *= 2;      a.resize(2 * n - 1, mon.unit());      std::fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values      REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values      f.resize(std::max(0, (2 * n - 1) - n), op.identity());    }        void point_set(int i, value_type z) {      assert (0 <= i and i < n);      point_set(0, 0, n, i, z);    }        void point_set(int i, int il, int ir, int j, value_type z) {      if (i == n + j - 1) { // 0-based        a[i] = z;      } else if (ir <= j or j+1 <= il) {        // nop      } else {        range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);        range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);        f[i] = op.identity();        point_set(2 * i + 1, il, (il + ir) / 2, j, z);        point_set(2 * i + 2, (il + ir) / 2, ir, j, z);        a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);      }    }        void range_apply(int l, int r, operator_type z) {      cout << "l: " <<  l << "r: " << r << endl;      assert (0 <= l and l <= r and r <= n);      range_apply(0, 0, n, l, r, z);    }        void range_apply(int i, int il, int ir, int l, int r, operator_type z) {      if (l <= il and ir <= r) { // 0-based        a[i] = op.apply(z, a[i]);        if (i < f.size()) f[i] = op.compose(z, f[i]);      } else if (ir <= l or r <= il) {        // nop      } else {        range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);        range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);        f[i] = op.identity();  // unnecessary if the oprator monoid is commutative        range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);        range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);        a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);      }    }        value_type range_concat(int l, int r) {      cout << "l: " <<  l << "r: " << r << endl;      assert (0 <= l and l <= r and r <= n);      value_type lacc = mon.unit(), racc = mon.unit();      for (int l1 = (l += n), r1 = (r += n) - 1; l1 > 1; l /= 2, r /= 2, l1 /= 2, r1 /= 2) { // 1-based loop, 2x faster than recursion        if (l < r) {          if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);          if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);        }        lacc = op.apply(f[l1 / 2 - 1], lacc);        racc = op.apply(f[r1 / 2 - 1], racc);      }      return mon.append(lacc, racc);    }  };    struct max_monoid {    typedef int value_type;    int unit() const { return 0; }    int append(int a, int b) const { return std::max(a, b); }  };    struct plus_operator_monoid {    typedef int value_type;    typedef int target_type;    int identity() const { return 0; }    int apply(value_type a, target_type b) const { return a + b; }    int compose(value_type a, value_type b) const { return a + b; }  };// typedef lazy_propagation_segment_tree<max_monoid, plus_operator_monoid> starry_sky_tree;   public:    vector<int> fallingSquares(vector<vector<int>>& positions) {    cout << "haha" << endl;    auto buttom_end_points = [&]() -> vector<int> {      unordered_set<int> coords;      for (const auto & pos : positions) {        coords.insert(pos[0]);        coords.insert(pos[1] - 1);      }      vector<int> end_pts(coords.begin(), coords.end());      sort(end_pts.begin(), end_pts.end());      return end_pts;    };        auto coordinate_compression = [&](const vector<int>& coordinates) -> unordered_map<int,int> {      vector<int> unique_coords = buttom_end_points();      unordered_map<int, int> compressed_coords;      for (int i = 0; i < unique_coords.size(); i++) {        compressed_coords[unique_coords[i]] = i;      }      return compressed_coords;    };                auto run = [&]() {      vector<int> ret;      int n = positions.size() - 1;      unordered_map<int, int> coordinates = coordinate_compression(buttom_end_points());      lazy_propagation_segment_tree<max_monoid, plus_operator_monoid> segtree(n);      for (const auto & square : positions) {        int l = square[0];        int r = square[0] + square[1] - 1;        int h = square[1];        segtree.range_apply(l, r, h);        ret.emplace_back(segtree.range_concat(0, n));      }      return ret;    };    return run();            }};