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

477. Doors
Time limit per test: 1.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



It seems that the Museum of the Modern Technology is the only place where they don't celebrate Halloween! How can they be so far from all the mistical and mysterious? You can hardly believe that two weeks ago the Museum staff have destroyed the last detail that could bring with its ominous creak a bit of Halloween atmosphere to the realm of technology. They have replaced the old wooden doors with new automatic ones, and now they are scratching their heads over how to configure the doors.

By the order of the Director, two automatic doors were purchased. An automatic door is characterized by parameter t, called the , which can be set to an integer value from 1 to 109 during the door installation. Then the door functions on the following principle. If a person passes through the door at time p, the door opens at time p - t and closes at time p + t. There is an exceptional case when several people go in a row with a time interval not exceeding 2 t between any two consecutive people. In this case the door opens only once, t seconds before the first person in the row, and it closes t seconds after the last person in the row has passed through it. It is very important to set the optimal values of the door parameters. On the one hand, if the doors open and close too often, it will annoy visitors. On the other hand, if both doors stay opened for a long time, visitors can get cold.

More formally, two lists of time moments are given. At the moments p1 < p2 <... < pn people have passed through the first door, and at the moments q1 < q2 <... < qm people have passed through the second one. The task is to use the given statistics to find the optimal  for the doors — t1 for the first door and t2 for the second one that satisfy the following conditions:

The total number of openings of the doors must be minimal possible.
There is no continuous interval of time that both doors are opened during this interval and its length exceeds the given value d.

Input
The first line of the input contains three integers n, m and d (1 ≤ n, m ≤ 5000, 1 ≤ d ≤ 109). The second line contains numbers pi, and the third line contains numbers qi, given in the ascending order (1 ≤ pi, qi ≤ 109).

Output
Output two integers t1 and t2, separated by a single space. If there are multiple solutions, output any. If there is no solution, output "No solution".

Example(s)
sample input
sample output
3 2 4
1 6 13
7 11
3 2

<|response|>
## 1) Abridged problem statement

Two increasing sequences are given:

- Door 1 passage times: \(p_1 < \dots < p_n\)
- Door 2 passage times: \(q_1 < \dots < q_m\)

Each door has an integer parameter \(t \in [1,10^9]\). A person passing at time \(x\) would keep the door open on \([x-t, x+t]\), but consecutive people with gaps \(\le 2t\) form one "row", so their intervals merge and the door opens only once for that row. Thus, for a fixed \(t\), each door is open on a union of disjoint intervals; the number of intervals equals the number of openings.

Find integers \(t_1, t_2\) such that:

1. The total number of openings (intervals) of both doors is minimized.
2. There is **no** continuous time interval where **both doors are open** for longer than \(d\).

If no such pair exists, print `"No solution"`.

Constraints: \(1 \le n,m \le 5000\), times and \(d\) up to \(10^9\).

---

## 2) Key observations needed to solve the problem

1. **For a fixed \(t\), door open-times are merged intervals.**
   Each passage time \(x\) gives \([x-t, x+t]\). These intervals merge whenever consecutive people satisfy \(x_{i+1}-x_i \le 2t\). So we can build merged intervals by a linear sweep over the times.

2. **#Openings changes only at \(O(k)\) threshold values.**
   For consecutive times \(a_i,a_{i+1}\), they merge iff:
   \[
   a_{i+1}-a_i \le 2t \iff t \ge \left\lceil \frac{a_{i+1}-a_i}{2} \right\rceil
   \]
   Therefore, the interval structure (and openings count) only changes at these thresholds. So each door has only \(O(n)\)/\(O(m)\) relevant candidate \(t\) values.

3. **Overlap constraint can be checked in linear time.**
   Convert merged intervals into events \((L,+1)\), \((R,-1)\) for each door. Merge the two sorted event streams, maintain `balance` = how many doors are open (0..2). Whenever `balance==2`, both doors overlap; ensure no such segment length exceeds \(d\).

4. **Tie-breaking matters:** process "close" before "open" at the same time.
   If one interval ends exactly when another begins, the overlap length should not incorrectly include a positive segment. Sorting events by `(time, delta)` with `-1 < +1` fixes this.

5. **Feasibility is monotone in \(t_2\) for fixed \(t_1\).**
   Increasing \(t_2\) only widens/merges intervals for door 2, never reducing overlap—so once a certain \(t_2\) becomes invalid, all larger \(t_2\) are also invalid (for the same \(t_1\)). This supports a two-pointer scan over candidate lists.

---

## 3) Full solution approach

### Step A: Build candidate sets for \(t_1\) and \(t_2\)

For door 1, include:
\[
\left\lceil \frac{p_{i+1}-p_i}{2} \right\rceil \quad \text{for } i=1..n-1
\]
Similarly for door 2 using \(q\).

