## 1. Abridged Problem Statement

We are given `N ≤ 300` border segments of a planar subdivision of Berland into polygonal provinces. Each segment has a positive building cost `v`. Two headquarters points lie strictly inside two different provinces.

We must build a wall only along given border segments. The wall must be a simple polygon and must separate the two headquarters, i.e. exactly one headquarters must lie inside the polygon. Find a minimum-total-cost set/sequence of segments forming such a wall, and output its cost and segment indices.

---

## 2. Detailed Editorial

### Graph interpretation

The province borders form a planar graph:

- segment endpoints are graph vertices,
- border segments are graph edges,
- edge weights are the given costs.

Because segments do not properly intersect — they can only meet at common endpoints — any simple cycle in this graph corresponds to a simple polygonal wall.

So the task becomes:

> Find a minimum-cost simple cycle in the planar graph such that the two given points lie on different sides of that cycle.

---

### Separating two points using ray parity

For a simple polygon, a point is inside it iff a ray from the point crosses the polygon boundary an odd number of times.

Take an upward vertical ray from each headquarters.

For every graph edge/segment `e`, define:

```text
c1(e) = 1 if e crosses the upward ray from headquarters 1, else 0
c2(e) = 1 if e crosses the upward ray from headquarters 2, else 0
```

For a cycle `C`:

```text
point 1 is inside C iff XOR of c1(e) over e in C is 1
point 2 is inside C iff XOR of c2(e) over e in C is 1
```

The wall separates the two headquarters iff exactly one of these parities is odd:

```text
(XOR c1(e)) != (XOR c2(e))
```

Equivalently:

```text
XOR over e in C of (c1(e) XOR c2(e)) = 1
```

So assign each graph edge a binary label:

```text
parity(e) = c1(e) XOR c2(e)
```

Now the problem is:

> Find a minimum-cost cycle whose XOR of edge parity labels is `1`.

---

### Minimum odd-parity cycle via doubled-state Dijkstra

We create a doubled graph of states:

```text
(vertex, accumulated_parity)
```

There are `2 * V` states.

For every original edge `u -- v` with cost `w` and parity `p`, add transitions:

```text
(u, q) -> (v, q XOR p)
(v, q) -> (u, q XOR p)
```

for both `q = 0, 1`.

Now, a path in this doubled graph from:

```text
(s, 0) to (s, 1)
```

corresponds to a closed walk in the original graph starting and ending at `s`, with odd total edge parity.

So for each possible starting vertex `s`, we run Dijkstra from `(s, 0)` and look at the distance to `(s, 1)`.

The minimum over all `s` is the desired answer.

---

### Why this gives a simple cycle

Dijkstra gives a minimum-cost odd-parity closed walk. A closed walk may repeat vertices/edges, but since all edge costs are positive, any useless even-parity subcycle can be removed. The remaining minimum odd-parity closed walk contains at least one odd-parity simple cycle, with cost no larger.

Therefore, minimizing over closed walks is enough to find the optimal simple polygonal wall.

---

### Complexity

Let:

- `V` be the number of distinct endpoints, `V ≤ 2N`,
- `E = N`.

For each vertex, we run Dijkstra on `2V` states and `2E` transitions.

Complexity:

```text
O(V * E log V)
```

Since `N ≤ 300`, this easily fits.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

        coord_t d_theta = theta2 - theta1;
        coord_t cx = center.x, cy = center.y;
        coord_t area = r * cx * (sin(theta2) - sin(theta1)) -
                       r * cy * (cos(theta2) - cos(theta1)) + r * r * d_theta;
        return area / 2.0;
    }

    friend vector<Point> intersect_circles(
        const Point& c1, coord_t r1, const Point& c2, coord_t r2
    ) {
        Point d = c2 - c1;
        coord_t dist = d.norm();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

        Point mid = c1 + d.unit() * a;
        Point perp_dir = d.perp().unit();

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }

    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

int n;
vector<Point> seg_a, seg_b;
vector<int> seg_v;
Point hq1, hq2;

void read() {
    cin >> n;
    seg_a.resize(n);
    seg_b.resize(n);
    seg_v.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> seg_a[i] >> seg_b[i] >> seg_v[i];
    }
    cin >> hq1 >> hq2;
}

