Pasha loves to send strictly positive integers to his friends. Pasha cares about security, therefore when he wants to send an integer nn , he encrypts it in the following way: he picks three integers aa , bb and cc such that l≤a,b,c≤rl≤a,b,c≤r , and then he computes the encrypted value m=n⋅a+b−cm=n⋅a+b−c .
Unfortunately, an adversary intercepted the values ll , rr and mm . Is it possible to recover the original values of aa , bb and cc from this information? More formally, you are asked to find any values of aa , bb and cc such that
- aa , bb and cc are integers,
- l≤a,b,c≤rl≤a,b,c≤r ,
- there exists a strictly positive integer nn , such that n⋅a+b−c=mn⋅a+b−c=m .
Input
The first line contains the only integer tt (1≤t≤201≤t≤20 ) — the number of test cases. The following tt lines describe one test case each.
Each test case consists of three integers ll , rr and mm (1≤l≤r≤5000001≤l≤r≤500000 , 1≤m≤10101≤m≤1010 ). The numbers are such that the answer to the problem exists.
Output
For each test case output three integers aa , bb and cc such that, l≤a,b,c≤rl≤a,b,c≤r and there exists a strictly positive integer nn such that n⋅a+b−c=mn⋅a+b−c=m . It is guaranteed that there is at least one possible solution, and you can output any possible combination if there are multiple solutions.
Example
Input
Copy
2
4 6 13
2 3 1
Output
Copy
4 6 5
2 2 3
对于表达式n * a + b – c = m, 只有m是确定的，又看到abc范围5e5，就能知道只需要枚举一个就好了，自然选择枚举a。因为b，c都在同一个范围内，所以尽量使得a * n更贴近m，便于构造b和c。因此从l~r枚举a，然后分a * n > m和 a * n < m两种情况，看哪种成立即可（没有要求最优啥的）。
特判一下m小于l的情况此时n * a必然大于m，必须让n取1，a取l才能使得b – c尽可能接近m。
记得开long long！
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { long long m, l, r;//别忘记开long long cin >> l >> r >> m; long long a = 0, b = 0, c = 0; if(m >= l) { for(a = l; a <= r; a++) { long long temp = m / a * a;//n * a < m if(m - temp <= r - l) { c = l, b = l + m - temp; break; } temp += a;//n * a > m if(temp - m <= r - l) { b = l, c = l + temp - m; break; } } } else//n只能为1（贪心 { a = l; b = l; c = 2 * l - m; } cout << a << ' ' << b << ' ' << c << ' ' << endl; } return 0; }