You are given q queries in the following form: Given three integers li, ri and di, find…
- User
You are given q queries in the following form:
Given three integers l_i, r_i and d_i, find minimum positive integer x_i such that it is divisible by d_i and it does not belong to the segment [l_i, r_i].
Can you answer all the queries?
Recall that a number x belongs to segment [l, r] if l ≤ x ≤ r. Input
The first line contains one integer q (1 ≤ q ≤ 500) — the number of queries.
Then q lines follow, each containing a query given in the format l_i r_i d_i (1 ≤ l_i ≤ r_i ≤ 10^9, 1 ≤ d_i ≤ 10^9). l_i, r_i and d_i are integers.
Output
For each query print one integer: the answer to this query.
Example
Input
5 2 4 2 5 10 4 3 10 1 1 2 3 4 6 5
Output
6 4 1 3 10
Assistant
We are to answer q queries. Each query gives l, r, d. We need minimum positive integer x such that d divides x (i.e., x is divisible by d) and x not in [l, r].
We need to find the smallest multiple of d that is either less than l or greater than r. Since we want minimum positive integer, we compare two candidates: the smallest multiple of d that is less than l (if any) and the smallest multiple of d that is greater than r (if any). The answer is the min of those two, but only among those that are positive (but both positive anyway, since multiples of d are positive integers given d>0 and we consider positive multiples). Actually, x must be positive integer. If there exists a multiple less than l, it might be 0? But 0 is not positive. So smallest positive multiple of d is d. So if d < l, then the smallest multiple less than l could be the largest multiple <= l-1. But we need to ensure it's positive. The largest multiple ≤ l-1 is floor((l-1)/d)*d. That could be 0 if floor((l-1)/d)=0, meaning l-1 < d. But if l > 1? Actually, if l=1, then floor(0/d)=0 => 0, but 0 is not positive. So we need to consider only positive multiples. So the candidate from below is: if there exists a positive multiple of d that is < l, i.e., d < l? Not exactly; if d < l, then d itself is a positive multiple less than l (since d is a multiple of itself). But could there be a multiple less than l even if d >= l? Only if d > l? If d > l, then the only multiples are d, 2d,... all >= d > l, so none less than l. So condition for existence of a positive multiple less than l is: d < l. Because the smallest positive multiple is d; if d >= l, then all multiples are >= l? Check: if d = l, then d is in [l, r] if r >= l, which it does. So d itself is in segment. The next multiple 2d is >= 2l > l, so it may be > r or not. But there is no positive multiple less than l because d is the smallest positive multiple, and it is >= l. So only if d < l can we have a positive multiple less than l. In that case, d itself is a candidate? Actually, d is a positive multiple less than l, and it's the smallest positive multiple overall, so that would be the smallest candidate from below. But we need the smallest such positive multiple that is not in [l,r]. If d < l, then d is not in [l,r] because it's less than l, so it qualifies. So candidate from below is d? But wait, consider l=5, d=2. d=2 <5, and 2 is a multiple of 2 and not in [5, r]. So answer would be 2, which is less than any multiple greater than r. But is there any other multiple less than l that is smaller than d? No, because d is the smallest positive multiple. So candidate below is d, if d < l. But is it always true that d is not in segment? Yes, because if d < l, it's not in segment. So answer could be d.
But consider the case where d < l but d might be zero? No.
So candidate below: if d < l, then x = d is valid and is the smallest positive multiple; so answer would be d (provided d not in segment). But careful: what if d is in the segment? That would mean d >= l and d <= r, but we assumed d < l, so impossible.
Thus if d < l, answer = d. However, there is nuance: What if d is not the only candidate? But it's the smallest positive integer divisible by d, so it's definitely the smallest possible x overall among all multiples, provided it is allowed. So if d < l, answer is d.
If d >= l, then no positive multiple below l exists (since d is smallest and d >= l). So we must take the smallest multiple greater than r. That would be the smallest multiple of d that is > r. That is: ceil((r+1)/d)d? Actually, we need smallest multiple > r. That's: if r < d, then d might be > r? But careful: d >= l, but l could be <= r. d might be less than or equal to r? If d is in [l, r], then d is not allowed; we need a multiple > r. The smallest multiple > r is: Let k = floor(r/d) + 1, then candidate = kd. That works even if d > r, then floor(r/d) = 0, k=1, candidate = d, which is > r. So candidate above = ((r // d) + 1) * d.
But we must ensure that candidate is positive. It is.
Now, what about cases where d < l but d is not the smallest answer? Consider d=6, l=10, r=20. d=6 < l, so candidate below =6, which is smallest. So answer 6.
But consider scenario where d < l, but d is divisible by something? It's fine.
Thus logic:
For each query:
if d < l: answer = d else: answer = ((r // d) + 1) * d
But is this always correct? Let's test some edge cases.
Edge case 1: l=1, r=5, d=2. Here d=2 >= l? l=1, so d >= l. So we go to else: r//d =5//2=2, +1 =>3, candidate=6. But is there a smaller multiple not in [1,5]? The multiples of 2: 2,4,6,... 2 and 4 are in segment, so the smallest positive not in segment is 6. So answer 6. Our logic gives 6.
Edge case 2: l=1, r=1, d=1. d=1 >= l, else branch: r//d=1//1=1, +1=2, candidate=2. But is there any positive multiple less than l? l=1, smallest positive multiple is 1, but it's in segment. So candidate above=2. answer 2.
Edge case 3: l=3, r=5, d=3. d >= l, else: r//d=5//3=1, +1=2, candidate=6. Multiples: 3 (in segment), 6 (not), answer 6.
Edge case 4: l=3, r=5, d=2. d=2 < l, so answer = d=2. Multiples: 2 (not in segment), correct.
Edge case 5: l=10, r=20, d=5. d=5 < l, answer=5. But 5 is less than l and not in segment. Yes.
Edge case 6: l=10, r=20, d=30. d=30 >= l, else: r//d=20//30=0, +1=1, candidate=30. 30 > r, answer 30. Also, is there any multiple less than l? Smallest positive multiple is 30, which is > r, so that's answer.
Edge case 7: l=100, r=200, d=150. d >= l, else: r//d=200//150=1, +1=2, candidate=300. But could there be a multiple less than l? smallest multiple is 150 which is in segment, so candidate=300.
Edge case 8: l=100, r=200, d=100. d >= l, else: r//d=200//100=2, +1=3, candidate=300. 100 and 200 are in segment, 300 is not, answer 300.
Edge case 9: l=1, r=10^9, d=1. d < l? No, d=1, l=1 => d >= l. So else: r//d = 10^9, +1 => 10^9+1, candidate = 10^9+1. That is >10^9, answer = 1000000001. But is there a smaller positive integer not in segment? All positive integers from 1 to 10^9 are in segment, so next is 10^9+1. So correct.
Edge case 10: l=1, r=10^9, d=2. d>=l => else: r//d = floor(1e9/2)=500000000, +1 => 500000001, candidate=1000000002? Actually (500000001)2 = 1000000002. But wait, is that the smallest multiple > r? Check r=1e9. Smallest multiple >1e9 is? Multiples of 2: 1e9 is even? 1e9 = 1000000000, which is even? Actually 1,000,000,000 is even? Yes, divisible by 2: 500,000,0002 = 1,000,000,000. So 1e9 is a multiple of 2 and is in segment. Next multiple is 1,000,000,002, which is > r. So candidate = 1,000,000,002. Our formula: floor(r/d) = floor(1e9/2)=500,000,000, +1 = 500,000,001, *2 = 1,000,000,002. Yes.
But is there any multiple less than l? l=1, smallest multiple is 2 which is >= l, so not less than l. So answer = 1,000,000,002.
All good.
Thus solution seems simple.
But wait, what about case where d is less than l but d is not the smallest? That's not possible.
But what about case where d is less than l but d is zero? d≥1.
Thus answer: if d < l: print(d) else print(((r // d) + 1) * d).
But we need to be careful about integer overflow? r and d up to 1e9, and (r//d + 1)*d could be up to? Worst-case: d=1, r=1e9, then result = 1e9+1, which fits in 32-bit signed? 1e9+1 < 2^31 (2,147,483,648), so fine. In C++ using 64-bit to be safe but Python has arbitrary ints.
Thus code is straightforward.
However, is there any scenario where the candidate from below could be something other than d? For instance, d < l but d could be 0? No. But could d be in segment? No, because d < l so it's below segment. So answer d is valid and smallest.
But consider scenario: l=2, r=4, d=2. Here d=2 is not less than l; d==l, so d >= l. So else branch: ((4//2)+1)*2 = (2+1)*2=6. answer 6. But could there be a multiple less than l? The smallest positive multiple is 2 which is not less than l (it's equal to l). So no. So 6 is answer.
Thus condition d < l is correct.
But what if d < l but d is not the smallest positive multiple? That's impossible because the set of positive multiples is {d, 2d, 3d,...}. The smallest is d.
Thus answer is indeed min(d if d<l else INF, ((r//d)+1)*d). But we can just do if d < l: print d else print ((r//d)+1)*d.
Check the example:
Input: 5 2 4 2 -> d=2, l=2, d is not < l, so else: r//d=4//2=2, +1=3, *2=6. Output 6 matches.
5 10 4 -> d=4, l=5? Actually l=5, d=4<5, so answer = 4. Output 4 matches.
3 10 1 -> d=1, l=3, d<l? 1<3 true, answer=1. Output 1 matches.
1 2 3 -> d=3, l=1, d>=l, else: r//d=2//3=0, +1=1, *3=3. Output 3 matches.
4 6 5 -> d=5, l=4, d>=l? 5>=4 true, else: r//d=6//5=1, +1=2, *5=10. Output 10 matches.
All good.
So solution is straightforward.
But wait, we should double-check the reasoning for the else branch: it returns the smallest multiple > r. But what about the scenario where d > r? Then ((r//d)+1)*d = (0+1)*d = d. d might be less than l? Actually if d > r, there are two subcases: d could be less than l? Not possible because l <= r, so if d > r, then d > r >= l, so d >= l? Actually d > r and r >= l => d > l as well? Could be d > r, but could d be < l? No, since l <= r, d > r implies d > l. So d > l. Then candidate = d, which is > r and thus not in segment. However, is it possible that there exists a positive multiple less than l? No because smallest multiple is d which is > l. So answer = d. That's fine.
But what if d is exactly equal to l? Then d is in segment; candidate from above = ((r//d)+1)*d. That's correct.
Thus algorithm stands.
Edge case: l=1, r=1, d=2. d=2 > r? 2>1, so d>=l? yes. else: r//d=1//2=0, +1=1, candidate=2. d is not in segment because segment is [1,1], so answer 2. But is there a smaller positive multiple? No. Good.
Now note that the constraints are small (q ≤ 500). So we can compute each query in O(1).
Thus we can write code.
But wait, there might be a nuance: In the first branch, we said if d < l, answer = d. But consider scenario: d < l, but d might be not the smallest positive multiple of d? Obviously it is. But is it guaranteed to be not in [l, r]? Yes because it's less than l. So it's valid. However, could there be a multiple of d that is less than l but larger than d? Possibly, but that would be larger, so the smallest is d. So answer d.
Thus final solution.
But I'm double-checking: Is there any scenario where the candidate from below is not d but some other multiple? Example: l=5, r=7, d=3. d=3 < l, answer = 3. That's fine.
Thus implementation: for each query read l, r, d; if d < l: print(d) else: print(((r // d) + 1) * d).
But be careful about integer division: In python, // does floor division, which for positive numbers is fine.
Thus solved.
Now the instruction: "You are given q queries... Can you answer all the queries?" So output each answer.
Now maybe there is nuance: The answer must be minimum positive integer x such that it is divisible by d and it does not belong to the segment [l, r]. So we must ensure we consider x could be less than l or greater than r. We've covered both.
But check: What about x=0? 0 is divisible by any d, but 0 is not positive. So not allowed.
Also, consider if l=1, and d=1, then d is not < l because d=l=1, so else branch: ((r//1)+1)*1 = r+1. That's answer.
What if l=1, r=1e9, d=1e9? d=1e9 >= l=1, else: r//d= (1e9)//1e9 =1, +1=2, candidate=2e9. But d itself (1e9) is in segment because l=1 <= 1e9 <= 1e9. So answer is 2e9. That's correct.
Now think about possible pitfalls: What about overflow? In C++, using 32-bit int might overflow if r and d are large, because (r/d+1)*d could be up to (1e9/1 + 1)*1 = 1e9+1, but for d small, e.g., d=1, r=1e9, result = 1e9+1, fits in int? int 32-bit max 2,147,483,647, so 1,000,000,001 fits. If d=1e9, r=1e9, result=2e9, fits? 2,000,000,000 < 2,147,483,647, fits. If d=1, r=2e9? But r ≤ 1e9 per constraints, so no issue. In Python it's fine.
Thus solution is trivial.
But wait: The problem statement might be from Codeforces (CF 1195A? Actually I recall a problem "Non-zero" etc. But this one is "Minimum positive integer not in segment divisible by d". The typical solution is exactly this.
I'll produce final answer.
One more check: Could there be a case where d is less than l but d is not allowed because it's inside [l,r]? It's not because it's less than l. So fine.
But what about l=10, r=20, d=5? d=5 < l, answer =5. That's fine.
Now consider if l=10, r=20, d=7. d=7 < l, answer 7. But is 7 divisible by 7? Yes. And 7 < 10, not in segment. So answer 7.
Thus answer is simple.
Now I'll produce final solution in Python.
Implementation:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return it = iter(data) q = int(next(it)) out = [] for _ in range(q): l = int(next(it)); r = int(next(it)); d = int(next(it)) if d < l: out.append(str(d)) else: # smallest multiple > r k = r // d ans = (k + 1) * d out.append(str(ans)) sys.stdout.write("\n".join(out))
Test with sample.
Sample:
5 2 4 2 -> d=2 not < l => r//d=2, (2+1)*2=6 5 10 4 -> d=4 <5 => output 4 3 10 1 -> d=1<3 => 1 1 2 3 -> d=3 not <1 => r//3=0, (0+1)*3=3 4 6 5 -> d=5 not <4 => r//5=1, (1+1)*5=10
Matches output.
Thus solution.
But is there any case where d < l but d is in segment? No.
Edge: l=1, r=1, d=2: d<l? 2<1 false, else: r//d=1//2=0 => (0+1)*2=2.
Yes.
Thus done.
I'll write final answer.
But maybe we need to consider the possibility that d could be 0? No, d >= 1.
Thus answer is correct.
But wait: The problem statement: "find minimum positive integer x_i such that it is divisible by d_i and it does not belong to the segment [l_i, r_i]." So x must be positive and divisible by d. That's all.
Thus answer.
But is there any scenario where both d < l and ((r//d)+1)*d could be smaller? That would be impossible because d is the smallest positive multiple. So if d qualifies, it's definitely the minimum.
Thus final.
Now I'll produce final answer with explanation and code. We need to answer each query independently.
The required integer (x) must be a positive multiple of (d) and must lie outside ([l, r]).
There are two possible sources for the answer:- a multiple smaller than (l) (if any),
- the smallest multiple greater than (r).
The smallest positive multiple of (d) is (d) itself.
- If (d < l), then (d) is outside the segment and is the smallest possible answer.
- Otherwise (i.e., (d \ge l)), no positive multiple smaller than (l) exists (because the smallest one, (d), is already (\ge l)). Then we must take the smallest multiple larger than (r). That multiple is (\left(\left\lfloor\frac{r}{d}\right\rfloor + 1\right) \cdot d).
Both branches are computed in constant time. The total complexity is (O(q)).
import sys def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) q = int(next(it)) out = [] for _ in range(q): l = int(next(it)) r = int(next(it)) d = int(next(it)) if d < l: out.append(str(d)) else: k = r // d # floor division ans = (k + 1) * d out.append(str(ans)) sys.stdout.write("\n".join(out)) if __name__ == "__main__": solve()