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

545. Cut the rope, another rope and so on!
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A game called "Cut the rope, another rope and so on!" is very popular in Berland. People all over the country just cut ropes on their bPads and bPhones over and over again.

The game is about sequentially cutting ropes with a small ball hanging on their ends. At the beginning of the game all ropes have one end attached to the top of the screen, that is, we can assume that the ends are located on the horizontal axis Ox. The other ends of the ropes are connected together and a small ball is attached to them. The ropes never shrink or stretch. At the beginning of the game the system is in a static state — some ropes are tight, some might be loose. In this game, the ball should be considered as a material point, that is, we assume that it is infinitely small.




Let's suppose that at the beginning the ball is suspended on n ropes. A player cuts off n-1 uncut ropes, one after another. The ball may move in some way after some ropes are cut. The next cutting is made as soon as the ball becomes static after the previous cutting (the first cutting is made immediately). If the present cutting does not change the ball's position, then the next cutting is done immediately.

The physics in this game is a bit peculiar: educated people say that the motion of the ball is going in a perfectly viscous medium. This means that at any time the ball is moving so that it reduces the potential energy in the fastest way. For example, if the ball can fall straight down, it moves exactly this way. Note that the ball never swings, that is, its movement always moves it below its current position. You should assume that ropes have negligible masses compared with the mass of the ball.

Assuming that the ball always moves at the constant speed of 1 unit of length per unit of time, find the position of the ball at the given moments of time t1, t2,..., tm.

Input
The first input line contains two integers n and m (2 ≤ n ≤ 20; 1 ≤ m ≤ 1000) — the number of ropes and the number of ball position queries, correspondingly.

The second line contains n integers x1, x2,..., xn (1 ≤ xi ≤ 200) — the coordinates of the ropes' attachment points on the horizontal axis.

The third line contains n integers l1, l2,..., ln (1 ≤ li ≤ 200), li is the length of the i-th rope. It is guaranteed that values x1, x2,..., xn and l1, l2,..., ln are such that the initial configuration really exists, that is, the lower ends of all ropes can be simultaneously tied to a ball. It is guaranteed that no two ropes have equal lengths and attached to the same point at the same time.

The fourth line describes the sequence of cuts, it contains n-1 distinct integers p1, p2,..., pn-1 (1 ≤ pj ≤ n), where pj is the index of the rope that is the j-th one to be cut.

The last input line contains m real numbers t1, t2,..., tm (0 ≤ tk ≤ 1000) — the moments of time for determining the ball's position. All ti are given with no more than three digits after the decimal point. The first rope is cut at time 0, each of the other ropes is cut at the moment the ball becomes stable after the cutting of the previous rope. If the current cutting doesn't change the ball's position, then the next rope is cut immediately. All values t1, t2,..., tm are distinct and are given in the increasing order.

Output
Print m lines, the k-th line must contain the coordinates of the ball at time tk. Consider all ropes attached to the Ox axis, and the Oy axis is directed upwards. Print the numbers with at least 5 digits after the decimal point. After the ball hangs on the last rope, it doesn't move anymore.

Example(s)
sample input
sample output
3 4
1 1 3
5 10 20
1 2
2.5 10 16 20
1.0000000000 -7.5000000000
1.0000000000 -15.0000000000
2.0972097000 -19.9796138520
3.0000000000 -20.0000000000

sample input
sample output
3 7
2 22 19
12 12 10
2 1
0 0.18 0.19 4.39 6 7 9
12.0000000000 -6.6332495807
11.8993800085 -6.7824977292
11.8937244905 -6.7907448565
15.0867736994 -9.2025355158
16.6125973239 -9.7108345914
17.5939901889 -9.9006634329
19.0000000000 -10.0000000000

<|response|>
1. Abridged problem statement

There are `n` ropes attached to points `(xi, 0)` on the horizontal axis. Rope `i` has length `li`, and all rope ends are tied to one point-like ball.

A rope does not stretch, so while rope `i` exists, the ball must satisfy `(x-xi)^2 + y^2 <= li^2`.

