// Local C++17 stress harness. Input generation is independent of the solver seed.
#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using Points = std::vector<std::array<int, 2>>;
using Route = std::vector<int>;
int distance(const Points& p, int a, int b) {
    return std::abs(p[a][0] - p[b][0]) + std::abs(p[a][1] - p[b][1]);
}
int fullCost(const Points& p, const Route& route) {
    int sum = 0;
    for (int i = 1; i < (int)route.size(); ++i)
        sum += distance(p, route[i-1], route[i]);
    return sum;
}
int delta(const Points& p, const Route& route, int left, int right) {
    int a = route[left-1], b = route[left], c = route[right];
    int change = distance(p,a,c) - distance(p,a,b);
    if (right+1 < (int)route.size()) {
        int d = route[right+1];
        change += distance(p,b,d) - distance(p,c,d);
    }
    return change;
}
bool valid(const Route& route) {
    if (route.empty() || route[0] != 0) return false;
    Route sorted = route;
    std::sort(sorted.begin(), sorted.end());
    for (int i = 0; i < (int)sorted.size(); ++i) if (sorted[i] != i) return false;
    return true;
}
[[noreturn]] void fail(const Points& p, const Route& route,
                     int left, int right, int expected, int actual) {
    std::cerr << "FAIL seed=20261004 left=" << left << " right=" << right
              << " expected=" << expected << " actual=" << actual << '\n';
    std::cerr << p.size() << '\n';
    for (const auto& point : p) std::cerr << point[0] << ' ' << point[1] << '\n';
    std::cerr << "route:";
    for (int x : route) std::cerr << ' ' << x;
    std::cerr << '\n';
    std::exit(1);
}
void check(const Points& p, const Route& route) {
    if (!valid(route)) fail(p,route,0,0,1,0);
    const int before = fullCost(p,route);
    for (int left = 1; left < (int)route.size(); ++left) {
        for (int right = left+1; right < (int)route.size(); ++right) {
            Route candidate = route;
            int predicted = delta(p,route,left,right);
            std::reverse(candidate.begin()+left, candidate.begin()+right+1);
            int actual = fullCost(p,candidate)-before;
            if (predicted != actual) fail(p,route,left,right,actual,predicted);
            if (!valid(candidate)) fail(p,route,left,right,1,0);
            std::reverse(candidate.begin()+left, candidate.begin()+right+1);
            if (candidate != route || fullCost(p,candidate) != before)
                fail(p,route,left,right,before,fullCost(p,candidate));
        }
    }
}
int main() {
    Points tail = {{{0,0}},{{1,0}},{{9,0}},{{8,0}},{{2,0}}};
    Route route = {0,1,2,3,4};
    check(tail,route);
    int correct = delta(tail,route,2,4);
    int wrongCycle = correct + distance(tail,2,0) - distance(tail,4,0);
    if (correct != -7 || wrongCycle != 0) fail(tail,route,2,4,-7,correct);
    std::mt19937 generator(20261004u);
    for (int trial = 0; trial < 1000; ++trial) {
        int n = 1 + generator()%12;
        Points points(n);
        // A small coordinate range deliberately includes duplicate points.
        for (auto& p : points) { p[0]=generator()%8; p[1]=generator()%8; }
        Route order(n);
        std::iota(order.begin(),order.end(),0);
        // Fixed consumption; never move warehouse 0.
        for (int i = n-1; i > 1; --i) std::swap(order[i],order[1+generator()%i]);
        check(points,order);
    }
    std::cout << "PASS: fixed tail counterexample and 1000 seeded cases\n";
}