Also add a few "guard" values that help corner cases:
- \(1\), \(d\), \(\left\lceil d/2 \right\rceil\)

Then sort and unique the candidate lists.

### Step B: Implement `check(t1, t2)` in \(O(n+m)\)

1. For door 1 times `p` and value `t1`, build merged intervals by scanning:
   - start = `p[i]-t1`, end = `p[i]+t1`
   - while next interval overlaps (`p[i]-t1 <= end`), extend end to `p[i]+t1`
   - emit events `(start,+1)`, `(end,-1)`
2. Same for door 2.
3. Merge the two event arrays (already sorted by time due to sorted input and linear creation), using tie-break "-1 before +1".
4. Track overlap segments (`balance==2`) and ensure their length \(\le d\).
5. Return `(valid, openings)` where openings is number of merged intervals of door1 + door2.

### Step C: Two-pointer optimization to find best (minimum openings)

Let `cand1` be candidate \(t_1\) sorted ascending, `cand2` be candidate \(t_2\) sorted ascending.

- Initialize pointer `j = len(cand2)-1` (largest \(t_2\)).
- For each \(t_1\) in increasing order:
  - while `j >= 0` and `check(t1, cand2[j])` is invalid, decrement `j`
  - if `j >= 0`, then `cand2[j]` is the **largest feasible** \(t_2\) for this \(t_1\), which tends to minimize openings of door 2. Use returned openings to update global best.

If no feasible pair found, print `"No solution"`.

Complexity:
- Candidates: \(O(n+m)\)
- Each `check`: \(O(n+m)\)
- Two-pointer does \(O(|cand1|+|cand2|)=O(n+m)\) checks
- Total: \(O((n+m)^2)\), acceptable for 5000 with careful implementation.

---

## 4) C++ implementation

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

int n, m, d;
vector<int> p, q;

void read() {
    cin >> n >> m >> d;
    p.resize(n);
    q.resize(m);
    cin >> p >> q;
}

pair<bool, int> check(int t1, int t2) {
    vector<pair<int, int>> p_seg, q_seg;

    for(int i = 0; i < n;) {
        int start = p[i] - t1;
        int end = p[i] + t1;
        i++;
        while(i < n && p[i] - t1 <= end) {
            end = p[i] + t1;
            i++;
        }
        p_seg.push_back({start, 1});
        p_seg.push_back({end, -1});
    }

    for(int i = 0; i < m;) {
        int start = q[i] - t2;
        int end = q[i] + t2;
        i++;
        while(i < m && q[i] - t2 <= end) {
            end = q[i] + t2;
            i++;
        }
        q_seg.push_back({start, 1});
        q_seg.push_back({end, -1});
    }

    int cnt = p_seg.size() / 2 + q_seg.size() / 2, balance = 0,
        last_pos = INT_MIN, i = 0, j = 0;

    while(i < (int)p_seg.size() || j < (int)q_seg.size()) {
        int pos, delta;
        if(j >= q_seg.size() ||
           (i < p_seg.size() && (p_seg[i].first < q_seg[j].first ||
                                 (p_seg[i].first == q_seg[j].first &&
                                  p_seg[i].second < q_seg[j].second)))) {
            tie(pos, delta) = p_seg[i++];
        } else {
            tie(pos, delta) = q_seg[j++];
        }

        balance += delta;
        if(balance == 2) {
            last_pos = pos;
        } else {
            if(balance == 1 && last_pos != INT_MIN && pos - last_pos > d) {
                return {false, cnt};
            }
            last_pos = INT_MIN;
        }
    }

    return {true, cnt};
}