void solve() {
    // The province borders form a planar subdivision: segments only ever touch
    // at shared endpoints, so the vertices of our graph are exactly the segment
    // endpoints and every segment is a single edge between two of them. Any
    // closed walk that visits distinct vertices is automatically a simple
    // polygon, so "build a simple polygon out of segments" just means "pick a
    // simple cycle of edges".
    //
    // A point is inside a simple polygon iff a ray from it crosses the boundary
    // an odd number of times. Cast an upward vertical ray from each
    // headquarters; for an edge let c1/c2 be whether it crosses the ray of hq1
    // / hq2. Over a whole cycle the inside/outside parity of hqk is the XOR of
    // its ck over the used edges. We need the wall to separate the two
    // headquarters, i.e. exactly one of them inside, i.e. parity(hq1) !=
    // parity(hq2). Since parity(hq1) ^ parity(hq2) = XOR of (c1 ^ c2) over the
    // cycle, we collapse the two parities into a single edge label par = c1 ^
    // c2 and look for a minimum cost cycle with odd total label.
    //
    // A minimum cost odd-label closed walk is always a single simple cycle:
    // with strictly positive weights any extra even sub-loop could be dropped.
    // We find it with a parity-doubled Dijkstra. Node (v, p) means "at vertex v
    // having accumulated label parity p"; an edge with label par links (v, p)
    // to (w, p ^ par). For each source s the shortest (s, 0) -> (s, 1) path is
    // an odd cycle through s, and the minimum over all sources is the answer.
    // We then rerun Dijkstra from the winning source to recover the segments.

    map<pair<int64_t, int64_t>, int> idx;
    auto get_idx = [&](const Point& p) -> int {
        pair<int64_t, int64_t> key = {llround(p.x), llround(p.y)};
        auto it = idx.find(key);
        if(it != idx.end()) {
            return it->second;
        }

        int id = idx.size();
        idx[key] = id;
        return id;
    };

    auto crosses_up_ray = [&](const Point& a, const Point& b,
                              const Point& h) -> bool {
        bool sa = a.x > h.x, sb = b.x > h.x;
        if(sa == sb) {
            return false;
        }

        coord_t t = (h.x - a.x) / (b.x - a.x);
        coord_t y_at_cross = a.y + t * (b.y - a.y);
        return y_at_cross > h.y;
    };

    int m = 0;
    vector<int> eu(n), ev(n), epar(n);
    for(int i = 0; i < n; i++) {
        eu[i] = get_idx(seg_a[i]);
        ev[i] = get_idx(seg_b[i]);
        int c1 = crosses_up_ray(seg_a[i], seg_b[i], hq1);
        int c2 = crosses_up_ray(seg_a[i], seg_b[i], hq2);
        epar[i] = c1 ^ c2;
        m = max({m, eu[i] + 1, ev[i] + 1});
    }

    vector<vector<tuple<int, int, int>>> adj(m);
    for(int i = 0; i < n; i++) {
        adj[eu[i]].push_back({ev[i], seg_v[i], i});
        adj[ev[i]].push_back({eu[i], seg_v[i], i});
    }

    const int64_t inf = numeric_limits<int64_t>::max();
    auto dijkstra = [&](int src, vector<int64_t>& dist,
                        vector<pair<int, int>>& par) {
        dist.assign(2 * m, inf);
        par.assign(2 * m, {-1, -1});
        priority_queue<
            pair<int64_t, int>, vector<pair<int64_t, int>>,
            greater<pair<int64_t, int>>>
            pq;
        dist[src] = 0;
        pq.push({0, src});
        while(!pq.empty()) {
            auto [d, node] = pq.top();
            pq.pop();
            if(d > dist[node]) {
                continue;
            }

            int v = node / 2, p = node & 1;
            for(auto [w, cost, seg]: adj[v]) {
                int to = 2 * w + (p ^ epar[seg]);
                if(d + cost < dist[to]) {
                    dist[to] = d + cost;
                    par[to] = {node, seg};
                    pq.push({dist[to], to});
                }
            }
        }
    };

    int64_t best = inf;
    int best_src = -1;
    vector<int64_t> dist;
    vector<pair<int, int>> par;
    for(int s = 0; s < m; s++) {
        dijkstra(2 * s, dist, par);
        if(dist[2 * s + 1] < best) {
            best = dist[2 * s + 1];
            best_src = s;
        }
    }

    dijkstra(2 * best_src, dist, par);
    vector<int> used;
    int node = 2 * best_src + 1;
    while(par[node].first != -1) {
        used.push_back(par[node].second + 1);
        node = par[node].first;
    }

    cout << best << "\n";
    cout << used.size() << "\n";
    cout << used << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys
import heapq
from math import inf


def main():
    # Read all input tokens at once.
    data = sys.stdin.read().strip().split()

    # If input is empty, do nothing.
    if not data:
        return

    # Pointer into token array.
    ptr = 0

    # Number of border segments.
    n = int(data[ptr])
    ptr += 1

    # Store segment endpoints and costs.
    seg_a = []
    seg_b = []
    seg_cost = []

    for _ in range(n):
        x1 = int(data[ptr])
        y1 = int(data[ptr + 1])
        x2 = int(data[ptr + 2])
        y2 = int(data[ptr + 3])
        v = int(data[ptr + 4])
        ptr += 5

        seg_a.append((x1, y1))
        seg_b.append((x2, y2))
        seg_cost.append(v)

    # Headquarters coordinates.
    hq1 = (int(data[ptr]), int(data[ptr + 1]))
    hq2 = (int(data[ptr + 2]), int(data[ptr + 3]))

    # Map endpoint coordinate pairs to compact vertex ids.
    vertex_id = {}

    def get_id(p):
        """
        Return graph vertex id for point p.
        Create a new id if this endpoint was not seen before.
        """
        if p not in vertex_id:
            vertex_id[p] = len(vertex_id)
        return vertex_id[p]

    def crosses_up_ray(a, b, h):
        """
        Return True if segment ab crosses the upward vertical ray
        starting at point h.

        The ray is:
            x = h.x, y > h.y

        A half-open convention is used to avoid double-counting crossings
        exactly at graph vertices.
        """
        ax, ay = a
        bx, by = b
        hx, hy = h

        # Check which side of vertical line x = hx each endpoint lies on.
        sa = ax > hx
        sb = bx > hx

        # If both are on same side, segment does not cross the vertical line
        # in the required half-open sense.
        if sa == sb:
            return False

        # Compute the segment parameter t at which x = hx.
        # Because sa != sb, bx - ax is nonzero.
        t = (hx - ax) / (bx - ax)

        # y-coordinate of the intersection with x = hx.
        y_cross = ay + t * (by - ay)

        # It crosses the upward ray only if the intersection is above h.
        return y_cross > hy

    # Endpoint ids and parity label for each edge.
    eu = [0] * n
    ev = [0] * n
    epar = [0] * n

    for i in range(n):
        # Convert endpoints into graph vertices.
        eu[i] = get_id(seg_a[i])
        ev[i] = get_id(seg_b[i])

        # Crossing parity for both headquarters.
        c1 = crosses_up_ray(seg_a[i], seg_b[i], hq1)
        c2 = crosses_up_ray(seg_a[i], seg_b[i], hq2)

        # Edge label is 1 iff this edge changes the relative inside/outside
        # parity of the two headquarters.
        epar[i] = int(c1) ^ int(c2)

    # Number of graph vertices.
    m = len(vertex_id)

    # Build undirected adjacency list.
    # adj[v] contains tuples:
    #   (neighbor_vertex, edge_cost, segment_index)
    adj = [[] for _ in range(m)]

    for i in range(n):
        u = eu[i]
        v = ev[i]
        w = seg_cost[i]

        adj[u].append((v, w, i))
        adj[v].append((u, w, i))

    def dijkstra(src_state):
        """
        Dijkstra on doubled graph.

        State encoding:
            state = 2 * vertex + parity

        parity is accumulated XOR of edge labels along the walk.
        """
        total_states = 2 * m

        # Distance array.
        dist = [inf] * total_states

        # Parent array for reconstructing path.
        # parent[state] = (previous_state, segment_index_used)
        parent = [(-1, -1)] * total_states

        # Priority queue of (distance, state).
        pq = []

        # Initialize source.
        dist[src_state] = 0
        heapq.heappush(pq, (0, src_state))

        while pq:
            d, state = heapq.heappop(pq)

            # Ignore stale priority queue entries.
            if d != dist[state]:
                continue

            # Decode current vertex and parity.
            v = state // 2
            parity = state & 1

            # Traverse each original edge.
            for to_vertex, cost, seg_idx in adj[v]:
                # New parity after using this segment.
                new_parity = parity ^ epar[seg_idx]

                # Encode next state.
                next_state = 2 * to_vertex + new_parity

                # Relax edge.
                nd = d + cost
                if nd < dist[next_state]:
                    dist[next_state] = nd
                    parent[next_state] = (state, seg_idx)
                    heapq.heappush(pq, (nd, next_state))

        return dist, parent

    best_cost = inf
    best_src = -1

    # Try every vertex as the beginning/end of the closed walk.
    for s in range(m):
        # Start from vertex s with accumulated parity 0.
        dist, _ = dijkstra(2 * s)

        # We want to return to vertex s with accumulated parity 1.
        target = 2 * s + 1

        if dist[target] < best_cost:
            best_cost = dist[target]
            best_src = s

    # Re-run Dijkstra from best source to reconstruct one optimal cycle.
    dist, parent = dijkstra(2 * best_src)

    # Target state: same vertex, odd parity.
    state = 2 * best_src + 1

    used_segments = []

    # Follow parents backward until source.
    while parent[state][0] != -1:
        prev_state, seg_idx = parent[state]

        # Output uses 1-based segment indices.
        used_segments.append(seg_idx + 1)

        state = prev_state

    # Print answer.
    print(int(best_cost))
    print(len(used_segments))
    print(*used_segments)


if __name__ == "__main__":
    main()
```

---

## 5. Compressed Editorial

Turn the border map into an undirected weighted planar graph: endpoints are vertices and given segments are edges.

For each edge, compute whether it crosses the upward ray from headquarters `1`, and whether it crosses the upward ray from headquarters `2`. Let:

```text
label(edge) = crosses_ray_1 XOR crosses_ray_2
```

For any cycle, the XOR of its edge labels is `1` exactly when the cycle separates the two headquarters.

Thus we need the minimum-cost cycle with odd XOR label.

Use a parity-expanded graph. State `(v, p)` means we are at vertex `v` with accumulated parity `p`. Traversing an edge with label `q` moves to parity `p XOR q`.

For every vertex `s`, run Dijkstra from `(s, 0)` and check distance to `(s, 1)`. This is the minimum odd-parity closed walk through `s`. Taking the best over all `s` gives the answer. Since all edge weights are positive, a minimum odd closed walk contains an optimal simple odd cycle.

Reconstruct the path using parent pointers and output the corresponding segment indices.
