SegmentTree

template <typename Segment>
struct SegmentTree {
  int n;
  mutable std::vector<Segment> a;

  void pull(int x, int l, int r) {
    int m = l + (r - l) / 2;
    a[x] = a[x + 1] + a[x + 2 * (m - l)];
  }

  explicit SegmentTree(int arg_n) : n(arg_n) {
    assert(n > 0);
    a.resize(2 * n - 1);
    auto build = [&](auto&& self, int x, int l, int r) -> void {
      if (r - l == 1) {
        return;
      }
      int m = l + (r - l) / 2;
      self(self, x + 1, l, m);
      self(self, x + 2 * (m - l), m, r);
      pull(x, l, r);
    };
    build(build, 0, 0, n);
  }

  template <typename M>
  explicit SegmentTree(const std::vector<M>& v) {
    assert(!v.empty());
    n = int(v.size());
    a.resize(2 * n - 1);
    auto build = [&](auto&& self, int x, int l, int r) -> void {
      if (r - l == 1) {
        a[x] = Segment(v[l]);
        return;
      }
      int m = l + (r - l) / 2;
      self(self, x + 1, l, m);
      self(self, x + 2 * (m - l), m, r);
      pull(x, l, r);
    };
    build(build, 0, 0, n);
  }

  template <typename... Types>
  void modifyImpl(int x, int l, int r, int p, Types&&... args) {
    if (r - l == 1) {
      a[x].apply(args...);
      return;
    }
    int m = l + (r - l) / 2;
    if (p < m) {
      modifyImpl(x + 1, l, m, p, args...);
    } else {
      modifyImpl(x + 2 * (m - l), m, r, p, args...);
    }
    pull(x, l, r);
  }

  template <typename... Types>
  void modify(int p, Types&&... args) {
    assert(0 <= p && p < n);
    modifyImpl(0, 0, n, p, args...);
  }

  Segment getImpl(int x, int l, int r, int ll, int rr) const {
    if (ll <= l && r <= rr) {
      return a[x];
    }
    int m = l + (r - l) / 2;
    if (rr <= m) {
      return getImpl(x + 1, l, m, ll, rr);
    } else if (m <= ll) {
      return getImpl(x + 2 * (m - l), m, r, ll, rr);
    } else {
      return getImpl(x + 1, l, m, ll, rr) + getImpl(x + 2 * (m - l), m, r, ll, rr);
    }
  }

  Segment get(int ll, int rr) const {
    assert(0 <= ll && ll < rr && rr <= n);
    return getImpl(0, 0, n, ll, rr);
  }

  template <typename F>
  int findFirstImpl(int x, int l, int r, int ll, int rr, F&& func) const {
    if (rr <= l || r <= ll) {
      return -1;
    }
    if (ll <= l && r <= rr && !func(a[x])) {
      return -1;
    }
    if (r - l == 1) {
      return l;
    }
    int m = l + (r - l) / 2;
    int res = findFirstImpl(x + 1, l, m, ll, rr, func);
    if (res == -1) {
      res = findFirstImpl(x + 2 * (m - l), m, r, ll, rr, func);
    }
    return res;
  }

  template <typename F>
  int findFirst(int ll, int rr, F&& func) const {
    return findFirstImpl(0, 0, n, ll, rr, func);
  }

  template <typename F>
  int findLastImpl(int x, int l, int r, int ll, int rr, F&& func) const {
    if (rr <= l || r <= ll) {
      return -1;
    }
    if (ll <= l && r <= rr && !func(a[x])) {
      return -1;
    }
    if (r - l == 1) {
      return l;
    }
    int m = l + (r - l) / 2;
    int res = findLastImpl(x + 2 * (m - l), m, r, ll, rr, func);
    if (res == -1) {
      res = findLastImpl(x + 1, l, m, ll, rr, func);
    }
    return res;
  }

  template <typename F>
  int findLast(int ll, int rr, F&& func) const {
    return findLastImpl(0, 0, n, ll, rr, func);
  }
};