<|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` weighted border segments of a planar subdivision into polygonal provinces. Two headquarters points lie strictly inside two different provinces.

We must choose border segments forming a simple polygonal wall such that the two headquarters are on different sides of the wall. The cost of the wall is the sum of chosen segment costs. Output any minimum-cost wall.

---

## 2. Key observations

### Observation 1: Borders form a planar graph

Treat every segment endpoint as a graph vertex and every border segment as an undirected weighted graph edge.

Because segments do not properly intersect, any simple cycle in this graph corresponds to a non-self-intersecting polygonal wall.

So the problem becomes:

> Find a minimum-cost simple cycle that separates the two headquarters.

---

### Observation 2: Separation can be tested by ray-crossing parity

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

For every edge `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
headquarters 1 is inside C iff XOR of c1(e) over e in C is 1
headquarters 2 is inside C iff XOR of c2(e) over e in C is 1
```

The cycle separates the two points iff exactly one of these XORs is `1`.

Therefore define one binary label per edge:

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

Then we need:

> A minimum-cost cycle whose XOR of `label(e)` over all its edges is `1`.

---

### Observation 3: Minimum odd-XOR cycle via doubled-state shortest paths

Create a graph with two states for every original vertex:

```text
(v, 0) = currently at vertex v, accumulated XOR is 0
(v, 1) = currently at vertex v, accumulated XOR is 1
```

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

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

for `q = 0, 1`.

Now a path:

```text
(s, 0) -> (s, 1)
```

is a closed walk in the original graph starting and ending at `s`, with odd total XOR.

We run Dijkstra from `(s, 0)` for every graph vertex `s` and take the cheapest distance to `(s, 1)`.

---

### Observation 4: Closed walk is enough

Dijkstra finds a minimum odd-XOR closed walk. It might look like it could repeat vertices, but all edge weights are positive.

If a minimum odd closed walk had a repeated vertex, it could be split into smaller closed walks. At least one of them would still have odd XOR and smaller or equal cost. Therefore the optimal closed walk can be taken as a simple cycle.

---

## 3. Full solution approach

1. Compress all segment endpoints into graph vertex IDs.
2. For each segment:
   - determine its two endpoint vertex IDs,
   - compute whether it crosses the upward ray from headquarters 1,
   - compute whether it crosses the upward ray from headquarters 2,
   - set `label = cross1 XOR cross2`.
3. Build an undirected weighted graph.
4. For every vertex `s`:
   - run Dijkstra on the doubled graph from state `(s, 0)`,
   - check distance to `(s, 1)`.
5. Keep the best source vertex.
6. Run Dijkstra once more from the best source and reconstruct the chosen segment indices using parent pointers.
7. Output total cost and the segment indices.

Complexity:

```text
V ≤ 2N, E = N

For each source:
    Dijkstra on 2V states and O(E) edges

Total complexity:
    O(V * E log V)

With N ≤ 300, this easily fits.
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Point {
    long long x, y;
};

