Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding…

  1. User

    Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.

    The only dry land there is an archipelago of n narrow islands located in a row. For more comfort let's represent them as non-intersecting segments on a straight line: island i has coordinates [li, ri], besides, ri < li + 1 for 1 ≤ i ≤ n - 1.

    To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length a can be placed between the i-th and the (i + 1)-th islads, if there are such coordinates of x and y, that li ≤ x ≤ ri, li + 1 ≤ y ≤ ri + 1 and y - x = a.

    The detective was supplied with m bridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands. Input

    The first line contains integers n (2 ≤ n ≤ 2·105) and m (1 ≤ m ≤ 2·105) — the number of islands and bridges.

    Next n lines each contain two integers li and ri (1 ≤ li ≤ ri ≤ 1018) — the coordinates of the island endpoints.

    The last line contains m integer numbers a1, a2, ..., am (1 ≤ ai ≤ 1018) — the lengths of the bridges that Andrewid got.

    Output

    If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line "No" (without the quotes), otherwise print in the first line "Yes" (without the quotes), and in the second line print n - 1 numbers b1, b2, ..., bn - 1, which mean that between islands i and i + 1 there must be used a bridge number bi.

    If there are multiple correct answers, print any of them. Note that in this problem it is necessary to print "Yes" and "No" in correct case.

    Examples

    Input

    4 4 1 4 7 8 9 10 12 14 4 5 3 8

    Output

    Yes 2 3 1

    Input

    2 2 11 14 17 18 2 9

    Output

    No

    Input

    2 1 1 1 1000000000000000000 1000000000000000000 999999999999999999

    Output

    Yes 1

    Note

    In the first sample test you can, for example, place the second bridge between points 3 and 8, place the third bridge between points 7 and 10 and place the first bridge between points 10 and 14.

    In the second sample test the first bridge is too short and the second bridge is too long, so the solution doesn't exist.

  2. DeepSeek Assistant

    We need to determine if we can assign bridges (each length a_i) to each adjacent island pair such that there exists a point x on left island and y on right island with y - x = a_i. Equivalent to there exists a length a that fits within the "distance range" between islands.

    Let islands i and i+1 have intervals [L_i, R_i] and [L_{i+1}, R_{i+1}]. The possible distances between a point on i and a point on i+1 are from min_dist = L_{i+1} - R_i (since left island ends at R_i, right island starts at L_{i+1}) to max_dist = R_{i+1} - L_i (left start, right end). Actually careful: For any x ∈ [L_i, R_i], y ∈ [L_{i+1}, R_{i+1}], the difference y - x can range from the minimum (when y as small as possible, x as large as possible) i.e., L_{i+1} - R_i to the maximum (y as large as possible, x as small as possible) i.e., R_{i+1} - L_i. Since intervals are non-intersecting and ordered: R_i < L_{i+1}, so min_dist is positive.

    Thus each gap i requires a bridge length a that lies in the interval [min_i, max_i], where min_i = L_{i+1} - R_i, max_i = R_{i+1} - L_i.

    So we have n-1 intervals for gaps. And we have m bridges with lengths a_j. Each bridge can be used at most once. We need to assign distinct bridges to each gap such that the assigned bridge length is within the gap's interval.

    We need to output any valid assignment (mapping from gaps to bridge indices) or "No".

    This is a classic matching problem: assign bridges to intervals. Since both n and m up to 2e5, we need an efficient greedy algorithm if the intervals are sorted appropriately. This looks like an interval scheduling / assignment problem: given intervals (min_i, max_i) sorted by something, and a multiset of values, assign each interval a value that lies within it, each value used once. This is akin to checking if we can assign given tasks with required resource lengths. Usually we sort intervals by their max (or min) and assign the smallest possible bridge that fits.

    But careful: We have intervals (min_i, max_i) representing allowed lengths. We need to assign each interval a distinct value from set A (multiset of bridge lengths). This is like checking if we can assign each interval a value. A known greedy solution: sort intervals by their upper bound (max_i) ascending, and for each interval in that order, assign the smallest available bridge that is >= min_i (and <= max_i obviously). If none, then impossible.

    Proof: If we consider intervals sorted by max, then picking the smallest possible bridge that fits ensures we don't waste larger bridges that may be needed by later intervals with tighter upper bounds. This is typical for matching points to intervals (or "interval stabbing" but reversed: we have points and intervals). Actually standard problem: Given a set of intervals and a set of points, assign each interval a point, each point at most one interval, point must lie in interval. The greedy algorithm (sort intervals by right endpoint, assign the smallest point that fits) works.

    But here we have intervals that are arbitrary and points (bridge lengths) with duplicates allowed? But each point is a distinct bridge with length. Since lengths can repeat, we treat each bridge separately. So we have multiset of values.

    Thus we can do:

    • Compute for each gap i (1 to n-1): min_i = L_{i+1} - R_i, max_i = R_{i+1} - L_i.
    • Sort gaps by max_i ascending, breaking ties by min_i perhaps.
    • Sort bridges array.
    • Use a multiset (or priority queue) to keep available bridges? Actually we can iterate over gaps sorted by max, and maintain a pointer or use a multiset to choose the smallest bridge >= min_i.

    Given both n,m up to 2e5, we can sort bridges and then for each gap, binary search among remaining bridges? But removal is tricky. However the greedy approach can be implemented by using a multiset (like balanced BST) of bridges, and for each gap (sorted by max), find the smallest bridge >= min_i. If that bridge <= max_i, assign it and remove from set. Else impossible.

    Since m up to 2e5, multiset (C++ set with duplicates) or TreeSet works O((n+m) log m). That should be fine.

    But careful about duplicates: we need to store multiple copies. In C++ we can use multiset. In Java, we can use TreeMap with counts, or use a sorted list and pointer? But the pointer method is not straightforward because we need to remove specific element. However there is an alternative: sort gaps by max, sort bridges, then for each gap, we can use a pointer to iterate over bridges and maintain a data structure? Actually there is known greedy: sort gaps by min? Let's think.

    Standard approach for "assign each interval a point" is: sort intervals by right endpoint; sort points; iterate intervals, for each interval, take the smallest point >= left endpoint, and if <= right, assign; then move pointer? But the point must be removed, so the pointer may need to skip assigned point. But we need to ensure we don't assign same point twice. If we sort points ascending, we can use a pointer that only moves forward: For each interval (sorted by right), we want the smallest available point that is >= min_i. Among all points not yet used, the smallest such is simply the first point in the sorted list that is >= min_i and hasn't been used. Since we are processing intervals in order of increasing max, and we always take the smallest eligible point, that point will be taken and we can mark it used (or increment pointer). However is it safe to just increment pointer when we assign? Not exactly: Suppose we have points sorted: 5,6,7. Intervals: (min=5,max=6) and (min=6,max=6). Sorted by max: first interval (5,6), second (6,6). For first interval we take smallest >=5, which is 5, assign, pointer moves to 6. For second interval, we need smallest >=6, and we have point 6 available (since pointer points to 6). 6 <=6 so assign. Works.

    But consider intervals sorted by max: (min=5,max=7), (min=6,max=6). Points: 6,7. First interval (5,7): smallest >=5 is 6, assign, pointer moves to 7. Second interval (6,6): smallest >=6 is 7, but 7 >6, fails. However there exists a solution: assign 7 to first interval, 6 to second. Our greedy failed because we took the smallest possible (6) for first interval, leaving 7 for second which is too large. But is our interval order correct? Since we sort by max, the first interval has max=7, second has max=6 (tighter). So we should process second before first because it has smaller max. Wait, the order must be by max ascending. So intervals: second (6,6) max=6, first (5,7) max=7. So process second first: smallest >=6 is 6, assign, pointer moves to 7. Then first: smallest >=5 is 7, 7<=7 works. So ordering by max works.

    Now consider a case: intervals: (min=1,max=2), (min=2,max=3). Points: 2,2. Greedy sorted by max: first (1,2) max=2, second (2,3) max=3. For first, smallest >=1 is 2 (first 2), assign, pointer moves to next 2. For second, smallest >=2 is 2 (since pointer points to second 2), assign, works. Good.

    But what if intervals have same max? Ordering by min or any works. Usually the greedy is: sort intervals by right endpoint ascending, and sort points. Then iterate intervals, and for each interval, find the smallest point >= left endpoint (using pointer). But careful: Because points are sorted, we can use a pointer that always moves forward; however we need to ensure that the point we pick is not less than left, but also not greater than right. The algorithm:

    Sort intervals by max (right). Sort points. Maintain an index i into points (starting at 0). For each interval (L,R) in sorted order: While i < m and points[i] < L: i++ (skip points that are too small for any later interval? Actually if a point is less than L, it might be used for previous intervals? But since intervals are sorted by max, and L may be larger? Wait, we cannot discard points that are less than L because they might be needed for intervals with smaller L? Actually consider intervals sorted by max: later intervals have larger or equal max, but their L could be smaller. However points that are less than current L are too small for the current interval. Could they be needed for a later interval? Later interval has larger max, but its L could be even larger (or smaller). For instance, intervals: (L=10,R=10) and (L=1,R=100). Sorted by max: first (10,10) then (1,100). Suppose points: 5,10. For first interval (10,10): we need a point >=10 and <=10. points[i] initially 5 which is <10, so we skip? But we might need that 5 for the later interval (1,100). However if we skip 5 (i++) and move to 10, assign 10 to first interval, then later interval (1,100) we have no points left (since i==m). But we could assign 5 to second interval, 10 to first, which works. But our algorithm would skip 5? Let's see: Starting i=0, first interval (10,10). While points[i] < L (10) increment i: points[0]=5 <10 => i=1; points[1]=10 not <10, stop. Then check if points[i] <= R (10) => yes assign, i++ (now i=2). For second interval, i=2 == m, fail. So algorithm fails. But should we have not skipped the 5? Actually the point 5 cannot be used for the first interval because it's less than L. However it might be used for later intervals, but since we are processing intervals in order of increasing max, we should not discard points that are too small for the current interval, because they could be used for later intervals that have smaller L. However later intervals have larger max, but L might be smaller. In the example, later interval has L=1 which is smaller than 5. So 5 is >=1 and <=100, so it is eligible. So discarding points that are too small for current interval is dangerous. The standard greedy for "assign each interval a point" typically sorts intervals by right endpoint and then iterates over points sorted, but the typical algorithm is: For each point, assign it to the interval with the smallest right endpoint that it can satisfy. That is a different perspective: sort points, and for each point, assign to the interval (that hasn't been assigned yet) with the smallest max that is >= point and also point >= min. This is also a known greedy: sort points ascending, maintain a priority queue of intervals that have min <= current point, sorted by max. Then for each point, assign to the interval with smallest max. This is more robust.

    Alternatively, we can use the interval sorted by max and maintain a multiset of bridges (sorted) and for each interval, choose the smallest bridge >= min_i. This avoids the issue of discarding too-small bridges because we are not forced to increment pointer over all smaller bridges; we can pick and remove from multiset. So using a BST is safer.

    But we can also implement the pointer approach if we sort intervals by min? Let's think of another approach: sort intervals by min (or something) and use a pointer over bridges. There's known algorithm: sort intervals by left endpoint, sort bridges. Use a priority queue for intervals that are currently "open", i.e., intervals whose left <= current bridge. But we need to assign bridges to intervals. Typically, for "assign tasks to workers" or "matching intervals to points", the algorithm that works is:

    • Sort intervals by left endpoint.
    • Sort bridges (points).
    • Use a min-heap of interval right endpoints.
    • Iterate through bridges in increasing order. For each bridge value a:
      • Add all intervals where min_i <= a (i.e., intervals that can potentially use this bridge) into the heap keyed by max_i.
      • Then, from the heap, pop the interval with the smallest max_i (since it's the most constrained) and assign the current bridge to it, provided that a <= max_i. If a > max_i, then that interval cannot be satisfied by any later bridge (since later bridges are larger), so it's impossible.

    This greedy is standard: process bridges in increasing order, assign to the interval with the smallest max among those that have min <= current bridge. This ensures we satisfy the tightest intervals first. Complexity O((n+m) log n) if we manage intervals well.

    Alternatively, we can process intervals sorted by max, and for each interval pick the smallest bridge >= min_i using a multiset. That's also O((n+m) log m). Both are fine.

    Given constraints, I'll implement the interval-sorted-by-max with multiset of bridges, because it's straightforward: sort gaps by max_i ascending, and for each gap, find in a multiset (like TreeMap of values to count) the smallest bridge >= min_i. If that bridge <= max_i, assign it and remove; else impossible.

    But careful: the multiset must support lower_bound (ceiling) operation. In Java, we can use TreeMap with counts; we need to retrieve the smallest key >= min_i, and ensure it's <= max_i. Or we can use TreeSet but duplicates need to be handled: we could store all bridges in a list, sort, and then use a boolean array to mark used, and for each gap, binary search for the first unused index with value >= min_i and <= max_i. However that would be O(m log m + n log m) but might degrade to O(n*m) if we skip many used ones? Actually we can use a binary search combined with a "next available" pointer via union-find or something. But simpler: use TreeMap.

    So steps:

    • Read n,m.
    • Read islands: long[] l, r (index 1..n)
    • For i = 1 to n-1: min_i = l[i+1] - r[i] max_i = r[i+1] - l[i] store as Gap objects with index i, min, max.
    • Read bridges array of length m: long[] a.
    • Create TreeMap<Long, Integer> multiset: for each a, count++.
    • Sort gaps by max ascending (if tie, by min ascending? But not crucial). But careful: In case of equal max, if we sort by min as well, it's fine.
    • For each gap in sorted order:
      • Find the smallest bridge >= min. In TreeMap, use ceilingKey(min). Actually we need key >= min. So map.ceilingKey(min).
      • If key is null or key > max, then output "No".
      • Else assign: result[gap.index] = something. But we need to output bridge indices (original positions). So we need to keep track of which bridge is which. So we need to know the index of the assigned bridge. Using a multiset that only stores lengths loses index information. So we need to store bridges along with their original indices. We can do: create an array of Bridge objects with (length, originalIndex). Sort bridges by length. Then we can use a TreeSet with comparator by length (and index to break ties), and remove. But duplicates exist: if multiple bridges have same length, we need to keep them separate. So we can sort bridges array, and then for each gap, we need to find the smallest bridge (by length) that is >= min_i and <= max_i, and not used. That's like picking the first bridge in sorted list that meets condition, but we need to skip used ones.

    We can do: sort bridges by length, and also store original indices. Then for each gap (sorted by max), we will perform a binary search on the sorted bridges to find the first index with length >= min_i. Then we need to find the first such bridge that is not used and length <= max_i. We can use a data structure to skip used indices, like a TreeSet of available indices, or a next array (union-find style) that points to the next unused index after a given one. Because we will assign bridges in order, and once a bridge is used, we want to skip it. We can implement a DSU "next" array: parent[i] = next unused index after i, or i itself if unused. Initially each i points to itself. When we take bridge i, we set parent[i] = i+1 (or union with next). Then to find the first unused index >= lower bound, we binary search to get the first index idx such that bridge[idx].length >= min_i. Then we find the root of idx in DSU (which gives the first unused index >= idx). If that index is beyond array or length > max_i, fail. Else use that bridge. This is O((n+m) α(m)) after sorting.

    But we need to be careful with binary search: we need to find the first bridge length >= min_i. Since bridges are sorted by length, we can use Arrays.binarySearch on the lengths array (or custom). Then we find the index lb = lower_bound (first with length >= min_i). That's O(log m). Then we find root of lb using DSU. If root < m and bridge[root].length <= max_i, assign and union root with root+1. If root == m or bridge[root].length > max_i, then fail.

    But we also need to check that bridge[root].length >= min_i; it will be because root is >= lb, and lb is first >= min_i, so root's length >= min_i. So condition is just <= max_i.

    Potential problem: After we union root with root+1, the DSU find for later queries will skip used ones.

    We need to ensure that the DSU find operation is amortized near constant.

    Implementation details:

    • Create array bridges of length m: each entry is a pair (long len, int idx). Sort by len ascending.
    • Build an array lengths[] = bridges[i].len for binary search.
    • Initialize parent array for DSU: parent[i] = i; size or not needed.
    • Find function: if parent[x] == x, return x; else parent[x] = find(parent[x]); return parent[x].
    • Union: when we use index i, we set parent[i] = i+1; But careful: we need to union with next index. However find will handle path compression. But typical "next available" DSU: We initialize parent[i] = i. When we use i, we set parent[i] = i+1 (or union(i, i+1)). Then find(i) will return the next available index. However we also need to ensure that parent[m] (beyond last) maybe set to m (or -1). We can just handle boundary.

    We can implement: after sorting, we have m bridges. We'll have an array next = new int[m+1]; (or parent). Typically we do:

    int[] parent = new int[m+1]; for (int i=0; i<=m; i++) parent[i] = i;

    Find(i) returns the smallest index >= i that is not used. When we mark index i as used, we union i with i+1: parent[i] = i+1; (or set parent[i]=find(i+1)). That will effectively set the representative to the next unused.

    Then to get first unused index >= lb, we do f = find(lb). If f == m, it means no unused index >= lb. Because we set parent[m] = m (sentinel). So if f == m, fail.

    Otherwise we use bridges[f], check if its length <= max_i; if yes, assign and union f with f+1; else fail.

    But careful: In the find function, we need to compress paths: if parent[x] == x, return x; else parent[x] = find(parent[x]); return parent[x]. Since parent[x] may be > x (like x+1). That's fine.

    But we also need to handle that parent[m] is always m (unused sentinel). However if we try to find lb where lb=m, it's ok.

    Now, is the greedy algorithm (sort gaps by max ascending and assign the smallest bridge >= min_i) correct? Let's double-check with some edge cases.

    We need to ensure that sorting by max ascending and picking the smallest available bridge >= min_i works. Is it always optimal? I recall that for the problem of matching points to intervals, the greedy that sorts intervals by right endpoint and picks the earliest point that lies in the interval (i.e., the smallest point >= left) is optimal if we treat points as multiset and we can choose any point. But the example earlier where sorting by max works, but we also considered the issue with skipping small points when using pointer, but with DSU we are not skipping; we are directly picking the smallest unused bridge >= min_i. That is exactly the same as using a multiset that supports removal. So that algorithm is known to be optimal. Let's prove: Suppose we have intervals sorted by max (R). We process in increasing R. For the current interval (L,R), if there is any solution that uses some set of bridges, we claim that we can replace the bridge assigned to this interval with the smallest bridge that is >= L and <= R, without harming future intervals. Because future intervals have larger or equal R (since sorted), so they can accept larger bridges. The smallest bridge that fits the current interval is the best to preserve flexibility. This is standard exchange argument.

    But consider the case where there are multiple intervals with same max? Doesn't matter.

    Thus algorithm is correct.

    Edge cases: The intervals might be large (up to 1e18). Bridge lengths up to 1e18. Use long.

    Now about output: We need to output bridge indices (1-indexed) for each gap in original order (1..n-1). So we store an array assign of size n-1 (int). For each gap processed, we know its original index (since we stored it). After assignment, we fill assign[gap.idx] = bridges[f].originalIndex (1-indexed). Then after all gaps processed, output "Yes" and then assign list.

    If any gap fails, output "No".

    Complexities: Sorting gaps O(n log n), sorting bridges O(m log m). Then for each gap, binary search O(log m) and DSU find O(α(m)). So overall O((n+m) log (n+m)). Good.

    Now we must be careful about the DSU find when we call find(lb) and then later we might need to find again for the same lb after some removals. That's fine.

    Implementation steps in detail:

    1. Read n,m.

    2. long[] l = new long[n]; long[] r = new long[n]; for i=0..n-1: read li, ri.

    3. Create Gap[] gaps = new Gap[n-1]; for i=0..n-2: min = l[i+1] - r[i]; max = r[i+1] - l[i]; gaps[i] = new Gap(i, min, max). Note: i is index of left island (0-indexed for gap). We'll output for gap i (between i and i+1) assignment b_i (1-indexed). So we need mapping: gap index from 0..n-2.

    4. Sort gaps by max ascending (if equal, by min ascending maybe, but not necessary).

    5. Read m bridges: long[] a = new long[m]; for i=0..m-1: a[i] = nextLong().

    6. Create Bridge[] bridges = new Bridge[m]; for i=0..m-1: bridges[i] = new Bridge(a[i], i+1) (original index 1-indexed). Sort bridges by length ascending.

    7. Extract long[] lengths = new long[m]; for i=0..m-1: lengths[i] = bridges[i].len.

    8. Initialize DSU: parent = new int[m+1]; for i=0; i<=m; i++) parent[i] = i; // note size m+1 to handle sentinel at m.

    9. Process each gap in sorted order:

      • long min = gap.min; long max = gap.max;
      • Find lower bound index: lb = lowerBound(lengths, min). (first index with lengths[lb] >= min). If min > lengths[m-1], then lb = m (no such).
      • int idx = find(lb); // find first unused index >= lb.
      • if idx == m: fail.
      • if bridges[idx].len > max: fail.
      • assign[gap.idx] = bridges[idx].origIdx;
      • // mark used: union idx with idx+1. parent[idx] = find(idx+1); // or set parent[idx]=idx+1? Actually to union we set parent[idx]=find(idx+1) for DSU path compression. But we must also consider that find(idx) will no longer be used; we set parent[idx] to the representative of idx+1. That's fine.
      • However note: if idx == lb exactly, then after union, later find(lb) will return find(parent[lb]) which is next available.
      • If idx > lb, then it's fine.
    10. After processing all gaps, output "Yes" and then the assignment array for i=0..n-2 (space separated).

    Edge Cases:

    • It's possible that min_i > max_i? Since l[i+1] > r[i] (non overlapping) so min_i = l[i+1]-r[i] > 0, and max_i = r[i+1]-l[i] > min_i? Not necessarily: Consider island i: [1,2], island i+1: [3,4]. min = 3-2=1, max=4-1=3. So max>=min. Actually r[i+1] - l[i] >= l[i+1] - r[i] because r[i+1] >= l[i+1] and l[i] <= r[i], so indeed max_i >= min_i always. So interval is valid.

    • Bridges lengths may be duplicate.

    • There may be more bridges than gaps; we only need n-1 bridges; extra are ignored.

    • If m < n-1: obviously impossible, we can check early: if m < n-1: print No.

    But algorithm will also detect because we need to assign n-1 bridges and we have only m; eventually we will run out.

    Now ensure the DSU find function works for index m. We'll have parent[m]=m. So find(m) returns m.

    Now lowerBound implementation: returns first index where lengths[i] >= key, else returns m.

    Now test with given examples.

    Example 1:

    n=4,m=4 Islands: [1,4], [7,8], [9,10], [12,14] Compute gaps: gap0 (1-2): min = 7-4=3, max = 8-1=7? Actually 8-1=7 => interval [3,7] gap1 (2-3): min = 9-8=1, max = 10-7=3 => [1,3] gap2 (3-4): min = 12-10=2, max = 14-9=5 => [2,5] Bridges: [4,5,3,8] sorted: [3,4,5,8] with indices: 3->3? Actually original: a1=4, a2=5, a3=3, a4=8. Sorted: (3,3), (4,1), (5,2), (8,4). Now gaps sorted by max: gap1: [1,3] max=3 gap0: [3,7] max=7 gap2: [2,5] max=5 -> Wait max=5? Actually gap2 max=5, gap0 max=7, gap1 max=3. So sorted by max: gap1 (max=3), gap2 (max=5), gap0 (max=7). (If tie? none) Process:

    • gap1: min=1, max=3. lowerBound >=1: first index 0 (len=3). find(0)=0 (unused). 3 <=3 -> assign bridge idx0 (orig idx 3). mark used (parent[0]=find(1)=1)
    • gap2: min=2, max=5. lowerBound >=2: first index? lengths: [3,4,5,8] -> index0 (len=3) but 3>=2. find(0) now: parent[0]=1, so find(0) calls find(1) -> 1 (since parent[1]=1 currently). idx=1 (len=4). 4 <=5 -> assign bridge idx1 (orig idx 1). mark used: parent[1]=find(2)=2.
    • gap0: min=3, max=7. lowerBound >=3: index0 (len=3). find(0) -> parent[0]=1, find(1) now parent[1]=2, find(2)=2 (since parent[2]=2). idx=2 (len=5). 5 <=7 -> assign bridge idx2 (orig idx 2). done. Assignment: gap0 (between 1-2) gets bridge 2 (orig idx 2). gap1 (2-3) gets bridge 3 (orig idx 3). gap2 (3-4) gets bridge 1 (orig idx 1). Output order: b1 b2 b3 = 2 3 1? Actually gap0 is between island 1-2, gap1 between 2-3, gap2 between 3-4. We got assign[0]=2, assign[1]=3, assign[2]=1. That's "2 3 1". matches sample output "2 3 1". Good.

    Example 2: n=2,m=2 Islands: [11,14], [17,18] gap0: min=17-14=3, max=18-11=7 => [3,7] Bridges: [2,9] sorted [2,9] Sorted gaps: only one. gap0: min=3, max=7. lowerBound>=3: first index? lengths: [2,9] -> index0 (len=2) <3 so index1 (len=9). lb=1. find(1)=1 (len=9). 9 >7 -> fail. So No. Good.

    Example 3: n=2,m=1 Islands: [1,1], [1e18,1e18] gap0: min = 1e18 - 1 = 999999999999999999? Actually 1e18 - 1 = 999...9 (18 digits? Let's compute: 10^18 - 1 = 999...9). But l2 = 1e18, r1=1, so min = 1e18 - 1 = 999...9, max = 1e18 - 1 = same? Actually max = r2 - l1 = 1e18 - 1 = 999...9. So interval [999...9, 999...9]. Bridge: 999...9. Sorted: that one. lowerBound >= min: index0. find(0)=0, len <= max? equal so assign. Yes. Output 1. Works.

    Thus algorithm passes examples.

    Now we need to consider potential pitfalls:

    • The DSU union: we set parent[idx] = find(idx+1). But we must ensure we never call find on idx+1 when idx+1 == m, which returns m (since parent[m]=m). That's fine.
    • Need to watch for long overflow? All values up to 1e18, but subtraction of two up to 1e18 could be up to 1e18, but still within long (since 1e18 fits in 2^63-1 ~9.22e18). So safe.
    • We must ensure that when we compute min and max, we use long.

    Now complexity: Sorting O(n log n + m log m). DSU operations O(n * α(m)). Binary search O(log m) per gap.

    Now confirm that this greedy is indeed correct in all cases. Let's attempt to construct a counterexample.

    Suppose we have intervals sorted by max:

    gap A: [1,100] gap B: [50,60] Bridges: 55, 70.

    Sorted by max: B (max=60) then A (max=100). Process B: min=50, max=60. smallest bridge >=50 is 55, assign 55. Then A: min=1, max=100, smallest bridge >=1 is 70, assign 70. Works. If we had reversed: 70, 55 sorted as 55,70 still same.

    Suppose intervals: A: [1,10], B: [5,6], C: [7,8]. Bridges: 6,7,9. Sorted by max: B max=6, C max=8, A max=10. Process B: min=5 -> smallest >=5 is 6, assign 6. C: min=7 -> smallest >=7 is 7, assign 7. A: min=1 -> smallest >=1 is 9, assign 9. Works.

    Now consider intervals: A: [1,5], B: [2,6], C: [3,7]. Bridges: 4,5,6. Sorted by max: A max=5, B max=6, C max=7. A: min=1 -> smallest >=1 is 4, assign 4 (since 4 <=5) OK. B: min=2 -> smallest >=2 is 5 (since 4 used), assign 5 (<=6) OK. C: min=3 -> smallest >=3 is 6 (since 5 used), assign 6 (<=7) OK.

    What if we had bridges: 5,6,7? Sorted same, would assign 5 to A? Actually A: min=1, smallest >=1 is 5 (since 5,6,7) assign 5, B: min=2 -> smallest >=2 is 6 assign 6, C: min=3 -> smallest >=3 is 7 assign 7. Works.

    Now what if we have intervals: A: [1,2], B: [1,3], C: [2,3]. Bridges: 2,2,3. Sorted by max: A max=2, C max=3? Actually A max=2, B max=3, C max=3? Let's assign: A: [1,2], B: [1,3], C: [2,3]. Sorted by max: A then B then C (since B and C both max=3; but order among them? Possibly B then C or C then B. Let's test both. Case 1: order A, B, C. A: min=1 -> smallest >=1 is 2 (first 2) assign 2. B: min=1 -> smallest >=1 is 2 (second 2) assign 2. C: min=2 -> smallest >=2 is 3 (since 2s used) assign 3. Works. Case 2: order A, C, B. A: assign first 2. C: min=2 -> smallest >=2 is 2 (second 2) assign 2 (but 2 <=3 OK). B: min=1 -> smallest >=1 is 3 assign 3 (<=3 OK). Works.

    So far okay.

    Now consider a case where sorting by max and choosing smallest bridge might fail if we choose a bridge that is too small for a later interval that also needs a small bridge? But later intervals have larger max, so they can accept larger bridges. The only risk is if later interval has a larger min than the chosen bridge? Actually if later interval has larger min, then the chosen bridge might be less than its min. But we always pick the smallest bridge >= current min. That bridge may be less than later interval's min if later interval has higher min? But later interval could have higher min, but if we assign a bridge that is small but still >= current min, it might be the only bridge that could satisfy a later interval with a high min? However later intervals have larger max but could have min larger or smaller. Let's attempt to construct a failure.

    We need a scenario where there are two intervals I and J with I.max < J.max, and we have two bridges x<y. Suppose I has interval [L1,R1], J has [L2,R2] with R1 < R2. Suppose the only way to assign is: assign y to I and x to J. But our greedy (assign smallest bridge >= L1 to I) would assign x to I (since x >= L1) and then y to J (if y >= L2 and <= R2). If that works, then it's fine. But if assigning x to I leaves no bridge for J because J requires a bridge <= R2 but also >= L2, and maybe only y fits J? Actually if J requires a bridge <= R2, and both x and y are <= R2, and both >= L2? Or maybe x < L2 so x cannot be assigned to J. Then if we assign x to I, we might be forced to assign y to J. That could be okay if y fits J. The problematic case is when y does not fit J (y > R2 or y < L2). But if y does not fit J, then the only feasible assignment might be y to I and x to J. For that to be necessary, we need that I can accept y (y <= R1) and J can accept x (x <= R2 and x >= L2). And also I can accept x? Possibly x also acceptable for I? If x is acceptable for I, then our greedy would assign x to I, leaving y for J, but y might not be acceptable for J. So we need:

    • I: [L1,R1]
    • J: [L2,R2] with R1 < R2 (so I is processed first)
    • Bridges: x < y
    • Conditions:
      • x is acceptable for I: L1 <= x <= R1
      • y is acceptable for I: L1 <= y <= R1? If y also acceptable for I, then both are acceptable, but greedy picks the smaller x, which might be okay if J can accept y. But if J cannot accept y, then greedy fails while optimal would assign y to I and x to J. But does J accept x? x must satisfy L2 <= x <= R2. And y must not be acceptable for J: either y < L2 or y > R2. Since y > x and R1 < R2, it's possible that y > R2? But if y > R2, and y <= R1 (since acceptable for I) then R1 >= y > R2, which contradicts R1 < R2. So y cannot be > R2 if y <= R1 and R1 < R2. So y > R2 is impossible because R1 < R2, and y <= R1, so y <= R1 < R2, so y <= R2 automatically. So y cannot be > R2. The other possibility: y < L2. Since y > x, and x >= L2? For J to accept x, we need x >= L2. If x >= L2, then y > x >= L2, so y >= L2, so y >= L2. So y cannot be < L2. So it seems that if both x and y are acceptable for I, and J accepts x, then J also automatically accepts y? Let's verify: We have x and y such that L1 <= x < y <= R1. Also we need L2 <= x <= R2 for J to accept x. Since y <= R1 and R1 < R2, we have y <= R1 < R2, so y <= R2. Also y > x >= L2, so y >= L2 (since y > x and x >= L2, so y > L2, but if L2 is integer, still >= L2). So indeed y also lies in [L2,R2]. So J would also accept y. So the case where only x works for J but y does not cannot happen if both are in I's interval and I.max < J.max. Because J's max is larger, and I's max is smaller, so any value <= R1 is <= R2. Also if J's min is <= x, then also <= y? Actually J's min could be > y? That would require L2 > y. But if L2 > y, then J cannot accept x because x < y < L2, so x < L2, so x not acceptable. So if J accepts x, then L2 <= x, and since y > x, we have y > L2? Actually y could still be less than L2 if L2 is between x and y? But if y > x and L2 > y, then L2 > y > x, so L2 > x, so x < L2, so x not acceptable. Contradiction. So J accepting x implies L2 <= x, so L2 <= x < y, thus L2 < y, so y > L2, but maybe L2 <= y? Since y > x and L2 <= x, we have L2 <= x < y, so L2 < y, but is it possible that L2 > y? No because L2 <= x < y, so L2 < y. So L2 <= y? Actually if L2 <= x, then L2 <= x < y, so L2 < y, but it could be that L2 is less than y but still y might be less than L2? That's impossible. So y > L2. So y >= L2? Since L2 is integer? But intervals are continuous, but we treat integer points? Actually coordinates can be any integer, but bridges length are integer; we need existence of points x and y (not necessarily integers? The coordinates li, ri are integers, but x and y can be any real? The problem states coordinates x and y such that li ≤ x ≤ ri, li+1 ≤ y ≤ ri+1 and y - x = a. Since li, ri are integers, a is integer, but x and y could be reals? Actually coordinates are integers, but they are endpoints; points can be anywhere in the interval, so x and y can be any real numbers? The problem statement says "such coordinates of x and y" implying they are coordinates, likely they can be any real numbers. However bridge length a is integer, but x and y can be real. So condition is: there exist reals x in [L_i, R_i] and y in [L_{i+1}, R_{i+1}] such that y - x = a. That's equivalent to a belonging to the interval [L_{i+1} - R_i, R_{i+1} - L_i] (since we can choose x and y appropriately). Because for any a in that closed interval, we can set x appropriately: we need y = x + a; constraints: L_i ≤ x ≤ R_i, and L_{i+1} ≤ x + a ≤ R_{i+1}. So we need x such that max(L_i, L_{i+1} - a) ≤ x ≤ min(R_i, R_{i+1} - a). Existence requires max(L_i, L_{i+1} - a) ≤ min(R_i, R_{i+1} - a). This is equivalent to a ∈ [L_{i+1} - R_i, R_{i+1} - L_i]. So indeed a can be any real number in that interval? But a is integer given. So we treat it as a real interval, and integer a must lie in it. Since the endpoints are integers (li, ri are integers), the interval endpoints are integers as well? L_{i+1} - R_i and R_{i+1} - L_i are differences of integers, thus integers. So the interval is integer. So it's a closed discrete integer interval. So our analysis stands.

    Thus the earlier reasoning about intervals and integer lengths is fine.

    Now the greedy argument: Since intervals are closed and values integer, the greedy works.

    Thus the algorithm is correct.

    But to be thorough, let's consider the potential counterexample from the pointer method: intervals sorted by max, but using multiset eliminates the skipping issue. So we are safe.

    Now implement.

    We'll need:

    • class Gap implements Comparable or use Comparator: store idx, min, max.

    • sort gaps: Arrays.sort(gaps, Comparator.comparingLong(Gap::getMax).thenComparingLong(Gap::getMin));

    • class Bridge implements Comparable (store len, origIdx) and sort by len.

    • DSU: parent array int[m+1]; find function iterative or recursive with path compression.

    • lowerBound: standard binary search.

    Now memory: up to 200k, fine.

    Now check for early exit if m < n-1: print "No".

    But note: if m >= n-1, we may still fail.

    Implementation details in Java:

    We'll use fast input (BufferedReader, StringTokenizer) due to large input.

    Now, be careful about 64-bit: use long.

    Now code:

    import java.util.*;
    import java.io.*;
    
    public class Bridges {
    
        static class Gap {
            int idx;
            long min, max;
            Gap(int i, long mn, long mx) { idx = i; min = mn; max = mx; }
        }
    
        static class Bridge implements Comparable<Bridge> {
            long len;
            int idx;
            Bridge(long l, int i) { len = l; idx = i; }
            public int compareTo(Bridge o) {
                if (len != o.len) return Long.compare(len, o.len);
                return Integer.compare(idx, o.idx);
            }
        }
    
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter pw = new PrintWriter(System.out);
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            long[] l = new long[n];
            long[] r = new long[n];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                l[i] = Long.parseLong(st.nextToken());
                r[i] = Long.parseLong(st.nextToken());
            }
            Gap[] gaps = new Gap[n-1];
            for (int i = 0; i < n-1; i++) {
                long min = l[i+1] - r[i];
                long max = r[i+1] - l[i];
                gaps[i] = new Gap(i, min, max);
            }
            // read bridges
            st = new StringTokenizer(br.readLine());
            Bridge[] bridges = new Bridge[m];
            for (int i = 0; i < m; i++) {
                long a = Long.parseLong(st.nextToken());
                bridges[i] = new Bridge(a, i+1); // 1-indexed
            }
            if (m < n-1) {
                pw.println("No");
                pw.close();
                return;
            }
            // sort gaps by max then min
            Arrays.sort(gaps, (g1, g2) -> {
                if (g1.max != g2.max) return Long.compare(g1.max, g2.max);
                return Long.compare(g1.min, g2.min);
            });
            // sort bridges by length
            Arrays.sort(bridges);
            long[] lengths = new long[m];
            for (int i = 0; i < m; i++) lengths[i] = bridges[i].len;
    
            // DSU next array
            int[] parent = new int[m+1];
            for (int i = 0; i <= m; i++) parent[i] = i;
    
            // find with path compression
            // find smallest index >= i that is not used
            // iterative find to avoid recursion depth? but m up to 200k, recursion okay.
            // We'll implement recursive for simplicity, but careful about stack depth? 200k recursion could overflow if chain long, but path compression will reduce depth; but recursion might still cause deep recursion in worst-case if we call find many times on the same index that is already used? Actually each call will compress, so depth is limited. But we can use iterative.
            // Use iterative:
            // int find(int x) {
            //     while (parent[x] != x) {
            //         parent[x] = parent[parent[x]]; // path compression step
            //         x = parent[x];
            //     }
            //     return x;
            // }
            // But careful: parent[x] may point to a higher index; we want to compress.
    
            // We'll implement iterative find with path compression.
    
            int[] assign = new int[n-1];
            boolean possible = true;
            for (Gap gap : gaps) {
                long min = gap.min;
                long max = gap.max;
                // lower bound on lengths
                int lb = lowerBound(lengths, min);
                int idx = find(parent, lb);
                if (idx == m || bridges[idx].len > max) {
                    possible = false;
                    break;
                }
                assign[gap.idx] = bridges[idx].idx;
                // mark as used: union idx with idx+1
                parent[idx] = find(parent, idx+1);
            }
            if (possible) {
                pw.println("Yes");
                for (int i = 0; i < n-1; i++) {
                    if (i > 0) pw.print(" ");
                    pw.print(assign[i]);
                }
                pw.println();
            } else {
                pw.println("No");
            }
            pw.close();
        }
    
        static int lowerBound(long[] arr, long key) {
            int lo = 0, hi = arr.length;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (arr[mid] < key) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            return lo;
        }
    
        static int find(int[] parent, int x) {
            // iterative with path compression
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
    }
    

    We must be careful: In find, we might call on x=m, which has parent[m]=m, returns m.

    But when we do parent[idx] = find(parent, idx+1); this union sets parent[idx] to the root of idx+1. That works.

    Now check for correctness of union: after marking idx as used, we want that subsequent find(lb) will skip idx. Since we set parent[idx] to the root of idx+1, find(lb) for any lb <= idx will eventually go to idx and then follow to idx+1, etc.

    However, we need to ensure that path compression in find works correctly. Our find function as written compresses paths by setting parent[x] = parent[parent[x]] during traversal. But typical iterative find with path compression:

    int find(int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }
    

    But simpler: we can use recursion:

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    

    Since recursion depth at most O(α) times? Actually worst-case depth could be up to m if we don't compress, but each find after union compresses. However recursion might cause stack overflow for deep chains? But m=200k, depth could be 200k in worst-case if we don't compress. Our union sets parent[idx]=find(idx+1). If we start with parent all self, and we mark used in order (maybe not sequential). But we might get chain like parent[0]=1, parent[1]=2, parent[2]=3,... after using first few sequentially. Then find(0) would traverse chain of length m. That could cause recursion depth of up to 200k, which might cause StackOverflowError in Java if recursion is used. So we should use iterative find with proper path compression to avoid deep recursion.

    But our find function as currently implemented (while loop with parent[x] = parent[parent[x]]) is not fully compressing all nodes to root in one pass; it does a kind of halving. Let's analyze:

    static int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    

    This compresses the path to some extent but not fully: It moves each node to its grandparent each iteration, which reduces depth but not all the way to root in a single call for all nodes on the path. However it works and is O(log n) amortized? Actually this is the standard path compression for disjoint set union with union by rank? But here we are not using union by rank; we are always setting parent[idx] = find(idx+1). This effectively builds a linked list. The find operation with the while loop above will flatten the path gradually. Let's test with a chain: parent[0]=1, parent[1]=2, parent[2]=3,..., parent[9]=10, parent[10]=10. Suppose we call find(0). Initially x=0, parent[0]=1 !=0, set parent[0]=parent[1] (which is 2), then x=2 (since after assignment, we set x = parent[x]? Let's read the code:

    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    

    Suppose x=0, parent[0]=1. Then parent[parent[0]] = parent[1]=2. So set parent[0]=2. Then x = parent[x] = parent[0] which is now 2. Now x=2, parent[2]=3. Set parent[2]=parent[3]=4, then x=4. This process jumps two steps each time, so after O(log n) iterations we get to root. However the nodes visited (0,2,4,8,...) are compressed only to their grandparent, but the intermediate nodes (like 1,3,5) are not visited and not compressed. However they may be visited later. But overall the amortized time is near O(log n) but can be O(log n) per operation, not quite inverse Ackermann but acceptable for 2e5. However there is a risk of stack overflow only if recursion used; iterative while is fine.

    But we need to ensure that after we union, find for later indices works properly. Since we are using a standard DSU for "next available" we often use an array "next" where we set next[i]=i+1 when used, and find is a recursion that compresses fully:

    int find(int x) {
        if (next[x] != x) next[x] = find(next[x]);
        return next[x];
    }
    

    That recursion might overflow. But we can implement it iteratively with a stack or while loop and compress fully. Let's adopt the recursive but with the knowledge that depth could be up to 200k; Java recursion limit is typically around 10k, so not safe. So we must use iterative.

    I can implement iterative find that fully compresses:

    static int find(int[] parent, int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        // path compression
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }
    

    This compresses all nodes on the path to root. It's safe and fast.

    But we can also use the simpler while loop with parent[x] = parent[parent[x]] because it still yields acceptable performance; the maximum depth will be reduced quickly. However for safety, I'll implement the full compression.

    Now test with scenario: after using indices 0,1,2,..., we will have a chain. Suppose we mark used in order: we process gaps and assign bridges. The order of assignments may not be in sorted order of indices; because we assign bridges based on lower bound. However typically the smallest bridge is assigned first; as we assign, we may use bridges not necessarily in increasing index order, but we always remove the bridge we used from the set. Since we always pick the smallest bridge >= min, and we process gaps sorted by max, it's possible we assign bridges in increasing order of length, but not necessarily the smallest indices in the sorted array. However in the sorted bridges array, indices correspond to sorted order by length, not original indices. So the order of usage may be increasing in terms of length, but not necessarily in terms of index (since same length may have different original indices, but we compare by length then index). However we will remove them in some order. The DSU will skip used ones.

    Now, the DSU find(lb) will return the first unused index >= lb. This works.

    Now, consider that lowerBound returns index of first length >= min. But there could be multiple bridges with same length. Our DSU find will skip used ones. That's fine.