void solve() {
    // The first observation to the problem is that it's enough to consider the
    // O(N+M) values for t1 and t2. Then a cubic solution is to test all pairs
    // of candidates and then perform a check(t1, t2). The check can be done in
    // O(N+M) too - we create the segments from p and q, and then have "in" and
    // "out" events (+1 and -1 to a balance). We don't have to sort these events
    // as we have two sorted lists of events which we can just merge.  Then we
    // are interested if there is a segment of length >= d. This can also be
    // done linearly by always maintaining the last point that had balance < 2,
    // and whenever the balance becomes == 2 we look at that last point and
    // check the distance to it. Note that when we merge, we should prioritize
    // the "out" events first.
    // To optimize this further, we can notice that for some t1, we would
    // ideally like to select the largest possible t2 as this will make the
    // number of openings and closings as small as possible. We will also notice
    // that if we have some t1 < t1', then the corresponding optimals are t2 >=
    // t2'. This means that we can do a two pointers like approach that starts
    // from t1=candidates[0] and t2=candidates[-1], and walk down while
    // check(t1, t2) is false. Then we will have at most O(|candidates|)
    // evaluates of check. To make the implementation convenient, we should make
    // check() return the actual answer in terms of #openings too (pair<bool,
    // int>).

    vector<int> candidates_t1, candidates_t2;
    for(int i = 1; i < n; i++) {
        int val = (p[i] - p[i - 1] + 1) / 2;
        candidates_t1.push_back(val);
    }
    for(int i = 1; i < m; i++) {
        int val = (q[i] - q[i - 1] + 1) / 2;
        candidates_t2.push_back(val);
    }

    candidates_t1.push_back(1);
    candidates_t1.push_back(d);
    candidates_t1.push_back((d + 1) / 2);
    candidates_t2.push_back(1);
    candidates_t2.push_back(d);
    candidates_t2.push_back((d + 1) / 2);

    sort(candidates_t1.begin(), candidates_t1.end());
    candidates_t1.erase(
        unique(candidates_t1.begin(), candidates_t1.end()), candidates_t1.end()
    );

    sort(candidates_t2.begin(), candidates_t2.end());
    candidates_t2.erase(
        unique(candidates_t2.begin(), candidates_t2.end()), candidates_t2.end()
    );

    int best_openings = n + m + 1;
    int best_t1 = -1, best_t2 = -1;
    int j = (int)candidates_t2.size() - 1;

    for(int i = 0; i < (int)candidates_t1.size(); i++) {
        bool valid;
        int t1 = candidates_t1[i], openings = -1;

        while(j >= 0) {
            tie(valid, openings) = check(t1, candidates_t2[j]);
            if(valid) {
                break;
            }
            j--;
        }

        if(j >= 0) {
            if(openings < best_openings) {
                best_openings = openings;
                best_t1 = t1;
                best_t2 = candidates_t2[j];
            }
        }
    }

    if(best_t1 == -1) {
        cout << "No solution\n";
    } else {
        cout << best_t1 << " " << best_t2 << "\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation

```python
import sys
from typing import List, Tuple

def build_events(times: List[int], t: int) -> List[Tuple[int, int]]:
    """
    Convert sorted pass times into merged open intervals for parameter t,
    returned as sorted events (pos, delta), delta in {+1, -1}.
    """
    events = []
    i = 0
    n = len(times)

    while i < n:
        start = times[i] - t
        end = times[i] + t
        i += 1

        while i < n and times[i] - t <= end:
            end = times[i] + t
            i += 1

        events.append((start, +1))
        events.append((end, -1))

    return events

def check(p: List[int], q: List[int], d: int, t1: int, t2: int) -> Tuple[bool, int]:
    """
    Returns (is_valid, total_openings) for given (t1, t2).
    is_valid: no overlap segment (both doors open) has length > d.
    total_openings: number of merged segments in door1 + door2.
    """
    pe = build_events(p, t1)
    qe = build_events(q, t2)

    openings = len(pe)//2 + len(qe)//2

    i = j = 0
    balance = 0
    last_pos = None

    while i < len(pe) or j < len(qe):
        if j >= len(qe):
            pos, delta = pe[i]
            i += 1
        elif i >= len(pe):
            pos, delta = qe[j]
            j += 1
        else:
            if pe[i] < qe[j]:
                pos, delta = pe[i]
                i += 1
            else:
                pos, delta = qe[j]
                j += 1

        balance += delta

        if balance == 2:
            last_pos = pos
        else:
            if balance == 1 and last_pos is not None and (pos - last_pos) > d:
                return False, openings
            last_pos = None

    return True, openings

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it)); m = int(next(it)); d = int(next(it))
    p = [int(next(it)) for _ in range(n)]
    q = [int(next(it)) for _ in range(m)]

    cand1 = []
    for i in range(1, n):
        gap = p[i] - p[i-1]
        cand1.append((gap + 1)//2)

    cand2 = []
    for i in range(1, m):
        gap = q[i] - q[i-1]
        cand2.append((gap + 1)//2)

    cand1.extend([1, d, (d + 1)//2])
    cand2.extend([1, d, (d + 1)//2])

    cand1 = sorted(set(cand1))
    cand2 = sorted(set(cand2))

    best_openings = n + m + 1
    best_t1 = best_t2 = None

    j = len(cand2) - 1
    for t1 in cand1:
        while j >= 0:
            ok, openings = check(p, q, d, t1, cand2[j])
            if ok:
                break
            j -= 1

        if j >= 0:
            if openings < best_openings:
                best_openings = openings
                best_t1 = t1
                best_t2 = cand2[j]

    if best_t1 is None:
        sys.stdout.write("No solution\n")
    else:
        sys.stdout.write(f"{best_t1} {best_t2}\n")

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