Initially the ball is stable. Then `n-1` ropes are cut in a given order. After each cut, the ball moves until it becomes stable again; then the next cut happens. The ball moves with speed `1` and always chooses the direction that decreases potential energy fastest, meaning it tries to move as downward as possible.

For each query time `t`, output the ball coordinates.

Constraints are small: `n ≤ 20`, `m ≤ 1000`.

---

2. Key observations needed to solve the problem

Observation 1: Each rope is a disk constraint

For rope `i`, the ball must stay inside or on the disk centered at `(xi, 0)` with radius `li`.

For an active rope set `S`, all feasible positions are the intersection of disks D_i for i in S.

---

Observation 2: Stable position is the lowest feasible point

Gravity pulls downward, so the stable position for active rope set `S` is the point with minimum `y` inside the intersection of disks.

The lowest point must be either:

1. The bottom of one circle: `(xi, -li)`
2. An intersection point of two circles.

Since `n ≤ 20`, we can enumerate all such candidate points and keep the lowest one that lies inside every active disk.

---

Observation 3: Motion consists only of vertical segments and circle arcs

At any moment, some ropes can be tight. A tight rope means the ball lies exactly on that circle boundary.

The ball wants to move in gravity direction `g = (0, -1)` but it cannot leave any active disk.

For each tight rope `i`, define the outward normal `n_i = (p - (xi,0)) / li`.

A velocity direction `d` is feasible if `d . n_i <= 0`.

If gravity itself satisfies all constraints, the ball falls vertically.

Otherwise, the ball slides along the boundary of one tight circle. Therefore each trajectory piece is either:

- a vertical segment,
- or an arc of some circle.

---

Observation 4: We can trace motion event by event

During vertical motion, the next event is hitting a circle boundary.

During circular arc motion, the next event is either:

- reaching an intersection with another active circle,
- or reaching the bottom point of the current circle.

Because there are at most `20` ropes, event-based simulation is easily fast enough.

---

3. Full solution approach

Step 1: Compute equilibrium for an active rope set

For current active ropes `S`:

1. Add all circle bottom points `(xi, -li)` as candidates.
2. Add all pairwise circle intersection points.
3. For every candidate, check whether it lies inside every disk in `S`.
4. Choose the valid candidate with smallest `y`.

---

Step 2: Process cuts

Start with all ropes active. Compute initial equilibrium.

For each cut:

1. Remove the cut rope from the active set.
2. Compute the new equilibrium.
3. If the new equilibrium is the same as the current position, this cut causes no movement.
4. Otherwise, trace the path from current position to the new equilibrium.
5. Store this motion phase: start time, start point, end point, list of path segments, total length.

Since the ball speed is `1`, phase duration equals total path length.

---

Step 3: Trace one motion phase

At current position:

1. Find tight ropes.
2. Compute the steepest feasible descent direction.
3. If direction is vertical: fall until hitting the nearest circle boundary below, or until reaching the target equilibrium.
4. If direction follows a circle: move along the circle arc, stop at the first intersection with another circle, or at the circle bottom.
5. Repeat until the target equilibrium is reached.

---

Step 4: Answer queries

For each query time `t`:

1. Find the motion phase containing `t`.
2. Let `s = t - phase.start_time`.
3. Walk through the stored segments until distance `s` is reached.
4. Interpolate inside that segment: linearly for vertical segments, by angle for circular arcs.
5. If `t` is after all phases, output the final stable position.

---

4. C++ implementation with comments

