#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using ll = long long; using P = std::pair; template std::ostream& operator<<(std::ostream& os, std::pair pa) { return os << "[" << pa.first << ", " << pa.second << "]"; } template std::ostream& operator<<(std::ostream& os, std::vector vec) { os << "{"; for (int i = 0; i < vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "}"; return os; } #define rep(i, a, b) for (ll(i) = (a); i < (b); i++) #define all(i) i.begin(), i.end() #define debug(i) std::cerr << "debug " << i << std::endl // const ll MOD = 998244353; const ll MOD = 1e9 + 7; long long extgcd(long long a,long long b,long long& x,long long& y){ for(ll u=y=1,v=x=0;a;){ ll q=b/a; std::swap(x-=q*u,u); std::swap(y-=q*v,v); std::swap(b-=q*a,a); } return b; } int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); ll t,a,b,temp,temp2; std::cin>>t>>a>>b; ll gcd=extgcd(a,b,temp,temp2); if((double)a/(double)gcd>(double)1e18/(double)b){ std::cout<