musou1500

template <typename T>
class LazySegmentTree {
  vector<T> data_;
  vector<T> lazy_;
  int size_;

  void Eval(int k) {
    if (lazy_[k] == 0) {
      return;
    }

musou1500

bool ntersects(double ax, double ay, double bx, double by, double cx,
                double cy, double dx, double dy) {
  double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
  double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
  double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
  double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);

  return tc * td < 0 && ta * tb < 0;
};

musou1500

vector<vector<int>> Dim2PartialSum(vector<vector<int>> &mat, int w, int h) {
  vector<vector<int>> psum(h + 1, vector<int>(w + 1, 0));
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      psum[i + 1][j + 1] =
          psum[i + 1][j] + psum[i][j + 1] + mat[i][j] - psum[i][j];
    }
  }

  return psum;

musou1500

struct Edge {
  int from, to, cost;
  Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
};

vector<optional<int>> BellmanFord(vector<Edge> &edges, int src, int node_size) {
  vector<optional<int>> dists(node_size);
  dists[src] = 0;
  for (int i = 0; i < node_size; ++i) {
    for (auto &e : edges) {

musou1500

double l = 0, r = 1000;
for (int i = 0; i < 80; ++i) {
  double c1, c2;
  c1 = (l * 2 + r) / 3;
  c2 = (l + r * 2) / 3;
  if (f(c1) > f(c2)) {
    l = c1;
  } else {
    r = c2;
  }

musou1500

struct Edge {
  int to, cap, rev;
  Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};

void AddEdge(vector<vector<Edge>> &g, int from, int to, int cap) {
  int idx = g[to].size(), rev_idx = g[from].size();
  g[from].emplace_back(to, cap, idx);
  g[to].emplace_back(from, 0, rev_idx);
}

musou1500

class Eratosthenes {
 private:
  vector<bool> is_prime_;
 public:
  Eratosthenes(int max_n): is_prime_(max_n + 1, true) {
    is_prime_[0] = is_prime_[1] = false;
    for (int i = 2; i < is_prime_.size(); i++) {
      if (!is_prime_[i]) {
        continue;
      }

musou1500

using ll = long long;

ll Inchworm(vector<ll> &va, ll k) {
  ll left, right, sum, ans;
  left = right = sum = ans = 0;
  while (left < va.size()) {
    while (right < n && sum + va[right] < k) {
      sum += va[right];
      right++;
    }

musou1500

int LcsLen(string &s, string &t, vector<vector<int>> &memo, int i, int j) {
  if (i < 0 || j < 0) {
    return 0;
  }

  if (memo[i][j] < 0) {
    if (s[i] == t[j]) {
      memo[i][j] = LcsLen(s, t, memo, i - 1, j - 1) + 1;
    } else {
      memo[i][j] =

musou1500

ll left = 0, right = max_n;
while (right - left > 1) {
  ll mid = (left + right) / 2;
  if (check(va, vf, mid, k)) {
    right = mid;
  } else {
    left = mid;
  }
}