#include <inttypes.h>

typedef struct {
	uint64_t hi;
	uint64_t lo;
} uint128_t;

uint64_t sqrt128(uint128_t);

uint64_t sqrt128(uint128_t x)
{
	uint128_t r = {-1ULL, -1ULL};

	for ( ; ; ) {
		r.lo += 2;
		if (r.lo < 2)
			r.hi++;
		uint64_t c = x.lo < r.lo;
		x.lo -= r.lo;
		if (x.hi < r.hi)
			break;
		x.hi -= r.hi;
		if (x.hi < c)
			break;
		x.hi -= c;
	}
	return r.hi << 63 | r.lo >> 1;
}