<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

303. Great Berland Wall
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Berland is in civil war. This time peaceful solution is hardly possible. Collapse to the East and West Berland is inevitable! Commander-in-chief of grey, general Kruglyakovski, has made a decision to hasten the process and to surround his headquarters with a wall (which later be called Great Berland Wall). The wall should be built in such a way that the enemy's headquarters would stay at the other side of the wall.

Looking to the Berland map general Kruglyakovski noticed that the country consists of a number of provinces. Each province has the form of a simple (but possibly not convex) polygon. The country of Berland has no enclaves and does not contain any enclaves of other countries inside, i.e. it is possible to get from one point of Berland to another without leaving the country. The "passability" is known for each segment of the border of each province. "Passability" is the maximum speed the soldier can move with along the corresponding segment.

General Kruglyakovski decided that the wall will pass only along the borders of the provinces and will have the form of a simple polygon. He sent the group of soldiers to build the wall during the night. And you got a task to find such a form and position of the wall that the time of building would be minimal. The time of building of the section of the wall is equal to the "passability" of the corresponding border segment. The time of building of the wall is equal to the sum of building of its segments.

Input
The first line of the input file contains the number of segments of province borders — integer number N (5≤ N≤ 300). The segments themselves follow further. Each segment is defined by five numbers x1, y1, x2, y2, v, where (x1, y1) and (x2, y2) are the coordinates of the segment end points and the integer number v (1 ≤ v ≤ 1000) is the "passability". Any pair of segments has not more than one common point and this point can only be their common end-point. Input data finishes with one more quadruple of numbers X1, Y1, X2, Y2, where (X1, Y1), (X2, Y2) are the coordinates of headquarters of the general Kruglyakovski and his opponent correspondingly. Both headquarters are situated strictly inside one of the provinces. The headquarters are situated in different provinces. All coordinates in the input are integer numbers less than 104 by the absolute value.

Output
Write to the first line of the output the total time of building of the wall. Write to the second line the number of border segments the wall will occupy. To the next line write the sequence of the numbers of the segments. The segments are numbered in the order they appear in the input. If there are several solutions choose any of them.

Example(s)
sample input
sample output
13
0 6 3 6 9 0 0 4 2 8
4 4 6 6 7 2 4 3 6 1
3 6 6 6 1 6 4 6 6 1
4 2 6 4 1 0 0 0 6 6
2 2 2 4 1 2 2 4 2 1
0 6 2 4 5 2 4 4 4 4
4 2 4 4 3
3 3
2 5
6
6
9 10 4 7 5 6

<|response|>
## 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.