```cpp
#include <bits/stdc++.h>

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 = long double;

struct Point {
    static constexpr coord_t eps = 1e-12L;
    static inline const coord_t PI = acosl((coord_t)-1.0L);

    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 dot(const Point& p) const { return x * p.x + y * p.y; }
    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrtl(norm2()); }

    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;
    }
};

int n, m;
vector<coord_t> xs, ls;
vector<int> cut_seq;
vector<coord_t> ts;

bool inside_disks(const Point& p, const vector<int>& S, coord_t tol = 1e-7L) {
    for(int i: S) {
        coord_t dx = p.x - xs[i], dy = p.y;
        if(dx * dx + dy * dy > ls[i] * ls[i] + tol) {
            return false;
        }
    }

    return true;
}

vector<Point> circle_pair_inters(int i, int j) {
    coord_t dx = xs[j] - xs[i];
    coord_t d = fabsl(dx);
    if(d < 1e-14L) {
        return {};
    }

    coord_t r1 = ls[i], r2 = ls[j];
    if(d > r1 + r2 + 1e-12L || d < fabsl(r1 - r2) - 1e-12L) {
        return {};
    }

    coord_t a = (r1 * r1 - r2 * r2 + d * d) / (2 * d);
    coord_t h2 = r1 * r1 - a * a;
    if(h2 < 0) {
        h2 = 0;
    }

    coord_t h = sqrtl(h2);
    coord_t sgn = (xs[j] > xs[i]) ? 1.0L : -1.0L;
    coord_t mx = xs[i] + a * sgn;
    return {Point(mx, h), Point(mx, -h)};
}

Point equilibrium(const vector<int>& S) {
    if(S.empty()) {
        return Point(0, -1e18L);
    }

    vector<Point> cands;
    for(int i: S) {
        cands.push_back(Point(xs[i], -ls[i]));
    }

    for(size_t a = 0; a < S.size(); ++a) {
        for(size_t b = a + 1; b < S.size(); ++b) {
            for(auto& q: circle_pair_inters(S[a], S[b])) {
                cands.push_back(q);
            }
        }
    }

    Point best(0, 1e18L);
    for(auto& c: cands) {
        if(inside_disks(c, S) && c.y < best.y) {
            best = c;
        }
    }

    return best;
}

vector<int> tight_set(const Point& p, const vector<int>& S) {
    vector<int> tight;
    for(int i: S) {
        coord_t dx = p.x - xs[i], dy = p.y;
        coord_t d = sqrtl(dx * dx + dy * dy);
        if(fabsl(d - ls[i]) < 1e-6L) {
            tight.push_back(i);
        }
    }

    return tight;
}

struct DirResult {
    Point dir;
    int arc_circle;
};

DirResult descent_dir(const Point& p, const vector<int>& tight) {
    Point g(0, -1);
    if(tight.empty()) {
        return {g, -1};
    }

    vector<Point> normals;
    for(int i: tight) {
        Point r(p.x - xs[i], p.y);
        coord_t rn = r.norm();
        if(rn < 1e-14L) {
            normals.push_back(Point(0, -1));
        } else {
            normals.push_back(r / rn);
        }
    }

    bool g_ok = true;
    for(auto& nk: normals) {
        if(g.dot(nk) > 1e-9L) {
            g_ok = false;
            break;
        }
    }
    if(g_ok) {
        int tangent_circle = -1;
        for(size_t k = 0; k < tight.size(); ++k) {
            if(fabsl(g.dot(normals[k])) < 1e-9L) {
                tangent_circle = tight[k];
                break;
            }
        }

        return {g, tangent_circle};
    }

    DirResult best;
    best.dir = Point(0, 1);
    best.arc_circle = -1;
    bool found = false;
    for(size_t k = 0; k < tight.size(); ++k) {
        const Point& nk = normals[k];
        coord_t gn = g.dot(nk);
        Point d(-gn * nk.x, -1 - gn * nk.y);
        coord_t dn = d.norm();
        if(dn < 1e-14L) {
            continue;
        }

        d = d / dn;
        if(d.y >= -1e-12L) {
            continue;
        }

        bool ok = true;
        for(size_t kk = 0; kk < tight.size(); ++kk) {
            if(kk == k) {
                continue;
            }
            if(d.dot(normals[kk]) > 1e-9L) {
                ok = false;
                break;
            }
        }
        if(!ok) {
            continue;
        }

        if(!found || d.y < best.dir.y) {
            best.dir = d;
            best.arc_circle = tight[k];
            found = true;
        }
    }

    if(!found) {
        return {Point(0, 0), -1};
    }

    return best;
}

struct Segment {
    bool is_vert;
    coord_t x, y0, y1;
    coord_t cx, r, theta0, theta1;
    coord_t len;
};

struct Phase {
    coord_t start_t;
    coord_t total_len;
    Point start_p, end_p;
    vector<Segment> segs;
};

coord_t fwd_angle(coord_t from, coord_t to, coord_t s) {
    coord_t two_pi = 2 * Point::PI;
    coord_t dt = s * (to - from);
    dt = fmodl(dt, two_pi);
    if(dt < 0) {
        dt += two_pi;
    }
    return dt;
}

vector<Segment> trace_path(Point start, Point target, const vector<int>& S) {
    vector<Segment> segs;
    Point cur = start;
    coord_t two_pi = 2 * Point::PI;
    for(int iter = 0; iter < 20000; ++iter) {
        if((cur - target).norm() < 1e-9L) {
            break;
        }

        vector<int> tight = tight_set(cur, S);
        DirResult dr = descent_dir(cur, tight);
        if(dr.dir.norm() < 1e-9L) {
            break;
        }

        if(dr.arc_circle == -1) {
            coord_t y_end = -1e18L;
            for(int i: S) {
                bool is_t = false;
                for(int t: tight) {
                    if(t == i) {
                        is_t = true;
                        break;
                    }
                }
                if(is_t) {
                    continue;
                }

                coord_t dx = cur.x - xs[i];
                coord_t disc = ls[i] * ls[i] - dx * dx;
                if(disc < 0) {
                    continue;
                }

                coord_t y_b = -sqrtl(disc);
                if(y_b < cur.y - 1e-12L && y_b > y_end) {
                    y_end = y_b;
                }
            }

            if(y_end < -1e17L) {
                y_end = target.y;
            }

            if(fabsl(cur.x - target.x) < 1e-9L && y_end < target.y - 1e-12L) {
                y_end = target.y;
            }

            Segment sg;
            sg.is_vert = true;
            sg.x = cur.x;
            sg.y0 = cur.y;
            sg.y1 = y_end;
            sg.len = cur.y - y_end;
            if(sg.len < 1e-12L) {
                break;
            }

            segs.push_back(sg);
            cur = Point(cur.x, y_end);
        } else {
            int arc_i = dr.arc_circle;
            coord_t theta0 = atan2l(cur.y, cur.x - xs[arc_i]);
            Point tang(-sinl(theta0), cosl(theta0));
            coord_t s = (tang.dot(dr.dir) > 0) ? 1.0L : -1.0L;
            coord_t best_dt = two_pi;
            Point best_pt = cur;
            bool have_event = false;
            for(int j: S) {
                if(j == arc_i) {
                    continue;
                }

                for(auto& q: circle_pair_inters(arc_i, j)) {
                    coord_t tq = atan2l(q.y, q.x - xs[arc_i]);
                    coord_t dt = fwd_angle(theta0, tq, s);
                    if(dt < 1e-9L) {
                        continue;
                    }
                    if(dt < best_dt) {
                        best_dt = dt;
                        best_pt = q;
                        have_event = true;
                    }
                }
            }

            {
                coord_t tq = -Point::PI / 2;
                coord_t dt = fwd_angle(theta0, tq, s);
                if(dt > 1e-9L && dt < best_dt) {
                    best_dt = dt;
                    best_pt = Point(xs[arc_i], -ls[arc_i]);
                    have_event = true;
                }
            }

            if(!have_event) {
                break;
            }

            coord_t theta1 = theta0 + s * best_dt;
            Segment sg;
            sg.is_vert = false;
            sg.cx = xs[arc_i];
            sg.r = ls[arc_i];
            sg.theta0 = theta0;
            sg.theta1 = theta1;
            sg.len = ls[arc_i] * best_dt;
            if(sg.len < 1e-12L) {
                break;
            }

            segs.push_back(sg);
            cur = best_pt;
        }

        if((cur - target).norm() < 1e-7L) {
            cur = target;
            break;
        }
    }

    return segs;
}

Point interpolate(const Phase& ph, coord_t s) {
    if(s <= 0) {
        return ph.start_p;
    }

    if(s >= ph.total_len - 1e-12L) {
        return ph.end_p;
    }

    coord_t acc = 0;
    for(const auto& sg: ph.segs) {
        if(s <= acc + sg.len + 1e-12L) {
            coord_t local = s - acc;
            coord_t frac = (sg.len > 1e-14L) ? local / sg.len : 0;
            if(sg.is_vert) {
                return Point(sg.x, sg.y0 + (sg.y1 - sg.y0) * frac);
            } else {
                coord_t theta = sg.theta0 + (sg.theta1 - sg.theta0) * frac;
                return Point(sg.cx + sg.r * cosl(theta), sg.r * sinl(theta));
            }
        }
        acc += sg.len;
    }

    return ph.end_p;
}

void read() {
    cin >> n >> m;
    xs.resize(n);
    ls.resize(n);
    for(auto& v: xs) {
        cin >> v;
    }

    for(auto& v: ls) {
        cin >> v;
    }

    cut_seq.resize(n - 1);
    for(auto& v: cut_seq) {
        cin >> v;
        --v;
    }

    ts.resize(m);
    for(auto& v: ts) {
        cin >> v;
    }
}

void solve() {
    // Each remaining rope i is the closed disk D_i = { p : (p.x - xs[i])^2
    // + p.y^2 <= ls[i]^2 } centered at (xs[i], 0). For any non-empty active
    // set S the stable position of the ball is the unique point of minimum
    // y inside the intersection of those disks. The KKT conditions of
    // minimising y over that intersection say at least one constraint is
    // active at the optimum, and at most two are needed in 2D; the
    // candidates are therefore the |S| circle bottoms (xs[i], -ls[i]) and
    // the at most two intersections of every pair of circles. We enumerate
    // all of them, keep those that lie inside every disk of S, and pick the
    // one with the smallest y.
    //
    // Cuts are processed in the given order. Cut 1 happens at t = 0; cut j
    // (j >= 2) happens at the instant the ball first becomes stationary
    // after cut j - 1. If a cut does not change the stable point it is
    // instantaneous.
    //
    // Between two consecutive equilibria the ball follows a perfectly
    // viscous gradient descent: its velocity is the projection of gravity
    // g = (0, -1) onto the feasible tangent cone at the current point.
    // Let T be the set of currently tight constraints (circles where
    // |p - c_i| = ls[i]); the tangent cone is { d : d . n_i <= 0 for i in T }
    // with outward normals n_i = (p - c_i) / ls[i]. The projection is
    // computed analytically:
    //   - if g satisfies all g . n_i <= 0, the velocity is g itself and the
    //     motion is straight down;
    //   - otherwise for each k in T we compute d_k = g - (g . n_k) n_k,
    //     which is the projection of g onto the hyperplane n_k = 0
    //     (i.e. the unit tangent to circle k at p that lowers y), and keep
    //     the one whose y-component is the smallest among those that still
    //     satisfy d . n_l <= 0 for every other l in T;
    //   - if no such d exists the cone has only the zero descent direction
    //     and the ball is at equilibrium.
    //
    // Each piece of the trajectory is therefore either a vertical segment
    // (interior motion until we touch the first circle from inside) or a
    // circular arc on some currently-tight rope. While on the arc of circle
    // i we follow it until the first angular event: either an intersection
    // with another active circle j or the bottom of circle i at theta =
    // -pi/2. Hitting an intersection turns it into a vertex and the next
    // iteration's projection chooses whether to transfer to the new circle,
    // re-enter the interior, or stop. The trajectory is built event by
    // event with at most O(n^2) events total.
    //
    // Each phase stores its starting time, total arc length, the precise
    // (start, end) equilibrium points, and the ordered list of vertical /
    // arc segments with their Euclidean lengths. Because the ball travels
    // at unit speed, the time spent in a phase equals its total length.
    // A query at time t locates the unique phase whose interval contains t,
    // walks the segment list by the local distance s = t - start_t,
    // interpolates linearly along the active piece (vertical or arc), and
    // returns the resulting point. After the final cut the ball stays at
    // the bottom of the last rope for all future times.

    vector<int> active(n);
    iota(active.begin(), active.end(), 0);

    Point cur = equilibrium(active);
    coord_t cur_time = 0;
    vector<Phase> phases;
    Point final_pos = cur;

    for(int ci = 0; ci < n - 1; ++ci) {
        int cut = cut_seq[ci];
        active.erase(find(active.begin(), active.end(), cut));

        Point new_eq = equilibrium(active);
        if((new_eq - cur).norm() < 1e-9L) {
            cur = new_eq;
            final_pos = cur;
            continue;
        }

        vector<Segment> segs = trace_path(cur, new_eq, active);
        coord_t total = 0;
        for(auto& sg: segs) {
            total += sg.len;
        }

        if(total < 1e-9L) {
            cur = new_eq;
            final_pos = cur;
            continue;
        }

        Phase ph;
        ph.start_t = cur_time;
        ph.total_len = total;
        ph.start_p = cur;
        ph.end_p = new_eq;
        ph.segs = std::move(segs);
        phases.push_back(std::move(ph));

        cur = new_eq;
        cur_time += total;
        final_pos = cur;
    }

    cout << fixed << setprecision(10);
    for(coord_t t: ts) {
        Point pos = final_pos;
        for(const auto& ph: phases) {
            if(t <= ph.start_t + ph.total_len + 1e-9L) {
                coord_t s = t - ph.start_t;
                if(s < 0) {
                    s = 0;
                }
                if(s > ph.total_len) {
                    s = ph.total_len;
                }
                pos = interpolate(ph, s);
                break;
            }
        }

        cout << pos.x << ' ' << pos.y << '\n';
    }
}

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

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

    return 0;
}
```

