#include #include #include using namespace std; using u64 = uint64_t; u64 gcd(u64 a, u64 b) { if(b == 0) { return a; } return gcd(b, a%b); } __uint128_t lcm(u64 a, u64 b) { return static_cast<__uint128_t>(a) * b / gcd(a, b); } void puts_uint128(__uint128_t x) { size_t n = 0; char buf[64]; do { buf[n++] = static_cast(x % 10 + '0'); x /= 10; } while(x != 0); buf[n] = '\0'; char *r = reinterpret_cast(malloc(n * sizeof(char))); for(size_t i=0; i