import java.util.*;

/**
 * There are 3 cases to consider:
 * 1. n=1. In this case the answer is -1.
 * 2. There is an odd number of sentries and they all lie on the same line.
 * 3. Everything else.
 *
 * For case (3) we do not have to move any sentries but we might have to rotate
 * some. Setup a graph that we will run a Min Cost Max Flow algorithm on. Get
 * the line of sentries that each sentry lies on. If there are more than two, on
 * any line, then there are some obstructions. Get the lines and sort the sentries
 * on the line. Sentries will only be able to see those that are adjacent on the
 * line. Additionally check which sentries are already staring at another sentry.
 * In the graph there will be two nodes for each sentry. Add an edge from node i
 * to node n+j with capacity 1 if Sentry i can be rotated to see Sentry j. Set the
 * cost of this edge to 0 if i is already looking at j and 1 otherwise.
 *
 * If there is an odd number of sentries and all sentries lie on a single line,
 * then we will need to move a sentry. Try moving each one to see which gives the
 * smallest cost. We need to check if there is a position that we can move each
 * sentry to such that it can see another and be seen by a sentry without rotating
 * either sentry. Use a 3D ray intersection check for this.
 *
 * Time Complexity: O(n^3)
 *
 * @author Finn Lidbetter
 */

public class who_watches_finn {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n==1) {
            System.out.println(-1);
            return;
        }
        Vector[] positions = new Vector[n];
        Vector[] dirs = new Vector[n];
        for (int i=0; i<n; i++) {
            long x = sc.nextInt();
            long y = sc.nextInt();
            long z = sc.nextInt();
            long vx = sc.nextInt();
            long vy = sc.nextInt();
            long vz = sc.nextInt();
            positions[i] = new Vector(x, y, z);
            dirs[i] = new Vector(vx, vy, vz);
        }
        HashMap<Line3D, HashSet<Integer>> linePoints = new HashMap<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<i; j++) {
                Vector line = positions[i].subtract(positions[j]).lineNormalised();
                Vector offset = positions[i];
                offset = offset.normalShift(line);
                Line3D normalRep = new Line3D(offset, line);
                if (linePoints.containsKey(normalRep)) {
                    HashSet<Integer> currLinePoints = linePoints.get(normalRep);
                    currLinePoints.add(i);
                    currLinePoints.add(j);
                } else {
                    HashSet<Integer> currLinePoints = new HashSet<Integer>();
                    currLinePoints.add(i);
                    currLinePoints.add(j);
                    linePoints.put(normalRep, currLinePoints);
                }
            }
        }
        HashMap<Line3D, ArrayList<Integer>> sortedLinePointsMap = new HashMap<>();
        for (Line3D line: linePoints.keySet()) {
            HashSet<Integer> pointSet = linePoints.get(line);
            ArrayList<Wrapper> sortableVectors = new ArrayList<>();
            for (int vIndex: pointSet) {
                sortableVectors.add(new Wrapper(vIndex, positions[vIndex]));
            }
            Collections.sort(sortableVectors);
            ArrayList<Integer> sortedIndices = new ArrayList<>();
            for (Wrapper w: sortableVectors) {
                sortedIndices.add(w.id);
            }
            sortedLinePointsMap.put(line, sortedIndices);
        }
        // visible[i][j] is True iff i and j can see each other if rotated.
        boolean[][] visible = new boolean[n][n];
        for (int i=0; i<n; i++) {
            Arrays.fill(visible[i], true);
        }
        for (Line3D line: sortedLinePointsMap.keySet()) {
            ArrayList<Integer> sortedLinePoints = sortedLinePointsMap.get(line);
            /*
            System.out.printf("Line: %s\n", line);
            for (int i=0; i<sortedLinePoints.size(); i++) {
                System.out.printf("\t%d->%d: %s\n", i, sortedLinePoints.get(i), positions[sortedLinePoints.get(i)]);
            }
             */
            for (int i=0; i<sortedLinePoints.size(); i++) {
                for (int j=0; j<sortedLinePoints.size(); j++) {
                    if (i-j == 1 || j-i == 1) {
                        visible[sortedLinePoints.get(i)][sortedLinePoints.get(j)] = true;
                        visible[sortedLinePoints.get(j)][sortedLinePoints.get(i)] = true;
                    } else {
                        visible[sortedLinePoints.get(i)][sortedLinePoints.get(j)] = false;
                        visible[sortedLinePoints.get(j)][sortedLinePoints.get(i)] = false;
                    }
                }
            }
        }
        // staring[i][j] is True iff i is already staring in the direction of j.
        boolean[][] staring = new boolean[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (i == j) {
                    continue;
                }
                Vector diff = positions[j].subtract(positions[i]);
                if (diff.cross(dirs[i]).isZero() && diff.dot(dirs[i]) > 0) {
                    staring[i][j] = true;
                }
            }
        }

        if (n%2 == 1 && linePoints.size() == 1) {
            // All sentries are on a single line and there is an odd number of
            // them, so we have to move one.
            // We are going to make a loop.
            // Try moving each sentry and try both directions of the loop.
            Vector lineDir = null;
            ArrayList<Integer> sortedPoints = null;
            // Iterate but there should only be one line in the map.
            for (Line3D line: sortedLinePointsMap.keySet()) {
                lineDir = line.dir;
                sortedPoints = sortedLinePointsMap.get(line);
            }
            int bestCost = oneLineOddCase(positions, dirs, lineDir, sortedPoints);
            System.out.println(bestCost);
            return;
        }
        long[][] cap = new long[2*n+2][2*n+2];
        long[][] cost = new long[2*n+2][2*n+2];
        for (int i=0; i<n; i++) {
            cap[2*n][i] = 1;
            cap[n+i][2*n+1] = 1;
            cost[2*n][i] = 0;
            cost[n+i][2*n+1] = 0;
        }
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (visible[i][j]) {
                    cap[i][j+n] = 1;
                    if (staring[i][j]) {
                        cost[i][j+n] = 0;
                    } else {
                        cost[i][j+n] = 1;
                    }
                }
            }
        }
        long[] flowCost = MinCostFlow.getFlowCost(cap, cost, 2*n, 2*n+1);
        System.out.println(flowCost[1]);
    }

    static int oneLineOddCase(Vector[] positions, Vector[] dirs, Vector lineDir, ArrayList<Integer> sortedPoints) {
        int n = positions.length;
        Vector check = positions[sortedPoints.get(1)].subtract(positions[sortedPoints.get(0)]);
        if (lineDir.dot(check) < 0) {
            lineDir = lineDir.scale(-1);
        }
        boolean[] isFacingForwards = new boolean[n];
        boolean[] isFacingBackwards = new boolean[n];
        for (int i=0; i<n; i++) {
            Vector dir = dirs[sortedPoints.get(i)];
            if (dir.cross(lineDir).isZero()) {
                if (dir.dot(lineDir) > 0) {
                    isFacingForwards[i] = true;
                } else {
                    isFacingBackwards[i] = true;
                }
            } else {
                isFacingForwards[i] = false;
                isFacingBackwards[i] = false;
            }
        }
        // oddPrefixForwards[i] is the number of points in odd indices up to
        // and including index i-1 facing forwards.
        // Others are similar.
        int[] prefixForwards = new int[n+1];
        int[] prefixBackwards = new int[n+1];
        int[] oddPrefixForwards = new int[n+1];
        int[] evenPrefixForwards = new int[n+1];
        int[] oddPrefixBackwards = new int[n+1];
        int[] evenPrefixBackwards = new int[n+1];
        for (int i=0; i<n; i++) {
            if (i%2==0) {
                evenPrefixForwards[i+1] = evenPrefixForwards[i];
                evenPrefixBackwards[i+1] = evenPrefixBackwards[i];
                if (isFacingForwards[i]) {
                    evenPrefixForwards[i+1] = evenPrefixForwards[i] + 1;
                }
                if (isFacingBackwards[i]) {
                    evenPrefixBackwards[i+1] = evenPrefixBackwards[i] + 1;
                }
                oddPrefixForwards[i+1] = oddPrefixForwards[i];
                oddPrefixBackwards[i+1] = oddPrefixBackwards[i];
            } else {
                oddPrefixForwards[i+1] = oddPrefixForwards[i];
                oddPrefixBackwards[i+1] = oddPrefixBackwards[i];
                if (isFacingForwards[i]) {
                    oddPrefixForwards[i+1] = oddPrefixForwards[i] + 1;
                }
                if (isFacingBackwards[i]) {
                    oddPrefixBackwards[i+1] = oddPrefixBackwards[i] + 1;
                }

                evenPrefixForwards[i+1] = evenPrefixForwards[i];
                evenPrefixBackwards[i+1] = evenPrefixBackwards[i];
            }
            prefixForwards[i+1] = prefixForwards[i];
            prefixBackwards[i+1] = prefixBackwards[i];
            if (isFacingForwards[i]) {
                prefixForwards[i+1]++;
            }
            if (isFacingBackwards[i]) {
                prefixBackwards[i+1]++;
            }
        }
        /*
        System.out.println("Facing forwards: "+Arrays.toString(isFacingForwards));
        System.out.println("Facing backwards: "+Arrays.toString(isFacingBackwards));
        System.out.println("prefixForwards: "+Arrays.toString(prefixForwards));
        System.out.println("oddPrefixForwards: "+Arrays.toString(oddPrefixForwards));
        System.out.println("evenPrefixForwards: "+Arrays.toString(evenPrefixForwards));
        System.out.println("prefixBackwards: "+Arrays.toString(prefixBackwards));
        System.out.println("oddPrefixBackwards: "+Arrays.toString(oddPrefixBackwards));
        System.out.println("evenPrefixBackwards: "+Arrays.toString(evenPrefixBackwards));
         */
        int bestCost = 1000 + n;
        for (int moveIndex=0; moveIndex<n; moveIndex++) {
            for (int cycleStartIndex = 0; cycleStartIndex<n; cycleStartIndex++) {
                if (cycleStartIndex == moveIndex) {
                    continue;
                }
                if (moveIndex < cycleStartIndex && cycleStartIndex % 2 == 0) {
                    continue;
                }
                if (moveIndex > cycleStartIndex && cycleStartIndex % 2 == 1) {
                    continue;
                }
                int beforeCycleCost = beforeCycleCost(
                        moveIndex, cycleStartIndex,
                        oddPrefixForwards, oddPrefixBackwards,
                        evenPrefixForwards, evenPrefixBackwards
                );
                for (int cycleEndIndex=cycleStartIndex+1; cycleEndIndex<n; cycleEndIndex++) {
                    if (cycleEndIndex == moveIndex) {
                        continue;
                    }
                    int cycleLen = cycleEndIndex - cycleStartIndex + 1 + 1;
                    if (moveIndex > cycleStartIndex && moveIndex < cycleEndIndex) {
                        cycleLen--;
                    }
                    if (cycleLen % 2 == 0){
                        continue;
                    }
                    int forwardCycleCost = forwardsCycleCost(
                            moveIndex, cycleStartIndex, cycleEndIndex,
                            prefixForwards,
                            isFacingForwards, isFacingBackwards,
                            sortedPoints,
                            positions, dirs
                    );
                    int backwardCycleCost = backwardsCycleCost(
                            moveIndex, cycleStartIndex, cycleEndIndex,
                            prefixBackwards,
                            isFacingForwards, isFacingBackwards,
                            sortedPoints,
                            positions, dirs
                    );

                    int afterCycleCost = afterCycleCost(
                            moveIndex, cycleEndIndex,
                            oddPrefixForwards, oddPrefixBackwards,
                            evenPrefixForwards, evenPrefixBackwards
                    );
                    int forwardTotal = beforeCycleCost + forwardCycleCost + afterCycleCost + 1000;
                    int backwardTotal = beforeCycleCost + backwardCycleCost + afterCycleCost + 1000;
//                    System.out.printf(
//                            "move: %d, cycleStart: %d, cycleEnd: %d, beforeCycle: %d, afterCycle: %d, forwardCycle: %d, backwardCycle: %d\n",
//                            moveIndex, cycleStartIndex, cycleEndIndex, beforeCycleCost, afterCycleCost, forwardCycleCost, backwardCycleCost);
                    if (forwardTotal < bestCost) {
                        bestCost = forwardTotal;
//                        System.out.printf(
//                                "move: %d, cycleStart: %d, cycleEnd: %d, beforeCycle: %d, afterCycle: %d, forwardCycle: %d, backwardCycle: %d\n",
//                                moveIndex, cycleStartIndex, cycleEndIndex, beforeCycleCost, afterCycleCost, forwardCycleCost, backwardCycleCost);
//                        System.out.println("^^^^^^^^New forwards best");
                    }
                    if (backwardTotal < bestCost) {
                        bestCost = backwardTotal;
//                        System.out.printf(
//                                "move: %d, cycleStart: %d, cycleEnd: %d, beforeCycle: %d, afterCycle: %d, forwardCycle: %d, backwardCycle: %d\n",
//                                moveIndex, cycleStartIndex, cycleEndIndex, beforeCycleCost, afterCycleCost, forwardCycleCost, backwardCycleCost);
//                        System.out.println("^^^^^^^^New backwards best");
                    }
                }
            }
        }
        return bestCost;
    }

    static int beforeCycleCost(
            int moveIndex, int cycleStartIndex,
            int[] oddPrefixForwards, int[] oddPrefixBackwards,
            int[] evenPrefixForwards, int[] evenPrefixBackwards
    ) {
        int cost = 0;
        if (moveIndex < cycleStartIndex) {
            int oddIndicesBeforeMove = countOddIndices(-1, moveIndex);
            int evenIndicesBeforeMove = countEvenIndices(-1, moveIndex);
            int oddIndicesAfterMove = countOddIndices(moveIndex, cycleStartIndex);
            int evenIndicesAfterMove = countEvenIndices(moveIndex, cycleStartIndex);
            // Need to reorient those in even indices before moveIndex that are not facing forwards.
            int evenBeforeMoveCost = evenIndicesBeforeMove - evenPrefixForwards[moveIndex];
            cost += evenBeforeMoveCost;
            // Need to reorient those in odd indices before moveIndex that are not facing backwards.
            int oddBeforeMoveCost = oddIndicesBeforeMove - oddPrefixBackwards[moveIndex];
            cost += oddBeforeMoveCost;
            // Need to reorient those in even indices after moveIndex that are not facing backwards.
            int evenAfterMoveCost = evenIndicesAfterMove - (evenPrefixBackwards[cycleStartIndex] - evenPrefixBackwards[moveIndex + 1]);
            cost += evenAfterMoveCost;
            // Need to reorient those in odd indices after moveIndex that are not facing forwards.
            int oddAfterMoveCost = oddIndicesAfterMove - (oddPrefixForwards[cycleStartIndex] - oddPrefixForwards[moveIndex + 1]);
            cost += oddAfterMoveCost;
//            System.out.printf("vvv evenBefore: %d, oddBefore: %d, oddAfter: %d, evenAfter: %d\n", evenBeforeMoveCost, oddBeforeMoveCost, oddAfterMoveCost, evenAfterMoveCost);
        } else {
            int oddIndicesBeforeCycle = countOddIndices(-1, cycleStartIndex);
            int evenIndicesBeforeCycle = countEvenIndices(-1, cycleStartIndex);
            // Need to reorient those in even indices that are not facing forwards.
            cost += evenIndicesBeforeCycle - evenPrefixForwards[cycleStartIndex];
            // Need to reorient those in odd indices that not facing backwards.
            cost += oddIndicesBeforeCycle - oddPrefixBackwards[cycleStartIndex];
        }
        return cost;
    }
    static int afterCycleCost(
            int moveIndex, int cycleEndIndex,
            int[] oddPrefixForwards, int[] oddPrefixBackwards,
            int[] evenPrefixForwards, int[] evenPrefixBackwards
    ) {
        int n = oddPrefixBackwards.length - 1;
        int cost = 0;
        if (moveIndex > cycleEndIndex) {
            int oddIndicesBeforeMove = countOddIndices(cycleEndIndex, moveIndex);
            int evenIndicesBeforeMove = countEvenIndices(cycleEndIndex, moveIndex);
            int oddIndicesAfterMove = countOddIndices(moveIndex, n);
            int evenIndicesAfterMove = countEvenIndices(moveIndex, n);
            // Need to reorient those in odd indices before moveIndex that are not facing backwards.
            cost += oddIndicesBeforeMove - (oddPrefixBackwards[moveIndex] - oddPrefixBackwards[cycleEndIndex + 1]);
            // Need to reorient those in even indices before moveIndex that are not facing forwards.
            cost += evenIndicesBeforeMove - (evenPrefixForwards[moveIndex] - evenPrefixForwards[cycleEndIndex + 1]);
            // Need to reorient those in even indices after moveIndex that are not facing backwards.
            cost += evenIndicesAfterMove - (evenPrefixBackwards[n] - evenPrefixBackwards[moveIndex + 1]);
            // Need to reorient those in odd indices after moveIndex that are not facing forwards.
            cost += oddIndicesAfterMove - (oddPrefixForwards[n] - oddPrefixForwards[moveIndex + 1]);
        } else {
            int oddIndicesAfterCycle = countOddIndices(cycleEndIndex, n);
            int evenIndicesAfterCycle = countEvenIndices(cycleEndIndex, n);
            // Need to reorient those in even indices that are not facing backwards.
            cost += evenIndicesAfterCycle - (evenPrefixBackwards[n] - evenPrefixBackwards[cycleEndIndex + 1]);
            // Need to reorient those in odd indices that are not facing forwards.
            cost += oddIndicesAfterCycle - (oddPrefixForwards[n] - oddPrefixForwards[cycleEndIndex + 1]);
        }
        return cost;
    }

    static int forwardsCycleCost(
            int moveIndex, int cycleStartIndex, int cycleEndIndex,
            int[] prefixForwards,
            boolean[] isFacingForwards, boolean[] isFacingBackwards,
            ArrayList<Integer> sortedPoints,
            Vector[] positions, Vector[] dirs
    ) {
        int forwardsCost = 0;
        if (cycleStartIndex < moveIndex && moveIndex < cycleEndIndex) {
            int indicesBeforeMove = countIndices(cycleStartIndex - 1, moveIndex);
            int indicesAfterMove = countIndices(moveIndex, cycleEndIndex);
            forwardsCost += indicesBeforeMove - (prefixForwards[moveIndex] - prefixForwards[cycleStartIndex]);
            forwardsCost += indicesAfterMove - (prefixForwards[cycleEndIndex] - prefixForwards[moveIndex + 1]);
        } else {
            int indices = countIndices(cycleStartIndex - 1, cycleEndIndex);
            forwardsCost += indices - (prefixForwards[cycleEndIndex] - prefixForwards[cycleStartIndex]);
        }
        int cycleStartPointIndex = sortedPoints.get(cycleStartIndex);
        int movePointIndex = sortedPoints.get(moveIndex);
        int cycleEndPointIndex = sortedPoints.get(cycleEndIndex);
        if (intersects(positions[cycleStartPointIndex], dirs[movePointIndex].scale(-1), positions[cycleEndPointIndex], dirs[cycleEndPointIndex])) {
            // There is a position we can move the point to that requires rotating
            // neither the end point, nor the moved point.
            forwardsCost += 0;
        } else {
            if ((isFacingBackwards[cycleEndIndex] || isFacingForwards[cycleEndIndex]) &&
                    (isFacingForwards[moveIndex] || isFacingBackwards[moveIndex])) {
                // Both the cycle end point and the moved point will need to be rotated.
                forwardsCost += 2;
            } else {
                // Rotating one of the moved point or the cycle end point will suffice.
                forwardsCost += 1;
            }
        }
        return forwardsCost;
    }

    static int backwardsCycleCost(
            int moveIndex, int cycleStartIndex, int cycleEndIndex,
            int[] prefixBackwards,
            boolean[] isFacingForwards, boolean[] isFacingBackwards,
            ArrayList<Integer> sortedPoints,
            Vector[] positions, Vector[] dirs
    ) {
        int backwardsCost = 0;
        if (cycleStartIndex < moveIndex && moveIndex < cycleEndIndex) {
            int indicesBeforeMove = countIndices(cycleStartIndex, moveIndex);
            int indicesAfterMove = countIndices(moveIndex, cycleEndIndex + 1);
            int afterMoveCost = indicesAfterMove - (prefixBackwards[cycleEndIndex + 1] - prefixBackwards[moveIndex + 1]);
            backwardsCost += afterMoveCost;
            int beforeMoveCost = indicesBeforeMove - (prefixBackwards[moveIndex] - prefixBackwards[cycleStartIndex + 1]);
            backwardsCost += beforeMoveCost;
//            System.out.printf("vvv beforeMoveCost: %d, afterMoveCost: %d\n", beforeMoveCost, afterMoveCost);
        } else {
            int indices = countIndices(cycleStartIndex, cycleEndIndex + 1);
            backwardsCost += indices - (prefixBackwards[cycleEndIndex + 1] - prefixBackwards[cycleStartIndex + 1]);
        }
        int cycleStartPointIndex = sortedPoints.get(cycleStartIndex);
        int movePointIndex = sortedPoints.get(moveIndex);
        int cycleEndPointIndex = sortedPoints.get(cycleEndIndex);
//        System.out.printf("vvv backwardsCycleCost before ray-ray check is: %d\n", backwardsCost);
        if (intersects(positions[cycleEndPointIndex], dirs[movePointIndex].scale(-1), positions[cycleStartPointIndex], dirs[cycleStartPointIndex])) {
            // There is a position we can move the point to that requires rotating
            // neither the end point, nor the moved point.
            backwardsCost += 0;
        } else {
            if ((isFacingBackwards[cycleStartIndex] || isFacingForwards[cycleStartIndex]) &&
                    (isFacingForwards[moveIndex] || isFacingBackwards[moveIndex])) {
                // Both the cycle end point and the moved point will need to be rotated.
                backwardsCost += 2;
            } else {
                // Rotating one of the moved point or the cycle end point will suffice.
                backwardsCost += 1;
            }
        }
        return backwardsCost;
    }

    static int countOddIndices(int lo, int hi) {
        return countIndices(lo, hi, 1);
    }
    static int countEvenIndices(int lo, int hi) {
        return countIndices(lo, hi, 0);
    }
    static int countIndices(int lo, int hi) {
        return countOddIndices(lo, hi) + countEvenIndices(lo, hi);
    }
    // Count the number of odd/even indices strictly between lo and hi.
    static int countIndices(int lo, int hi, int parity) {
        int indices = (hi - lo - 1) / 2;
        int loParity = lo < 0 ? ((-lo) % 2) : lo % 2;
        int hiParity = hi < 0 ? ((-hi) % 2) : hi % 2;
        if (parity==0 && loParity==1 && hiParity==1) {
            indices++;
        } else if (parity==1 && loParity==0 && hiParity==0) {
            indices++;
        }
        return indices;
    }

    static boolean intersects(Vector p1, Vector d1, Vector p2, Vector d2) {
        if (d1.lineNormalised().equals(d2.lineNormalised())) {
            // d1 and d2 are parallel. We don't care about this case.
            return false;
        }
        if (d1.cross(d2).dot(p1.subtract(p2)) != 0) {
            // The lines do not intersect.
            return false;
        }
        // p + rv = q + tu
        long[] p = new long[]{p1.x, p1.y, p1.z};
        long[] v = new long[]{d1.x, d1.y, d1.z};
        long[] q = new long[]{p2.x, p2.y, p2.z};
        long[] u = new long[]{d2.x, d2.y, d2.z};
        int x = 0;
        int y = 1;
        while (v[x]==0) {
            x++;
        }
        if (x==y) {
            y = 0;
        }
        long tNum = v[x]*q[y] - v[x]*p[y] - q[x]*v[y] + p[x]*v[y];
        long tDenom = u[x]*v[y] - v[x]*u[y];
        long rNum = tNum*u[x] + tDenom*q[x] - tDenom*p[x];
        long rDenom = tDenom * v[x];
        if (tDenom < 0) {
            tNum *= -1;
            tDenom *= -1;
        }
        if (rDenom < 0) {
            rNum *= -1;
            rDenom *= -1;
        }
        return tNum > 0 && rNum > 0;
    }
}
class Line3D {
    Vector offset;
    Vector dir;
    public Line3D(Vector offset, Vector dir) {
        this.offset = offset;
        this.dir = dir;
    }
    public int hashCode() {
        return Objects.hash(offset.x, offset.y, offset.z, dir.x, dir.y, dir.z);
    }
    public boolean equals(Object obj) {
        Line3D l2 = (Line3D) obj;
        return offset.equals(l2.offset) && dir.equals(l2.dir);
    }
    public String toString() {
        return String.format("%s + t%s", offset, dir);
    }
}
class Wrapper implements Comparable<Wrapper> {
    int id;
    Vector v;
    public Wrapper(int idd, Vector vv) {
        id = idd;
        v = vv;
    }
    public int compareTo(Wrapper w2) {
        int vectorComparison = v.compareTo(w2.v);
        if (vectorComparison == 0) {
            return id - w2.id;
        }
        return vectorComparison;
    }
}
class Vector implements Comparable<Vector> {
    long x,y,z;
    public Vector(long xx, long yy, long zz) {
        x = xx;
        y = yy;
        z = zz;
    }
    public Vector add(Vector v2) {
        return new Vector(x + v2.x, y + v2.y, z + v2.z);
    }
    public Vector scale(long c) {
        return new Vector(c*x, c*y, c*z);
    }
    public Vector subtract(Vector v2) {
        return new Vector(x - v2.x, y - v2.y, z - v2.z);
    }
    public long dot(Vector v2) {
        return x * v2.x + y * v2.y + z * v2.z;
    }
    public Vector cross(Vector v2) {
        return new Vector(
                y * v2.z - z * v2.y,
                -(x * v2.z - z * v2.x),
                x * v2.y - y * v2.x
        );
    }
    public boolean isZero() {
        return x==0 && y==0 && z==0;
    }
    public Vector lineNormalised() {
        long absX = x < 0 ? -x : x;
        long absY = y < 0 ? -y : y;
        long absZ = z < 0 ? -z : z;
        long gcf = gcd(absX, gcd(absY, absZ));
        if (x < 0 || (x == 0 && y < 0) || (x == 0 && y == 0 && z < 0)) {
            return new Vector(-x/gcf, -y/gcf, -z/gcf);
        }
        return new Vector(x/gcf, y/gcf, z/gcf);
    }
    public Vector normalShift(Vector v2) {
        long scalar = 0;
        if (v2.x != 0) {
            long target = x % (long)Math.abs(v2.x);
            if (target < 0) {
                target += v2.x;
            }
            long diff = x - target;
            scalar = diff / v2.x;
        } else if (v2.y != 0) {
            long target = y % (long)Math.abs(v2.y);
            if (target < 0) {
                target += v2.y;
            }
            long diff = y - target;
            scalar = diff / v2.y;
        } else {
            long target = z % (long)Math.abs(v2.z);
            if (target < 0) {
                target += v2.z;
            }
            long diff = z - target;
            scalar = diff / v2.z;
        }
        return subtract(v2.scale(scalar));
    }
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a%b);
    }
    public int hashCode() {
        return Objects.hash(x,y,z);
    }
    public boolean equals(Object obj) {
        Vector v2 = (Vector) obj;
        return x == v2.x && y == v2.y && z == v2.z;
    }
    public int compareTo(Vector v2) {
        int xComp = Long.compare(x, v2.x);
        if (xComp != 0) {
            return xComp;
        }
        int yComp = Long.compare(y, v2.y);
        if (yComp != 0) {
            return yComp;
        }
        return Long.compare(z, v2.z);
    }
    public String toString() {
        return String.format("[%d,%d,%d]",x,y,z);
    }
}
class MinCostFlow {
    static final long INF = Long.MAX_VALUE / 2 - 1;
    static boolean found[];
    static int N, dad[];
    static long flow[][], dist[], pi[];
    static long[] getFlowCost(long cap[][], long cost[][], int s, int t) {
        N = cap.length;
        found = new boolean[N];
        dad = new int[N];
        flow = new long[N][N];
        dist = new long[N + 1];
        pi = new long[N];
        long totflow = 0;
        long totcost = 0;
        while (search(cap, cost, s, t)) {
            long amt = INF;
            for (int x = t; x != s; x = dad[x]) {
                amt = Math.min(
                        amt,
                        flow[x][dad[x]] != 0 ? flow[x][dad[x]] : cap[dad[x]][x] - flow[dad[x]][x]
                );
            }
            for (int x = t; x != s; x = dad[x]) {
                if (flow[x][dad[x]] != 0) {
                    flow[x][dad[x]] -= amt;
                    totcost -= amt * cost[x][dad[x]];
                } else {
                    flow[dad[x]][x] += amt;
                    totcost += amt * cost[dad[x]][x];
                }
            }
            totflow += amt;
        }
        return new long[] { totflow, totcost };
    }
    static boolean search(long cap[][], long cost[][], int s, int t) {
        Arrays.fill(found, false);
        Arrays.fill(dist, INF);
        dist[s] = 0;
        while (s != N) {
            int best = N;
            found[s] = true;
            for (int k = 0; k < N; k++) {
                if (found[k]) {
                    continue;
                }
                if (flow[k][s] != 0) {
                    long val = dist[s] + pi[s] - pi[k] - cost[k][s];
                    if (dist[k] > val) {
                        dist[k] = val;
                        dad[k] = s;
                    }
                }
                if (flow[s][k] < cap[s][k]) {
                    long val = dist[s] + pi[s] - pi[k] + cost[s][k];
                    if (dist[k] > val) {
                        dist[k] = val;
                        dad[k] = s;
                    }
                }
                if (dist[k] < dist[best]) {
                    best = k;
                }
            }
            s = best;
        }
        for (int k = 0; k < N; k++) {
            pi[k] = Math.min(pi[k] + dist[k], INF);
        }
        return found[t];
    }
}