Problem: zero_crossings_ch1 (2022 round3)

**Note: The only difference between this and [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-3/problems/E2) is that here, marble locations don't depend on previous answers.**

There are \(N\) rubber bands on an infinite 2D peg board. The \(i\)th rubber band is initially shaped as a [convex polygon](https://en.wikipedia.org/wiki/Convex_polygon) of \(M_i\) integer vertices, \((X_{i,1}, Y_{i,1}),\) \(\ldots,\) \((X_{i,M_i}, Y_{i,M_i})\) in clockwise order. No two rubber bands touch or cross each other, though each rubber band may be fully enclosed in another. Other than their initial layout, all rubber bands look identical.

You are given \(Q\) queries, the \(i\)th of which involves a red and blue marble shaped as a circle with radius \(1\), centered at points \((A_i, B_i)\) and \((C_i, D_i)\) respectively. The marbles do not touch each other, or any rubber bands. Formally, \((A_i, B_i)\) and \((C_i, D_i)\) are more than \(2\) units away from each other, and each more than \(1\) unit away from any rubber band. 

Query \(i\) asks whether you can roll the marbles and continuously move/deform rubber bands so:
- the red marble ends up at \((C_i, D_i)\),
- the blue marble ends up at \((A_i, B_i)\),
- the final state of all rubber bands looks identical to the initial state (one rubber band may end up in place of another, but must end up having the exact same vertices), and
- rubber bands never touch/cross, and the marbles never touch each other or any rubber band.

For example, the first sample case and the fifth query of the second case can be solved as follows:

{{PHOTO_ID:472941018189408|WIDTH:700}}

Let \(R_i = 1\) if the answer to the \(i\)th query is "yes", else \(R_i = 0\). Please find the sum of \(R_1, ..., R_Q\).


# Constraints

\(1 \le T \le 100\)
\(1 \le N \le 200{,}000\)
\(3 \le M_i \le 250{,}000\)
\(3 \le \sum_{i=1}^{N} M_i \le 800{,}000\)
\(1 \le Q \le 500{,}000\)
\(0 \le X_{ij}, Y_{ij} \le 10^9\)
\(0 \le A_i, B_i, C_i, D_i \le 10^9\)

The sum of \(M_i\) across all test cases is at most \(3{,}000{,}000\).
The sum of \(Q\) across all test cases is at most \(2{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. For the \(i\)th test case, there is first a line containing a single integer \(N\). Then, \(N\) descriptions of polygons follow, the \(i\)th of which consists of two lines: the first containing a single integer \(M_i\) and the second containing \(2*M_i\) space-separated integers \(X_{i,1}\), \(Y_{i,1}\), \(\ldots\), \(X_{i,M_i}\), \(Y_{i,M_i}\). Then, there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains four space-separated integers \(A_i\), \(B_i\), \(C_i\), \(D_i\).


# Output Format

For the \(i\)th test case, print `"Case #i: "` followed by a single integer, the sum \(R_1 + ... + R_Q\).


# Sample Explanation

In the first case, the only query is possible, as depicted above on the left.

In the second case, \(R = [1, 1, 0, 0, 1, 1, 0]\).

In the third case, the only query is not possible as one marble is inside the rubber band, while the other is outside. If the marbles swap places, then the rubber band will be surrounding the wrong marble.


Sample input:
4
4
3
17 13 18 11 16 11
4
1 1 1 2 2 2 2 1
8
15 8 15 4 12 1 5 1 2 4 2 8 5 11 12 11
4
5 4 5 8 12 8 12 4
1
7 6 10 6
7
6
10 90 20 90 30 80 20 70 10 70 0 80
5
10 0 0 50 10 60 100 100 100 0
4
30 40 30 60 90 90 90 40
4
90 20 90 10 40 10 30 30
3
20 10 10 50 30 20
3
40 50 40 60 50 50
3
60 50 80 70 80 50
7
10 80 20 80
30 90 40 90
40 90 20 80
60 70 70 55
20 20 40 20
30 10 90 30
90 30 30 90
1
3
0 4 7 7 3 0
1
3 4 2 6
1
4
0 4 0 1000000000 7 7 3 0
1
3 4 2 6


Sample output:
Case #1: 1
Case #2: 4
Case #3: 0
Case #4: 1


Solution: It'd be easier to think about the problem if the marbles were simply points rather than circles with nonzero radii. It turns out this is actually an equivalent problem. We can imagine scaling everything up by a factor of \(10^{100}\) as our first action. Now there will always be space for the marbles to move past each other, so we don't need to worry about their radii. Once we achieve the desired positions, we can scale everything back down as the last step.

The question that remains is whether the two polygons containing each marble are "topologically equivalent." We will get to what this means later.

For each edge in a hull, we will store which hull it is part of, and whether it's on the upper or lower half of that hull.

We can observe that the relationships between enclosed polygons forms a tree. We'll have to build this structure and be able to find the polygon that contains a given point. We can use a line sweep from left to right, maintaining a sorted set \(S\) of all of edges spanning the current \(x\) coordinate, sorted by increasing \(y\) coordinates. During insertion/deletion, \(S\) uses a custom comparator that evaluates each line inside at the current \(x\). Note that as lines never cross, this relative order will be maintained at every \(x\), and so the set will always be well-ordered despite dynamically changing \(x\) within the comparator logic.

In the offline version of this problem, we'll also add all query points to the set. When our sweep line reaches the start or end of a line, we'll add it to or remove it from \(S\). When we get to a query point (or the leftmost line in a rubber band), we use a floor/lower bound search on \(S\) (again with a custom comparator by \(y\) value) to find the line immediately below us:
* If the line below us is in the lower convex hull of its rubber band, this means it is our parent, and this polygon's parent is ours as well.
* If the line below us is part of an upper hull, then it must be our sibling. We can set our parent to its parent. Note that since we are sweeping from bottom to top, we must have already encountered this line, and so its parent is guaranteed to have already been determined.

Having computed the tree structure of all nodes and which node corresponds to each query point, all that remains is checking whether two nodes \(u\) and \(v\) are topologically equivalent. Hashing would seem appropriate here. Let us define the *subtree hash* of a node as a constant (fixed globally) combined with its children's subtree hashes using an associative hash function.

Some wrong ideas include only requiring the subtree hashes of \(u\) and \(v\) to be equal, or only requiring the subtree hashes of children of the lowest common ancestor of \(u\) and \(v\) to be equal. Instead, it is important for us to us to also check that the nodes are topologically-equivalently-situated with respect to their ancestors' structures as well.

Namely, we can define the *root-path hash* of each node to be the root-path hash of its parent joined non-commutatively with the node itself's subtree hash. Two nodes are topologically equivalent if and only if their root-path hashes are equal. First we'll compute all subtree hashes for all nodes from the bottom up using DFS. Then, the root-path hash can be computed for each node using another DFS, where we pass the root-path hash of each parent downwards.

The sweep line algorithm will run in \(\mathcal{O}((V + Q) \log V)\) where \(V\) is the total number of polygon vertices, while building the graph and hashing all nodes will take \(\mathcal{O}(N)\). After this is done, each query can be answered in \(\mathcal{O}(1)\) time.




Code: import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

public class ZeroCrossingsCh1 {
  static double globalX = 0;

  static void solve(Scanner fs, PrintWriter out, int tt) {
    int nHulls = fs.nextInt();
    Hull[] hulls = new Hull[nHulls + 1];
    for (int i = 0; i < nHulls; i++) {
      hulls[i] = new Hull(fs);
    }
    hulls[nHulls] = new Hull();
    for (int i = 0; i <= nHulls; i++) {
      hulls[i].id = i;
    }
    ArrayList < Event > events = new ArrayList<>();
    for (Hull h: hulls) {
      events.addAll(h.getEvents());
    }

    int nQ = fs.nextInt();
    Query[] queries = new Query[nQ];
    for (int qq = 0; qq < nQ; qq++) {
      queries[qq] = new Query(fs);
      events.addAll(queries[qq].getEvents());
    }
    Collections.sort(events);

    TreeSet<Seg> set = new TreeSet<>((a, b) -> {
      double ay = a.evalAt(globalX),
      by = b.evalAt(globalX);
      return Double.compare(ay, by);
    });
    for (Event e: events) {
      globalX = e.x;
      if (e.qp != null) {
        Vec position = e.qp.position;
        Seg hSeg = new Seg(position, position.add(new Vec(1, 0)));
        Seg higher = set.higher(hSeg);
        e.qp.node = parent(higher, hulls[nHulls]);
      } else {
        if (e.isEval) {
          Seg higher = set.higher(e.s);
          e.s.hull.parent = parent(higher, hulls[nHulls]);
          e.s.hull.parent.children.add(e.s.hull);
        } else if (e.isStart) {
          set.add(e.s);
        } else {
          set.remove(e.s);
        }
      }
    }
    hulls[nHulls].calcSubtreeHash();
    hulls[nHulls].calcAllHash(new HarmeyerHash(), new HarmeyerHash());

    int ans = 0;
    for (Query qq: queries) {
      Hull node1 = qq.qp1.node, node2 = qq.qp2.node;
      boolean possible = node1.allHash.equals(node2.allHash);
      if (possible) ans++;
    }
    out.println("Case #" + tt + ": " + ans);
  }

  static Hull parent(Seg higher, Hull rootHull) {
    if (higher == null) {
      return rootHull;
    } else if (higher.isUpper) {
      //father
      return higher.hull;
    } else {
      //brother
      return higher.hull.parent;
    }
  }

  // at a particular x:
  // query points (-0.3)
  // removals (-0.1)
  // additions(+0.1)
  // evals(+0.3)
  static class Event implements Comparable < Event > {
    double x,
    y;
    boolean isStart;
    boolean isEval;
    Seg s;
    QueryPoint qp;
    public Event(boolean isStart, Seg s, QueryPoint qp, boolean isEval) {
      this.isStart = isStart;
      this.isEval = isEval;
      this.s = s;
      this.qp = qp;
      if (this.s == null) {
        x = qp.position.x - 0.3;
      } else {
        if (isStart) {
          x = s.from.x + 0.1;
        } else if (isEval) {
          x = s.from.x + 0.3;
          y = s.from.y;
        } else {
          x = s.to.x - 0.1;
        }
      }
    }
    public int compareTo(Event o) {
      if (x != o.x) return Double.compare(x, o.x);
      //process higher y first, since we look upwards
      return Double.compare(o.y, y);
    }
  }

  static class Hull implements Comparable < Hull > {
    int nPoints;
    Vec[] points;
    Vec[] upperHull,
    lowerHull;
    Seg[] upperHullSegs,
    lowerHullSegs;
    int id;

    Hull parent;
    ArrayList < Hull > children = new ArrayList<>();
    HarmeyerHash subtreeHash;
    HarmeyerHash allHash;

    //root hull
    public Hull() {}

    public Hull(Scanner fs) {
      nPoints = fs.nextInt();
      points = new Vec[nPoints];
      for (int i = 0; i < nPoints; i++) {
        points[i] = new Vec(fs.nextInt(), fs.nextInt());
      }
      if (area() < 0) {
        Vec[] newPoints = new Vec[nPoints];
        for (int i = 0; i < nPoints; i++) newPoints[i] = points[nPoints - 1 - i];
        points = newPoints;
      }
      Vec[] sorted = points.clone();
      Arrays.sort(sorted, (a, b) -> {
        if (a.x != b.x) return Double.compare(a.x, b.x);
        return Double.compare(a.y, b.y);
      });
      int leftInd = 0, rightInd = 0;
      for (int i = 0; i < nPoints; i++)
        if (points[i] == sorted[0]) leftInd = i;
      for (int i = 0; i < nPoints; i++)
        if (points[i] == sorted[nPoints - 1]) rightInd = i;
      if (rightInd < leftInd) rightInd += nPoints;
      lowerHull = new Vec[rightInd - leftInd + 1];
      for (int i = leftInd; i <= rightInd; i++) lowerHull[i - leftInd] = points[i % nPoints];

      while (leftInd < rightInd) leftInd += nPoints;
      upperHull = new Vec[leftInd - rightInd + 1];
      for (int i = rightInd; i <= leftInd; i++) upperHull[leftInd - i] = points[i % nPoints];

      upperHullSegs = new Seg[upperHull.length - 1];
      for (int i = 0; i + 1 < upperHull.length; i++) upperHullSegs[i] = new Seg(upperHull[i], upperHull[i + 1]);
      lowerHullSegs = new Seg[lowerHull.length - 1];
      for (int i = 0; i + 1 < lowerHull.length; i++) lowerHullSegs[i] = new Seg(lowerHull[i], lowerHull[i + 1]);

      for (Seg s: upperHullSegs) {
        s.isUpper = true;
        s.hull = this;
      }
      for (Seg s: lowerHullSegs) {
        s.isUpper = false;
        s.hull = this;
      }
    }

    double area() {
      double area = 0;
      for (int i = 0; i < points.length; i++) {
        area += points[i].cross(points[(i + 1) % nPoints]);
      }
      return area / 2;
    }

    // Add events for all lines which aren't vertical.
    ArrayList < Event > getEvents() {
      if (nPoints == 0) {
        // Root query.
        return new ArrayList<>();
      }
      ArrayList < Event > res = new ArrayList<>();
      Seg firstUpper = null;
      for (Seg s: upperHullSegs) {
        if (s.isVertical()) continue;
        if (firstUpper == null) firstUpper = s;
        res.add(new Event(true, s, null, false));
        res.add(new Event(false, s, null, false));
      }
      for (Seg s: lowerHullSegs) {
        if (s.isVertical()) continue;
        res.add(new Event(true, s, null, false));
        res.add(new Event(false, s, null, false));
      }
      res.add(new Event(false, firstUpper, null, true));
      return res;
    }

    void calcSubtreeHash() {
      for (Hull hh: children) {
        hh.calcSubtreeHash();
      }
      Collections.sort(children);
      HarmeyerHash me = new HarmeyerHash();
      me.add('(');
      for (Hull hh: children) {
        me.append(hh.subtreeHash);
      }
      me.add(')');
      this.subtreeHash = me;
    }

    void calcAllHash(HarmeyerHash prefix, HarmeyerHash suffix) {
      prefix = prefix.clone();
      suffix = suffix.clone();
      allHash = new HarmeyerHash();
      allHash.add('s');
      allHash.append(prefix);
      allHash.add('S');
      allHash.append(subtreeHash);
      allHash.add('e');
      allHash.append(suffix);
      allHash.add('E');
      // Now we need to calculate this for our kids
      prefix.add('('); {
        HarmeyerHash temp = new HarmeyerHash();
        temp.add(')');
        temp.append(suffix);
        suffix = temp;
      }
      HarmeyerHash[] subtreesCS = new HarmeyerHash[children.size() + 1];
      subtreesCS[0] = new HarmeyerHash();
      for (int i = 1; i <= children.size(); i++) {
        subtreesCS[i] = subtreesCS[i - 1].clone();
        subtreesCS[i].append(children.get(i - 1).subtreeHash);
      }
      for (int at = 0; at < children.size(); at++) {
        int countIdentical = 1;
        while (at + countIdentical < children.size() &&
              children.get(at + countIdentical).subtreeHash.equals(
                  children.get(at).subtreeHash)) {
          countIdentical++;
        }
        HarmeyerHash beforeGroup = subtreesCS[at];
        HarmeyerHash afterMe = subtreesCS[children.size()].clone();
        afterMe.subHash(subtreesCS[at + 1]);
        HarmeyerHash groupPrefix = prefix.clone();
        groupPrefix.append(beforeGroup);
        HarmeyerHash groupSuffix = afterMe.clone();
        groupSuffix.append(suffix);
        for (int inGroup = 0; inGroup < countIdentical; inGroup++) {
          children.get(at + inGroup).calcAllHash(groupPrefix, groupSuffix);
        }
        at += countIdentical - 1;
      }
    }

    public int compareTo(Hull o) {
      return subtreeHash.compareTo(o.subtreeHash);
    }
  }

  static class QueryPoint {
    Query q;
    Vec position;
    Hull node;
    public QueryPoint(Query q, Vec p) {
      this.q = q;
      this.position = p;
    }
    Event getEvent() {
      return new Event(false, null, this, false);
    }
  }

  static class Query {
    QueryPoint qp1, qp2;
    public Query(Scanner fs) {
      Vec p1 = new Vec(fs.nextInt(), fs.nextInt());
      Vec p2 = new Vec(fs.nextInt(), fs.nextInt());
      qp1 = new QueryPoint(this, p1);
      qp2 = new QueryPoint(this, p2);
    }
    ArrayList < Event > getEvents() {
      ArrayList < Event > res = new ArrayList<>();
      res.add(qp1.getEvent());
      res.add(qp2.getEvent());
      return res;
    }
  }

  static class VecL implements Comparable < VecL > {
    long x, y;

    public VecL(long x, long y) {
      this.x = x;
      this.y = y;
    }

    public VecL add(VecL o) {
      return new VecL(x + o.x, y + o.y);
    }

    public VecL sub(VecL o) {
      return new VecL(x - o.x, y - o.y);
    }

    public VecL scale(long s) {
      return new VecL(x * s, y * s);
    }

    public long dot(VecL o) {
      return x * o.x + y * o.y;
    }

    public long cross(VecL o) {
      return x * o.y - y * o.x;
    }

    public long mag2() {
      return dot(this);
    }

    public VecL rot90() {
      return new VecL(-y, x);
    }

    public VecL rot270() {
      return new VecL(y, -x);
    }

    public String toString() {
      return "(" + x + ", " + y + ")";
    }

    public int hashCode() {
      return Long.hashCode(x << 13 ^ (y * 57));
    }

    public boolean equals(Object oo) {
      VecL o = (VecL) oo;
      return x == o.x && y == o.y;
    }

    public int compareTo(VecL o) {
      if (x != o.x) return Long.compare(x, o.x);
      return Long.compare(y, o.y);
    }

    // origin->q1, axes-> quadrant in ccw direction
    public int quadrant() {
      if (x == 0 || y == 0) {
        if (y == 0) {
          return x >= 0 ? 1 : 3;
        }
        return y >= 0 ? 2 : 4;
      }
      if (x > 0) {
        return y > 0 ? 1 : 4;
      }
      return y > 0 ? 2 : 3;
    }

    public int radialCompare(VecL o) {
      if (quadrant() == o.quadrant()) {
        return -Long.signum(cross(o));
      }
      return Integer.compare(quadrant(), o.quadrant());
    }
  }

  static class Vec {
    static final double EPS = 1e-6;

    double x, y;

    public Vec(double x, double y) {
      this.x = x;
      this.y = y;
    }

    public Vec add(Vec o) {
      return new Vec(x + o.x, y + o.y);
    }

    public Vec sub(Vec o) {
      return new Vec(x - o.x, y - o.y);
    }

    public Vec scale(double s) {
      return new Vec(x * s, y * s);
    }

    public double dot(Vec o) {
      return x * o.x + y * o.y;
    }

    public double cross(Vec o) {
      return x * o.y - y * o.x;
    }

    public double mag2() {
      return dot(this);
    }

    public double mag() {
      return Math.sqrt(mag2());
    }

    public Vec unit() {
      return scale(1 / mag());
    }

    public Vec rot90() {
      return new Vec(-y, x);
    }

    public Vec rot270() {
      return new Vec(y, -x);
    }

    public Vec rotate(double theta) {
      double PI = Math.PI;
      double newX = x * Math.cos(theta) + y * Math.cos(PI / 2 + theta);
      double newY = x * Math.sin(theta) + y * Math.sin(PI / 2 + theta);
      return new Vec(newX, newY);
    }

    // Angle between 0 and 2PI
    public double angle() {
      return (Math.atan2(y, x) + 2 * Math.PI) % (2 * Math.PI);
    }

    public String toString() {
      DecimalFormat df = new DecimalFormat("#.##");
      return "(" + df.format(x) + ", " + df.format(y) + ")";
    }

    static boolean eq(double a, double b) {
      return Math.abs(a - b) < EPS;
    }

    static boolean leq(double a, double b) {
      return a - EPS < b;
    }

    static boolean geq(double a, double b) {
      return a + EPS > b;
    }

    public boolean equals(Object oo) {
      Vec o = (Vec) oo;
      return eq(x, o.x) && eq(y, o.y);
    }
  }


  static class Seg {
    Vec from, to, dir;
    Hull hull;
    boolean isUpper;

    double m, b;

    public Seg(Vec from, Vec to) {
      this.from = from;
      this.to = to;
      dir = to.sub(from);
      if (!isVertical()) {
        m = dir.y / dir.x;
        b = from.y - m * from.x;
      }
    }

    boolean isVertical() {
      return Math.abs(dir.x) < 0.5;
    }

    double evalAt(double x) {
      return m * x + b;
    }

    //line-line intersection
    public Vec lineIntersect(Seg o) {
      double det = o.dir.x * dir.y - dir.x * o.dir.y;
      if (Vec.eq(det, 0)) {
        return null;
      }
      double dist = (o.dir.x * (o.from.y - from.y) -
                     o.dir.y * (o.from.x - from.x)) / det;
      return from.add(dir.scale(dist));
    }

    public boolean containsPoint(Vec o) {
      double distFromLine = dir.unit().cross(o.sub(from));
      if (!Vec.eq(distFromLine, 0)) {
        return false;
      }
      return Vec.eq(dir.mag(), from.sub(o).mag() + to.sub(o).mag());
    }

    // seg-seg intersection
    public Vec segIntersection(Seg o) {
      Vec intersect = lineIntersect(o);
      if (intersect == null) {
        return null;
      }
      return containsPoint(intersect) && o.containsPoint(intersect) ? intersect
                                                                    : null;
    }

    // returns 1 if above, 0 if on, -1 if below
    public int side(Vec o) {
      Vec oDir = o.sub(from);
      double distFromLine = dir.unit().cross(oDir);
      if (Vec.eq(distFromLine, 0)) {
        return 0;
      }
      return (int)Math.signum(distFromLine);
    }

    public boolean intersects(Seg o) {
      return side(o.from) != side(o.to) && o.side(from) != o.side(to);
    }

    public Vec getClosestTo(Vec o) {
      double percentThere = o.sub(from).dot(dir) / dir.mag2();
      return from.add(dir.scale(Math.max(0, Math.min(1, percentThere))));
    }

    public Vec projectToLine(Vec o) {
      return dir.scale(o.sub(from).dot(dir) / dir.mag2()).add(from);
    }

    // toContain must be a point with positive x and y coordinates.
    // this method returns the shortest line segment from the x-axis to the
    // point to the y axis
    public static Seg getShortestSegFromAxesContainingQ1Point(Vec toContain) {
      double slope = -Math.pow(toContain.y / toContain.x, 1.0 / 3);
      double b = toContain.y - toContain.x * slope;
      double xInt = -b / slope;
      return new Seg(new Vec(0, b), new Vec(xInt, 0));
    }

    public String toString() {
      return from + " -> " + to;
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread t = new Thread(null, null, "", 1 << 29) {
      public void run() {
        A(null);
      }
    };
    t.start();
    t.join();
  }

  public static void A(String[] args) {
    Scanner fs = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    long time = System.currentTimeMillis();
    int T = fs.nextInt();
    for (int tt = 0; tt < T; tt++) {
      solve(fs, out, tt + 1);
    }
    fs.close();
    out.close();
  }

  // Cannot use 0 as a character in the strings
  static class HarmeyerHash implements Comparable < HarmeyerHash > {
    static final long m1 = 8675309, m2 = 1_000_000_007, m3 = 1_000_000_009;
    long v1 = 0, v2 = 0, v3;
    int l = 0;
    static final long s1 = 257, s2 = 619, s3 = 10007;
    static long[] s1Pow, s2Pow, s3Pow;
    static boolean precomped = false;

    void add(char o) {
      v1 = (v1 * s1 + o) % m1;
      v2 = (v2 * s2 + o) % m2;
      v3 = (v3 * s3 + o) % m3;
      l++;
    }

    void subHash(HarmeyerHash smallerPrefix) {
      HarmeyerHash old = this;
      HarmeyerHash toSub = smallerPrefix;
      int diff = this.l - smallerPrefix.l;
      old.v1 = (old.v1 - (toSub.v1 * s1Pow[diff]) % m1 + m1) % m1;
      old.v2 = (old.v2 - (toSub.v2 * s2Pow[diff]) % m2 + m2) % m2;
      old.v3 = (old.v3 - (toSub.v3 * s3Pow[diff]) % m3 + m3) % m3;
      l = diff;
    }

    public int compareTo(HarmeyerHash o) {
      if (v1 != o.v1) {
        return Long.compare(v1, o.v1);
      }
      if (v2 != o.v2) {
        return Long.compare(v2, o.v2);
      }
      return Long.compare(v3, o.v3);
    }

    public boolean equals(Object o) {
      return compareTo((HarmeyerHash) o) == 0;
    }

    public int hashCode() {
      return (int)v1;
    }

    public HarmeyerHash clone() {
      HarmeyerHash toReturn = new HarmeyerHash();
      toReturn.v1 = v1;
      toReturn.v2 = v2;
      toReturn.v3 = v3;
      toReturn.l = l;
      return toReturn;
    }

    static void precomp() {
      if (precomped) {
        return;
      }
      precomped = true;
      s1Pow = new long[10_000_000];
      s2Pow = new long[10_000_000];
      s3Pow = new long[10_000_000];
      s1Pow[0] = s2Pow[0] = s3Pow[0] = 1;
      for (int i = 1; i < s1Pow.length; i++) {
        s1Pow[i] = (s1Pow[i - 1] * s1) % m1;
      }
      for (int i = 1; i < s2Pow.length; i++) {
        s2Pow[i] = (s2Pow[i - 1] * s2) % m2;
      }
      for (int i = 1; i < s3Pow.length; i++) {
        s3Pow[i] = (s3Pow[i - 1] * s3) % m3;
      }
    }

    //need fastPow if o can be longer than 10^6
    void append(HarmeyerHash o) {
      precomp();
      v1 = (v1 * s1Pow[o.l] + o.v1) % m1;
      v2 = (v2 * s2Pow[o.l] + o.v2) % m2;
      v3 = (v3 * s3Pow[o.l] + o.v3) % m3;
      l += o.l;
    }

    public static HarmeyerHash[] getPrefixHashes(char[] word) {
      precomp();
      int n = word.length;
      HarmeyerHash[] toReturn = new HarmeyerHash[n + 1];
      toReturn[0] = new HarmeyerHash();
      for (int i = 1; i <= n; i++) {
        toReturn[i] = toReturn[i - 1].clone();
        toReturn[i].add(word[i - 1]);
      }
      return toReturn;
    }

    //inclusive, exclusive
    public static HarmeyerHash substringHash(HarmeyerHash[] prefixHashes, int from, int to) {
      if (from == to) {
        return new HarmeyerHash();
      }
      HarmeyerHash old = prefixHashes[to].clone(), toSub = prefixHashes[from];
      int diff = to - from;
      old.v1 = (old.v1 - (toSub.v1 * s1Pow[diff]) % m1 + m1) % m1;
      old.v2 = (old.v2 - (toSub.v2 * s2Pow[diff]) % m2 + m2) % m2;
      old.v3 = (old.v3 - (toSub.v3 * s3Pow[diff]) % m3 + m3) % m3;
      old.l = to - from;
      return old;
    }

    public String toString() {
      return "[" + v1 + " " + v2 + " " + v3 + "]";
    }
  }
}