class Solution(object):
    def mySqrt(self, x):
        if x < 2:
            return x
 
        left, right = 1, x // 2
 
        while left <= right:
            mid = (left + right) // 2
            square = mid * mid
 
            if square == x:
                return mid
            elif square < x:
                left = mid + 1
            else:
                right = mid - 1
 
        return right 

Y2xhc3MgU29sdXRpb24ob2JqZWN0KToKICAgIGRlZiBteVNxcnQoc2VsZiwgeCk6CiAgICAgICAgaWYgeCA8IDI6CiAgICAgICAgICAgIHJldHVybiB4CiAgICAgICAgCiAgICAgICAgbGVmdCwgcmlnaHQgPSAxLCB4IC8vIDIKICAgICAgICAKICAgICAgICB3aGlsZSBsZWZ0IDw9IHJpZ2h0OgogICAgICAgICAgICBtaWQgPSAobGVmdCArIHJpZ2h0KSAvLyAyCiAgICAgICAgICAgIHNxdWFyZSA9IG1pZCAqIG1pZAogICAgICAgICAgICAKICAgICAgICAgICAgaWYgc3F1YXJlID09IHg6CiAgICAgICAgICAgICAgICByZXR1cm4gbWlkCiAgICAgICAgICAgIGVsaWYgc3F1YXJlIDwgeDoKICAgICAgICAgICAgICAgIGxlZnQgPSBtaWQgKyAxCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICByaWdodCA9IG1pZCAtIDEKICAgICAgICAKICAgICAgICByZXR1cm4gcmlnaHQg