---

5. Python implementation with comments

```python
import sys
import math
from dataclasses import dataclass

# Numerical tolerances.
EPS = 1e-12
PI = math.acos(-1.0)


@dataclass
class Point:
    # 2D point/vector.
    x: float = 0.0
    y: float = 0.0

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, c):
        return Point(self.x * c, self.y * c)

    def __truediv__(self, c):
        return Point(self.x / c, self.y / c)

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def norm2(self):
        return self.x * self.x + self.y * self.y

    def norm(self):
        return math.sqrt(self.norm2())


@dataclass
class DirResult:
    # Chosen descent direction and circle to follow.
    dir: Point
    arc_circle: int


@dataclass
class Segment:
    # A segment is either vertical or a circular arc.
    is_vert: bool

    # Vertical segment data.
    x: float = 0.0
    y0: float = 0.0
    y1: float = 0.0

    # Arc data.
    cx: float = 0.0
    r: float = 0.0
    theta0: float = 0.0
    theta1: float = 0.0

    # Euclidean length.
    length: float = 0.0


@dataclass
class Phase:
    # One motion phase after a cut.
    start_t: float
    total_len: float
    start_p: Point
    end_p: Point
    segs: list


def inside_disks(p, S, xs, ls, tol=1e-7):
    # Check whether point p lies inside every disk indexed by S.
    for i in S:
        dx = p.x - xs[i]
        dy = p.y
        if dx * dx + dy * dy > ls[i] * ls[i] + tol:
            return False
    return True


def circle_pair_inters(i, j, xs, ls):
    # Compute intersection points of circles i and j.
    dx = xs[j] - xs[i]
    d = abs(dx)

    if d < 1e-14:
        return []

    r1 = ls[i]
    r2 = ls[j]

    if d > r1 + r2 + 1e-12 or d < abs(r1 - r2) - 1e-12:
        return []

    a = (r1 * r1 - r2 * r2 + d * d) / (2.0 * d)
    h2 = r1 * r1 - a * a

    if h2 < 0:
        h2 = 0.0

    h = math.sqrt(h2)
    sgn = 1.0 if xs[j] > xs[i] else -1.0
    mx = xs[i] + a * sgn

    return [Point(mx, h), Point(mx, -h)]


def equilibrium(S, xs, ls):
    # Find the lowest point in the intersection of active disks.
    if not S:
        return Point(0.0, -1e18)

    candidates = []

    for i in S:
        candidates.append(Point(xs[i], -ls[i]))

    for a in range(len(S)):
        for b in range(a + 1, len(S)):
            candidates.extend(circle_pair_inters(S[a], S[b], xs, ls))

    best = Point(0.0, 1e18)

    for c in candidates:
        if inside_disks(c, S, xs, ls) and c.y < best.y:
            best = c

    return best


def tight_set(p, S, xs, ls):
    # Return active ropes that are tight at point p.
    tight = []

    for i in S:
        dx = p.x - xs[i]
        dy = p.y
        d = math.sqrt(dx * dx + dy * dy)

        if abs(d - ls[i]) < 1e-6:
            tight.append(i)

    return tight


def descent_dir(p, tight, xs, ls):
    # Gravity direction.
    g = Point(0.0, -1.0)

    if not tight:
        return DirResult(g, -1)

    normals = []

    for i in tight:
        r = Point(p.x - xs[i], p.y)
        rn = r.norm()

        if rn < 1e-14:
            normals.append(Point(0.0, -1.0))
        else:
            normals.append(r / rn)

    g_ok = True
    for nk in normals:
        if g.dot(nk) > 1e-9:
            g_ok = False
            break

    if g_ok:
        tangent_circle = -1

        for k, nk in enumerate(normals):
            if abs(g.dot(nk)) < 1e-9:
                tangent_circle = tight[k]
                break

        return DirResult(g, tangent_circle)

    best_dir = Point(0.0, 1.0)
    best_circle = -1
    found = False

    for k, nk in enumerate(normals):
        gn = g.dot(nk)
        d = Point(-gn * nk.x, -1.0 - gn * nk.y)
        dn = d.norm()

        if dn < 1e-14:
            continue

        d = d / dn

        if d.y >= -1e-12:
            continue

        ok = True

        for kk, nkk in enumerate(normals):
            if kk == k:
                continue

            if d.dot(nkk) > 1e-9:
                ok = False
                break

        if not ok:
            continue

        if not found or d.y < best_dir.y:
            best_dir = d
            best_circle = tight[k]
            found = True

    if not found:
        return DirResult(Point(0.0, 0.0), -1)

    return DirResult(best_dir, best_circle)


def fwd_angle(frm, to, s):
    # Angular distance from frm to to in direction s = +1 or -1.
    two_pi = 2.0 * PI
    dt = s * (to - frm)
    dt = math.fmod(dt, two_pi)

    if dt < 0:
        dt += two_pi

    return dt


def trace_path(start, target, S, xs, ls):
    # Build vertical/arc segments from start to target.
    segs = []
    cur = start
    two_pi = 2.0 * PI

    for _ in range(20000):
        if (cur - target).norm() < 1e-9:
            break

        tight = tight_set(cur, S, xs, ls)
        dr = descent_dir(cur, tight, xs, ls)

        if dr.dir.norm() < 1e-9:
            break

        if dr.arc_circle == -1:
            # Vertical free fall.
            y_end = -1e18

            for i in S:
                if i in tight:
                    continue

                dx = cur.x - xs[i]
                disc = ls[i] * ls[i] - dx * dx

                if disc < 0:
                    continue

                y_b = -math.sqrt(disc)

                if y_b < cur.y - 1e-12 and y_b > y_end:
                    y_end = y_b

            if y_end < -1e17:
                y_end = target.y

            if abs(cur.x - target.x) < 1e-9 and y_end < target.y - 1e-12:
                y_end = target.y

            length = cur.y - y_end

            if length < 1e-12:
                break

            segs.append(Segment(
                is_vert=True,
                x=cur.x,
                y0=cur.y,
                y1=y_end,
                length=length
            ))

            cur = Point(cur.x, y_end)

        else:
            arc_i = dr.arc_circle

            theta0 = math.atan2(cur.y, cur.x - xs[arc_i])
            tang = Point(-math.sin(theta0), math.cos(theta0))
            s = 1.0 if tang.dot(dr.dir) > 0 else -1.0

            best_dt = two_pi
            best_pt = cur
            have_event = False

            for j in S:
                if j == arc_i:
                    continue

                for q in circle_pair_inters(arc_i, j, xs, ls):
                    tq = math.atan2(q.y, q.x - xs[arc_i])
                    dt = fwd_angle(theta0, tq, s)

                    if dt < 1e-9:
                        continue

                    if dt < best_dt:
                        best_dt = dt
                        best_pt = q
                        have_event = True

            tq = -PI / 2.0
            dt = fwd_angle(theta0, tq, s)

            if dt > 1e-9 and dt < best_dt:
                best_dt = dt
                best_pt = Point(xs[arc_i], -ls[arc_i])
                have_event = True

            if not have_event:
                break

            theta1 = theta0 + s * best_dt
            length = ls[arc_i] * best_dt

            if length < 1e-12:
                break

            segs.append(Segment(
                is_vert=False,
                cx=xs[arc_i],
                r=ls[arc_i],
                theta0=theta0,
                theta1=theta1,
                length=length
            ))

            cur = best_pt

        if (cur - target).norm() < 1e-7:
            cur = target
            break

    return segs


def interpolate(phase, s):
    # Return point after traveling distance s in this phase.
    if s <= 0:
        return phase.start_p

    if s >= phase.total_len - 1e-12:
        return phase.end_p

    acc = 0.0

    for sg in phase.segs:
        if s <= acc + sg.length + 1e-12:
            local = s - acc
            frac = local / sg.length if sg.length > 1e-14 else 0.0

            if sg.is_vert:
                return Point(
                    sg.x,
                    sg.y0 + (sg.y1 - sg.y0) * frac
                )
            else:
                theta = sg.theta0 + (sg.theta1 - sg.theta0) * frac
                return Point(
                    sg.cx + sg.r * math.cos(theta),
                    sg.r * math.sin(theta)
                )

        acc += sg.length

    return phase.end_p


def solve():
    data = sys.stdin.read().strip().split()

    if not data:
        return

    ptr = 0

    n = int(data[ptr])
    ptr += 1

    m = int(data[ptr])
    ptr += 1

    xs = [float(data[ptr + i]) for i in range(n)]
    ptr += n

    ls = [float(data[ptr + i]) for i in range(n)]
    ptr += n

    # Convert cut order to zero-based indices.
    cut_seq = [int(data[ptr + i]) - 1 for i in range(n - 1)]
    ptr += n - 1

    ts = [float(data[ptr + i]) for i in range(m)]

    # Initially all ropes are active.
    active = list(range(n))

    # Initial equilibrium.
    cur = equilibrium(active, xs, ls)

    cur_time = 0.0
    phases = []
    final_pos = cur

    # Precompute all movement phases.
    for cut in cut_seq:
        # Remove cut rope.
        active.remove(cut)

        # New equilibrium after cutting.
        new_eq = equilibrium(active, xs, ls)

        # If unchanged, next cut is immediate.
        if (new_eq - cur).norm() < 1e-9:
            cur = new_eq
            final_pos = cur
            continue

        # Build trajectory.
        segs = trace_path(cur, new_eq, active, xs, ls)

        # Total duration equals path length.
        total = sum(sg.length for sg in segs)

        if total < 1e-9:
            cur = new_eq
            final_pos = cur
            continue

        phases.append(Phase(
            start_t=cur_time,
            total_len=total,
            start_p=cur,
            end_p=new_eq,
            segs=segs
        ))

        cur = new_eq
        cur_time += total
        final_pos = cur

    out = []

    # Answer queries.
    for t in ts:
        # If no phase contains t, ball is already at final position.
        pos = final_pos

        for ph in phases:
            if t <= ph.start_t + ph.total_len + 1e-9:
                s = t - ph.start_t

                if s < 0:
                    s = 0.0

                if s > ph.total_len:
                    s = ph.total_len

                pos = interpolate(ph, s)
                break

        out.append(f"{pos.x:.10f} {pos.y:.10f}")

    sys.stdout.write("\n".join(out))


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