[Here](https://mirror.codeforces.com/contests/694053) is the contest link↵
↵
#### [A. Midpoint Rivalry](https://mirror.codeforces.com/contestsgym/694053/problem/A)↵
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
Can Leo just stand at the location of the possible chest that is closer to $a$? What if $x$ and $y$ are in opposite directions from $a$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For Leo to beat Maya, he must pick a starting position $z$ that is strictly closer to $x$ than $a$ is, AND strictly closer to $y$ than $a$ is.↵
↵
If $x$ and $y$ are on the same side of $a$ (e.g., $a < x$ and $a < y$), Leo can simply start at the chest position that is closest to $a$. For instance, if $a < x < y$, Leo can choose $z = x$. His distance to $x$ will be $0 < |a-x|$, and his distance to $y$ will be $y-x$, which is strictly less than Maya's distance of $y-a$. In this case, Leo is guaranteed to win.↵
↵
If $x$ and $y$ are on opposite sides of $a$ (e.g., $x < a < y$), any position $z$ that is strictly closer to $x$ than $a$ must satisfy $z < a$. However, any position strictly closer to $y$ than $a$ must satisfy $z > a$. It is mathematically impossible for $z$ to be both strictly less than and strictly greater than $a$ simultaneously.↵
↵
Thus, the answer is `YES` if and only if $x$ and $y$ are on the same side of $a$, which can be checked using the condition `(x < a) == (y < a)` or `(x - a) * (y - a) > 0`.↵
↵
- Time Complexity: $O(1)$ per test case.↵
- Space Complexity: $O(1)$↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
out = []↵
for i in range(1, 3 * t, 3):↵
a, x, y = int(input_data[i]), int(input_data[i+1]), int(input_data[i+2])↵
if (x < a) == (y < a):↵
out.append("YES")↵
else:↵
out.append("NO")↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [B. Odd One Out](https://mirror.codeforces.com/contestsgym/694053/problem/B)↵
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
When $n$ is odd, how many moves does Aqua make? Which positions can she mark? What does this mean for the final remaining digit?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The game depends entirely on the parity of $n$. ↵
↵
- **If $n$ is odd:** A total of $n-1$ turns will be made. Since $n-1$ is even, Ignis and Aqua will each make exactly $\frac{n-1}{2}$ moves. However, there are exactly $\frac{n-1}{2}$ even positions in the number. This means Aqua is forced to mark *every single* even position, so the last remaining digit is guaranteed to be on an odd position. Ignis gets to choose which odd position to save. If there is at least one odd digit on any odd position, Ignis can simply mark all other odd positions and win. If all digits on odd positions are even, Ignis will lose.↵
- **If $n$ is even:** The logic flips. Ignis will make $\frac{n}{2}$ moves and Aqua will make $\frac{n-2}{2}$ moves. Since there are $\frac{n}{2}$ odd positions, Ignis is forced to mark all of them, meaning the final digit will definitely come from an even position. Aqua gets to pick which one survives. If there is at least one even digit on an even position, Aqua will save it and win. Otherwise, Ignis wins.↵
↵
- Time Complexity: $O(n)$ per round.↵
- Space Complexity: $O(n)$ or $O(1)$ to store the string.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
idx = 1↵
out = []↵
for _ in range(t):↵
n = int(input_data[idx])↵
s = input_data[idx+1]↵
idx += 2↵
↵
if n % 2 != 0:↵
ignis_wins = False↵
for i in range(0, n, 2):↵
if int(s[i]) % 2 != 0:↵
ignis_wins = True↵
break↵
out.append("1" if ignis_wins else "2")↵
else:↵
aqua_wins = False↵
for i in range(1, n, 2):↵
if int(s[i]) % 2 == 0:↵
aqua_wins = True↵
break↵
out.append("2" if aqua_wins else "1")↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [C. Bullet Budget](https://mirror.codeforces.com/contestsgym/694053/problem/C)↵
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
If a beast starts at position $x$, how many seconds do you have to kill it? Does the side (left or right) matter?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Every beast essentially acts as a job with a strict deadline. A beast at position $x_i$ will reach the shrine in exactly $|x_i|$ seconds. Since we want to stop it *before* it reaches the shrine, we must fully deplete its endurance within the first $|x_i|$ seconds.↵
↵
The side from which a beast approaches doesn't matter; only its absolute distance $d_i = |x_i|$ matters. ↵
↵
Because we can distribute our $k$ arrows completely arbitrarily each second, we just need to make sure we aren't overwhelmed at any point. By second $d$, we can fire at most $d \times k$ arrows in total. Therefore, the total endurance of all beasts that started at distance $d$ or closer must not exceed $d \times k$. ↵
↵
We can simply group the beasts by their initial absolute distance, compute the prefix sums of their endurances, and check if $S_d \le d \times k$ holds for all $d \in [1, n]$. If it holds for all distances, the answer is `YES`. Otherwise, it is `NO`.↵
↵
- Time Complexity: $O(n)$ per test case.↵
- Space Complexity: $O(n)$ to store the accumulated endurances.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
idx = 1↵
out = []↵
↵
for _ in range(t):↵
n = int(input_data[idx])↵
k = int(input_data[idx+1])↵
idx += 2↵
↵
endurance_at_dist = [0] * (n + 1)↵
↵
a = []↵
for _ in range(n):↵
a.append(int(input_data[idx]))↵
idx += 1↵
↵
for i in range(n):↵
x = int(input_data[idx])↵
idx += 1↵
dist = abs(x)↵
if dist <= n:↵
endurance_at_dist[dist] += a[i]↵
↵
possible = True↵
current_sum = 0↵
for d in range(1, n + 1):↵
current_sum += endurance_at_dist[d]↵
if current_sum > d * k:↵
possible = False↵
break↵
↵
if possible:↵
out.append("YES")↵
else:↵
out.append("NO")↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [D. Chain Reaction](https://mirror.codeforces.com/contestsgym/694053/problem/D)↵
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
If you have two separate segments of crystals, you have two choices: detonate them separately, or plant crystals in the gap between them to connect them into a single segment. Which choice is better?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First, if there are no crystals in the kingdom (the string is all `0`s), the cost is obviously 0.↵
Otherwise, we can group the `1`s into contiguous segments. For example, `01100101` has 3 segments of `1`s.↵
↵
To clear the first segment, we must pay $a$ coins to detonate it.↵
For every subsequent segment, we have a choice:↵
1. Treat it as a separate segment and pay another $a$ coins to detonate it.↵
2. Bridge the gap between it and the previous segment by planting crystals. If the gap consists of $L$ zeros, this costs $L \times b$ coins, and effectively merges the two segments so they can be detonated together with the previous one.↵
↵
Naturally, we should choose the cheaper option for each gap. Thus, for each gap of length $L$ between two segments of `1`s, we add $\min(a, L \times b)$ to our total cost. ↵
↵
- Time Complexity: $O(n)$ to parse the string.↵
- Space Complexity: $O(n)$ or $O(1)$ to store the string and count gaps.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
idx = 1↵
out = []↵
↵
for _ in range(t):↵
a = int(input_data[idx])↵
b = int(input_data[idx+1])↵
s = input_data[idx+2]↵
idx += 3↵
↵
first_one = s.find('1')↵
if first_one == -1:↵
out.append("0")↵
continue↵
↵
last_one = s.rfind('1')↵
↵
ans = a↵
current_zero_len = 0↵
↵
for i in range(first_one, last_one + 1):↵
if s[i] == '0':↵
current_zero_len += 1↵
else:↵
if current_zero_len > 0:↵
ans += min(a, current_zero_len * b)↵
current_zero_len = 0↵
↵
out.append(str(ans))↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [E. Stain the Scroll](https://mirror.codeforces.com/contestsgym/694053/problem/E)↵
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
Can you rephrase the problem in terms of intervals? Every time a seal matches a part of the scroll, it covers a specific range $[L, R]$. The goal is to cover the entire range $[1, |t|]$ with the minimum number of intervals.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
This problem boils down to finding all occurrences of all seals in the scroll $t$, turning them into intervals, and then solving the classic "Minimum Interval Cover" problem.↵
↵
1. **String Matching:** For each seal $s_i$, we can slide a window across $t$ to find all starting positions where $s_i$ exactly matches a substring of $t$. If it matches starting at position $p$, it covers the interval $[p, p + |s_i| - 1]$. We collect all such intervals.↵
2. **Greedy Coverage:** We want to cover the interval $[1, |t|]$. We maintain a variable `covered` (initially 0), meaning we have covered everything up to index `covered`.↵
At each step, we look at all available intervals $[L, R]$ that start within or immediately after our covered region (i.e., $L \le \text{covered} + 1$). Among all these valid candidates, we greedily pick the one that extends our coverage the furthest (i.e., the one with the maximum $R$).↵
We then update `covered = R` and record this seal and its position. We repeat this process until `covered` $\ge |t|$.↵
↵
If at any point no valid interval can extend our coverage (all valid intervals have $R \le \text{covered}$), it means there is a gap we can never stain, so we output `-1`.↵
↵
- Time Complexity: $O(|t| \cdot \sum |s_i|)$ for string matching, and $O(K \log K)$ or $O(K \cdot |t|)$ for the greedy step, where $K$ is the number of valid occurrences. Given the small constraints, this is practically instantaneous.↵
- Space Complexity: $O(K)$ to store the intervals.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
q = int(input_data[0])↵
idx = 1↵
out = []↵
↵
for _ in range(q):↵
t_str = input_data[idx]↵
n = int(input_data[idx+1])↵
idx += 2↵
↵
seals = []↵
for _ in range(n):↵
seals.append(input_data[idx])↵
idx += 1↵
↵
intervals = []↵
for i, s in enumerate(seals):↵
seal_len = len(s)↵
for j in range(len(t_str) - seal_len + 1):↵
if t_str[j:j+seal_len] == s:↵
intervals.append((j + 1, j + seal_len, i + 1, j + 1))↵
↵
covered = 0↵
ans = []↵
possible = True↵
↵
while covered < len(t_str):↵
best_r = -1↵
best_seal = -1↵
best_pos = -1↵
↵
for L, R, seal_idx, pos in intervals:↵
if L <= covered + 1:↵
if R > best_r:↵
best_r = R↵
best_seal = seal_idx↵
best_pos = pos↵
↵
if best_r <= covered:↵
possible = False↵
break↵
↵
ans.append((best_seal, best_pos))↵
covered = best_r↵
↵
if not possible:↵
out.append("-1")↵
else:↵
out.append(str(len(ans)))↵
for seal_idx, pos in ans:↵
out.append(f"{seal_idx} {pos}")↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
↵
#### [A. Midpoint Rivalry](https://mirror.codeforces.com/
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
Can Leo just stand at the location of the possible chest that is closer to $a$? What if $x$ and $y$ are in opposite directions from $a$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For Leo to beat Maya, he must pick a starting position $z$ that is strictly closer to $x$ than $a$ is, AND strictly closer to $y$ than $a$ is.↵
↵
If $x$ and $y$ are on the same side of $a$ (e.g., $a < x$ and $a < y$), Leo can simply start at the chest position that is closest to $a$. For instance, if $a < x < y$, Leo can choose $z = x$. His distance to $x$ will be $0 < |a-x|$, and his distance to $y$ will be $y-x$, which is strictly less than Maya's distance of $y-a$. In this case, Leo is guaranteed to win.↵
↵
If $x$ and $y$ are on opposite sides of $a$ (e.g., $x < a < y$), any position $z$ that is strictly closer to $x$ than $a$ must satisfy $z < a$. However, any position strictly closer to $y$ than $a$ must satisfy $z > a$. It is mathematically impossible for $z$ to be both strictly less than and strictly greater than $a$ simultaneously.↵
↵
Thus, the answer is `YES` if and only if $x$ and $y$ are on the same side of $a$, which can be checked using the condition `(x < a) == (y < a)` or `(x - a) * (y - a) > 0`.↵
↵
- Time Complexity: $O(1)$ per test case.↵
- Space Complexity: $O(1)$↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
out = []↵
for i in range(1, 3 * t, 3):↵
a, x, y = int(input_data[i]), int(input_data[i+1]), int(input_data[i+2])↵
if (x < a) == (y < a):↵
out.append("YES")↵
else:↵
out.append("NO")↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [B. Odd One Out](https://mirror.codeforces.com/
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
When $n$ is odd, how many moves does Aqua make? Which positions can she mark? What does this mean for the final remaining digit?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The game depends entirely on the parity of $n$. ↵
↵
- **If $n$ is odd:** A total of $n-1$ turns will be made. Since $n-1$ is even, Ignis and Aqua will each make exactly $\frac{n-1}{2}$ moves. However, there are exactly $\frac{n-1}{2}$ even positions in the number. This means Aqua is forced to mark *every single* even position, so the last remaining digit is guaranteed to be on an odd position. Ignis gets to choose which odd position to save. If there is at least one odd digit on any odd position, Ignis can simply mark all other odd positions and win. If all digits on odd positions are even, Ignis will lose.↵
- **If $n$ is even:** The logic flips. Ignis will make $\frac{n}{2}$ moves and Aqua will make $\frac{n-2}{2}$ moves. Since there are $\frac{n}{2}$ odd positions, Ignis is forced to mark all of them, meaning the final digit will definitely come from an even position. Aqua gets to pick which one survives. If there is at least one even digit on an even position, Aqua will save it and win. Otherwise, Ignis wins.↵
↵
- Time Complexity: $O(n)$ per round.↵
- Space Complexity: $O(n)$ or $O(1)$ to store the string.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
idx = 1↵
out = []↵
for _ in range(t):↵
n = int(input_data[idx])↵
s = input_data[idx+1]↵
idx += 2↵
↵
if n % 2 != 0:↵
ignis_wins = False↵
for i in range(0, n, 2):↵
if int(s[i]) % 2 != 0:↵
ignis_wins = True↵
break↵
out.append("1" if ignis_wins else "2")↵
else:↵
aqua_wins = False↵
for i in range(1, n, 2):↵
if int(s[i]) % 2 == 0:↵
aqua_wins = True↵
break↵
out.append("2" if aqua_wins else "1")↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [C. Bullet Budget](https://mirror.codeforces.com/
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
If a beast starts at position $x$, how many seconds do you have to kill it? Does the side (left or right) matter?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Every beast essentially acts as a job with a strict deadline. A beast at position $x_i$ will reach the shrine in exactly $|x_i|$ seconds. Since we want to stop it *before* it reaches the shrine, we must fully deplete its endurance within the first $|x_i|$ seconds.↵
↵
The side from which a beast approaches doesn't matter; only its absolute distance $d_i = |x_i|$ matters. ↵
↵
Because we can distribute our $k$ arrows completely arbitrarily each second, we just need to make sure we aren't overwhelmed at any point. By second $d$, we can fire at most $d \times k$ arrows in total. Therefore, the total endurance of all beasts that started at distance $d$ or closer must not exceed $d \times k$. ↵
↵
We can simply group the beasts by their initial absolute distance, compute the prefix sums of their endurances, and check if $S_d \le d \times k$ holds for all $d \in [1, n]$. If it holds for all distances, the answer is `YES`. Otherwise, it is `NO`.↵
↵
- Time Complexity: $O(n)$ per test case.↵
- Space Complexity: $O(n)$ to store the accumulated endurances.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
idx = 1↵
out = []↵
↵
for _ in range(t):↵
n = int(input_data[idx])↵
k = int(input_data[idx+1])↵
idx += 2↵
↵
endurance_at_dist = [0] * (n + 1)↵
↵
a = []↵
for _ in range(n):↵
a.append(int(input_data[idx]))↵
idx += 1↵
↵
for i in range(n):↵
x = int(input_data[idx])↵
idx += 1↵
dist = abs(x)↵
if dist <= n:↵
endurance_at_dist[dist] += a[i]↵
↵
possible = True↵
current_sum = 0↵
for d in range(1, n + 1):↵
current_sum += endurance_at_dist[d]↵
if current_sum > d * k:↵
possible = False↵
break↵
↵
if possible:↵
out.append("YES")↵
else:↵
out.append("NO")↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [D. Chain Reaction](https://mirror.codeforces.com/
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
If you have two separate segments of crystals, you have two choices: detonate them separately, or plant crystals in the gap between them to connect them into a single segment. Which choice is better?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First, if there are no crystals in the kingdom (the string is all `0`s), the cost is obviously 0.↵
Otherwise, we can group the `1`s into contiguous segments. For example, `01100101` has 3 segments of `1`s.↵
↵
To clear the first segment, we must pay $a$ coins to detonate it.↵
For every subsequent segment, we have a choice:↵
1. Treat it as a separate segment and pay another $a$ coins to detonate it.↵
2. Bridge the gap between it and the previous segment by planting crystals. If the gap consists of $L$ zeros, this costs $L \times b$ coins, and effectively merges the two segments so they can be detonated together with the previous one.↵
↵
Naturally, we should choose the cheaper option for each gap. Thus, for each gap of length $L$ between two segments of `1`s, we add $\min(a, L \times b)$ to our total cost. ↵
↵
- Time Complexity: $O(n)$ to parse the string.↵
- Space Complexity: $O(n)$ or $O(1)$ to store the string and count gaps.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
t = int(input_data[0])↵
idx = 1↵
out = []↵
↵
for _ in range(t):↵
a = int(input_data[idx])↵
b = int(input_data[idx+1])↵
s = input_data[idx+2]↵
idx += 3↵
↵
first_one = s.find('1')↵
if first_one == -1:↵
out.append("0")↵
continue↵
↵
last_one = s.rfind('1')↵
↵
ans = a↵
current_zero_len = 0↵
↵
for i in range(first_one, last_one + 1):↵
if s[i] == '0':↵
current_zero_len += 1↵
else:↵
if current_zero_len > 0:↵
ans += min(a, current_zero_len * b)↵
current_zero_len = 0↵
↵
out.append(str(ans))↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
#### [E. Stain the Scroll](https://mirror.codeforces.com/
↵
Idea and preparation:↵
↵
<spoiler summary="Hint">↵
Can you rephrase the problem in terms of intervals? Every time a seal matches a part of the scroll, it covers a specific range $[L, R]$. The goal is to cover the entire range $[1, |t|]$ with the minimum number of intervals.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
This problem boils down to finding all occurrences of all seals in the scroll $t$, turning them into intervals, and then solving the classic "Minimum Interval Cover" problem.↵
↵
1. **String Matching:** For each seal $s_i$, we can slide a window across $t$ to find all starting positions where $s_i$ exactly matches a substring of $t$. If it matches starting at position $p$, it covers the interval $[p, p + |s_i| - 1]$. We collect all such intervals.↵
2. **Greedy Coverage:** We want to cover the interval $[1, |t|]$. We maintain a variable `covered` (initially 0), meaning we have covered everything up to index `covered`.↵
At each step, we look at all available intervals $[L, R]$ that start within or immediately after our covered region (i.e., $L \le \text{covered} + 1$). Among all these valid candidates, we greedily pick the one that extends our coverage the furthest (i.e., the one with the maximum $R$).↵
We then update `covered = R` and record this seal and its position. We repeat this process until `covered` $\ge |t|$.↵
↵
If at any point no valid interval can extend our coverage (all valid intervals have $R \le \text{covered}$), it means there is a gap we can never stain, so we output `-1`.↵
↵
- Time Complexity: $O(|t| \cdot \sum |s_i|)$ for string matching, and $O(K \log K)$ or $O(K \cdot |t|)$ for the greedy step, where $K$ is the number of valid occurrences. Given the small constraints, this is practically instantaneous.↵
- Space Complexity: $O(K)$ to store the intervals.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
def solve():↵
input_data = sys.stdin.read().split()↵
if not input_data: return↵
q = int(input_data[0])↵
idx = 1↵
out = []↵
↵
for _ in range(q):↵
t_str = input_data[idx]↵
n = int(input_data[idx+1])↵
idx += 2↵
↵
seals = []↵
for _ in range(n):↵
seals.append(input_data[idx])↵
idx += 1↵
↵
intervals = []↵
for i, s in enumerate(seals):↵
seal_len = len(s)↵
for j in range(len(t_str) - seal_len + 1):↵
if t_str[j:j+seal_len] == s:↵
intervals.append((j + 1, j + seal_len, i + 1, j + 1))↵
↵
covered = 0↵
ans = []↵
possible = True↵
↵
while covered < len(t_str):↵
best_r = -1↵
best_seal = -1↵
best_pos = -1↵
↵
for L, R, seal_idx, pos in intervals:↵
if L <= covered + 1:↵
if R > best_r:↵
best_r = R↵
best_seal = seal_idx↵
best_pos = pos↵
↵
if best_r <= covered:↵
possible = False↵
break↵
↵
ans.append((best_seal, best_pos))↵
covered = best_r↵
↵
if not possible:↵
out.append("-1")↵
else:↵
out.append(str(len(ans)))↵
for seal_idx, pos in ans:↵
out.append(f"{seal_idx} {pos}")↵
↵
print("\n".join(out))↵
↵
if __name__ == '__main__':↵
solve()↵
```↵
</spoiler>↵
↵