struct AdjEdge {
    int to;
    int cost;
    int id; // original segment index
};

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

    int n;
    cin >> n;

    vector<Point> a(n), b(n);
    vector<int> cost(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y >> cost[i];
    }

    Point h1, h2;
    cin >> h1.x >> h1.y >> h2.x >> h2.y;

    // Compress endpoint coordinates into graph vertex ids.
    map<pair<long long, long long>, int> id;

    auto get_id = [&](Point p) -> int {
        pair<long long, long long> key = {p.x, p.y};
        auto it = id.find(key);
        if (it != id.end()) return it->second;

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

    /*
        Checks if segment ab crosses the upward vertical ray from h.

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

        We use a half-open convention on the x-coordinate:
            one endpoint must satisfy x > h.x and the other must not.

        This avoids double-counting crossings that happen exactly at graph
        vertices.
    */
    auto crosses_up_ray = [](Point p, Point q, Point h) -> bool {
        bool side_p = p.x > h.x;
        bool side_q = q.x > h.x;

        // Segment does not cross the vertical line x = h.x.
        if (side_p == side_q) return false;

        /*
            Compute whether the y-coordinate of the intersection with
            x = h.x is strictly above h.y.

            y_cross = p.y + (h.x - p.x) * (q.y - p.y) / (q.x - p.x)

            To avoid floating point, compare:
                y_cross > h.y

            after multiplying by dx = q.x - p.x, remembering that dx may be
            negative.
        */
        long long dx = q.x - p.x;

        __int128 value =
            (__int128)(p.y - h.y) * dx +
            (__int128)(h.x - p.x) * (q.y - p.y);

        if (dx > 0) return value > 0;
        else return value < 0;
    };

    vector<int> eu(n), ev(n), label(n);

    for (int i = 0; i < n; i++) {
        eu[i] = get_id(a[i]);
        ev[i] = get_id(b[i]);

        int c1 = crosses_up_ray(a[i], b[i], h1);
        int c2 = crosses_up_ray(a[i], b[i], h2);

        // This edge contributes to separation parity iff it crosses exactly
        // one of the two headquarters' rays.
        label[i] = c1 ^ c2;
    }

    int vertices = (int)id.size();

    vector<vector<AdjEdge>> graph(vertices);

    for (int i = 0; i < n; i++) {
        graph[eu[i]].push_back({ev[i], cost[i], i});
        graph[ev[i]].push_back({eu[i], cost[i], i});
    }

    const long long INF = (long long)4e18;

    /*
        Dijkstra on doubled graph.

        State encoding:
            state = 2 * vertex + parity

        parity is accumulated XOR of edge labels along the current path.
    */
    auto dijkstra = [&](int source_state,
                        vector<long long>& dist,
                        vector<pair<int, int>>& parent) {
        int states = 2 * vertices;

        dist.assign(states, INF);

        // parent[state] = {previous_state, segment_index_used}
        parent.assign(states, {-1, -1});

        priority_queue<
            pair<long long, int>,
            vector<pair<long long, int>>,
            greater<pair<long long, int>>
        > pq;

        dist[source_state] = 0;
        pq.push({0, source_state});

        while (!pq.empty()) {
            auto [d, state] = pq.top();
            pq.pop();

            if (d != dist[state]) continue;

            int v = state / 2;
            int parity = state & 1;

            for (const AdjEdge& e : graph[v]) {
                int new_parity = parity ^ label[e.id];
                int next_state = 2 * e.to + new_parity;

                long long nd = d + e.cost;

                if (nd < dist[next_state]) {
                    dist[next_state] = nd;
                    parent[next_state] = {state, e.id};
                    pq.push({nd, next_state});
                }
            }
        }
    };

    long long best_cost = INF;
    int best_source = -1;

    vector<long long> dist;
    vector<pair<int, int>> parent;

    // Try every vertex as the start/end of the odd-parity closed walk.
    for (int s = 0; s < vertices; s++) {
        int source_state = 2 * s;
        int target_state = 2 * s + 1;

        dijkstra(source_state, dist, parent);

        if (dist[target_state] < best_cost) {
            best_cost = dist[target_state];
            best_source = s;
        }
    }

    // Re-run Dijkstra from the best source to reconstruct the actual wall.
    dijkstra(2 * best_source, dist, parent);

    vector<int> answer_segments;

    int state = 2 * best_source + 1;

    while (parent[state].first != -1) {
        int segment_id = parent[state].second;

        // Output uses 1-based indices.
        answer_segments.push_back(segment_id + 1);

        state = parent[state].first;
    }

    cout << best_cost << '\n';
    cout << answer_segments.size() << '\n';

    for (int i = 0; i < (int)answer_segments.size(); i++) {
        if (i) cout << ' ';
        cout << answer_segments[i];
    }
    cout << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
import heapq


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    ptr = 0

    n = data[ptr]
    ptr += 1

    seg_a = []
    seg_b = []
    seg_cost = []

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

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

    h1 = (data[ptr], data[ptr + 1])
    h2 = (data[ptr + 2], data[ptr + 3])

    # Compress all endpoint coordinates into graph vertex ids.
    vertex_id = {}

    def get_id(p):
        if p not in vertex_id:
            vertex_id[p] = len(vertex_id)
        return vertex_id[p]

    def crosses_up_ray(p, q, h):
        """
        Return True if segment pq crosses the upward ray from h:

            x = h.x, y > h.y

        A half-open convention is used:
        one endpoint must have x > h.x and the other must not.
        This avoids double-counting when the ray passes through a graph vertex.
        """
        px, py = p
        qx, qy = q
        hx, hy = h

        side_p = px > hx
        side_q = qx > hx

        # No crossing of the vertical line x = hx.
        if side_p == side_q:
            return False

        dx = qx - px

        # Exact integer comparison of:
        # y_cross > hy
        #
        # y_cross = py + (hx - px) * (qy - py) / dx
        value = (py - hy) * dx + (hx - px) * (qy - py)

        if dx > 0:
            return value > 0
        else:
            return value < 0

    eu = [0] * n
    ev = [0] * n
    label = [0] * n

    for i in range(n):
        eu[i] = get_id(seg_a[i])
        ev[i] = get_id(seg_b[i])

        c1 = crosses_up_ray(seg_a[i], seg_b[i], h1)
        c2 = crosses_up_ray(seg_a[i], seg_b[i], h2)

        # Edge label is 1 iff the edge crosses exactly one of the two rays.
        label[i] = int(c1) ^ int(c2)

    vertices = len(vertex_id)

    # Build undirected graph.
    # graph[v] contains tuples:
    #   (neighbor_vertex, edge_cost, segment_index)
    graph = [[] for _ in range(vertices)]

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

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

    def dijkstra(source_state):
        """
        Dijkstra on the doubled graph.

        State encoding:
            state = 2 * vertex + parity

        parity is the accumulated XOR of edge labels on the path.
        """
        total_states = 2 * vertices
        INF = 10**30

        dist = [INF] * total_states

        # parent[state] = (previous_state, segment_index_used)
        parent = [(-1, -1)] * total_states

        dist[source_state] = 0
        pq = [(0, source_state)]

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

            if d != dist[state]:
                continue

            v = state // 2
            parity = state & 1

            for to, cost, seg_idx in graph[v]:
                new_parity = parity ^ label[seg_idx]
                next_state = 2 * to + new_parity

                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

    INF = 10**30
    best_cost = INF
    best_source = -1

    # Try every original graph vertex as start/end of the wall cycle.
    for s in range(vertices):
        source_state = 2 * s
        target_state = 2 * s + 1

        dist, _ = dijkstra(source_state)

        if dist[target_state] < best_cost:
            best_cost = dist[target_state]
            best_source = s

    # Re-run Dijkstra from the best source to reconstruct the wall.
    dist, parent = dijkstra(2 * best_source)

    state = 2 * best_source + 1
    answer_segments = []

    while parent[state][0] != -1:
        previous_state, seg_idx = parent[state]

        # Convert to 1-based segment number.
        answer_segments.append(seg_idx + 1)

        state = previous_state

    print(best_cost)
    print(len(answer_segments))
    print(*answer_segments)


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