Restoring authorship annotation for Vlad Yaroslavlev <vladon@vladon.com>. Commit 2 of 2.

1 files changed, 1273 insertions, 1273 deletions

diff --git a/library/cpp/int128/int128.h b/library/cpp/int128/int128.h
index e6345f4f12..f1121fc0c6 100644
--- a/library/cpp/int128/int128.h
+++ b/library/cpp/int128/int128.h
@@ -1,1278 +1,1278 @@
-#pragma once 
- 
-#include "int128_util.h" 
- 
-#include <util/generic/bitops.h> 
-#include <util/system/compiler.h> 
-#include <util/system/defaults.h> 
-#include <util/stream/output.h> 
-#include <util/string/cast.h> 
-#include <util/string/builder.h> 
-#include <util/str_stl.h> 
-#include <util/ysaveload.h> 
- 
-#include <cfenv> 
-#include <climits> 
-#include <cmath> 
-#include <limits> 
-#include <type_traits> 
- 
-#if !defined(_little_endian_) && !defined(_big_endian_) 
-    static_assert(false, "Platform endianness is not supported"); 
-#endif 
- 
-template <bool IsSigned> 
-class TInteger128 { 
-public: 
-    TInteger128() noexcept = default; 
- 
-#if defined(_little_endian_) 
-    constexpr TInteger128(const ui64 high, const ui64 low) noexcept 
-        : Low_(low) 
-        , High_(high) 
-    { 
-    } 
-#elif defined(_big_endian_) 
-    constexpr TInteger128(const ui64 high, const ui64 low) noexcept 
-        : High_(high) 
-        , Low_(low) 
-    { 
-    } 
-#endif 
- 
-    constexpr TInteger128(const TInteger128<!IsSigned> other) noexcept 
-        : TInteger128{GetHigh(other), GetLow(other)} 
-    { 
-    } 
- 
-#if defined(_little_endian_) 
-    constexpr TInteger128(const char other) noexcept 
-        : Low_{static_cast<ui64>(other)} 
-        , High_{0} 
-    { 
-    } 
- 
-    constexpr TInteger128(const ui8 other) noexcept 
-        : Low_{other} 
-        , High_{0} 
-    { 
-    } 
- 
-    constexpr TInteger128(const ui16 other) noexcept 
-        : Low_{other} 
-        , High_{0} 
-    { 
-    } 
- 
-    constexpr TInteger128(const ui32 other) noexcept 
-        : Low_{other} 
-        , High_{0} 
-    { 
-    } 
- 
-    constexpr TInteger128(const ui64 other) noexcept 
-        : Low_{other} 
-        , High_{0} 
-    { 
-    } 
- 
-#if defined(Y_HAVE_INT128) 
-    constexpr TInteger128(const unsigned __int128 other) noexcept 
-        : Low_{static_cast<ui64>(other & ~ui64{0})} 
-        , High_{static_cast<ui64>(other >> 64)} 
-    { 
-    } 
-#endif 
- 
-    constexpr TInteger128(const i8 other) noexcept 
-        : Low_{static_cast<ui64>(other)} 
-        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0} 
-    { 
-    } 
- 
-    constexpr TInteger128(const i16 other) noexcept 
-        : Low_{static_cast<ui64>(other)} 
-        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0} 
-    { 
-    } 
- 
-    constexpr TInteger128(const i32 other) noexcept 
-        : Low_(static_cast<ui64>(other)) 
-        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0} 
-    { 
-    } 
- 
-    constexpr TInteger128(const i64 other) noexcept 
-        : Low_(static_cast<ui64>(other)) 
-        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0} 
-    { 
-    } 
- 
-#if defined(Y_HAVE_INT128) 
-    template <bool IsSigned2 = IsSigned, std::enable_if_t<!IsSigned2, bool> = false> 
-    constexpr TInteger128(const signed __int128 other) noexcept 
-        : Low_{static_cast<ui64>(other & ~ui64{0})} 
-        , High_{static_cast<ui64>(static_cast<unsigned __int128>(other) >> 64)} 
-    { 
-    } 
- 
-    template <bool IsSigned2 = IsSigned, typename std::enable_if_t<IsSigned2, bool> = false> 
-    constexpr TInteger128(const signed __int128 other) noexcept 
-        : Low_{static_cast<ui64>(other & ~ui64(0))} 
-        , High_{static_cast<ui64>(other >> 64)} 
-    { 
-    } 
-#endif 
- 
-#elif defined(_big_endian_) 
-    static_assert(false, "Big-endian will be later"); 
-#endif // _little_endian_ or _big_endian_ 
- 
-    constexpr TInteger128& operator=(const char other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator=(const ui8 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator=(const ui16 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator=(const ui32 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator=(const ui64 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-#if defined(Y_HAVE_INT128) 
-    constexpr TInteger128& operator=(const unsigned __int128 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
-#endif 
- 
-    constexpr TInteger128& operator=(const i8 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator=(const i16 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator=(const i32 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator=(const i64 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
- 
-#if defined(Y_HAVE_INT128) 
-    constexpr TInteger128& operator=(const signed __int128 other) noexcept { 
-        *this = TInteger128{other}; 
-        return *this; 
-    } 
-#endif // Y_HAVE_INT128 
- 
-    constexpr TInteger128& operator+=(const TInteger128 other) noexcept { 
-        return *this = *this + other; 
-    } 
- 
-    constexpr TInteger128& operator-=(const TInteger128 other) noexcept { 
-        return *this = *this - other; 
-    } 
- 
-    constexpr TInteger128& operator*=(const TInteger128 other) noexcept { 
-        return *this = *this * other; 
-    } 
- 
-    constexpr TInteger128& operator&=(const TInteger128 other) noexcept { 
-        return *this = *this & other; 
-    } 
- 
-    constexpr TInteger128& operator^=(const TInteger128 other) noexcept { 
+#pragma once
+
+#include "int128_util.h"
+
+#include <util/generic/bitops.h>
+#include <util/system/compiler.h>
+#include <util/system/defaults.h>
+#include <util/stream/output.h>
+#include <util/string/cast.h>
+#include <util/string/builder.h>
+#include <util/str_stl.h>
+#include <util/ysaveload.h>
+
+#include <cfenv>
+#include <climits>
+#include <cmath>
+#include <limits>
+#include <type_traits>
+
+#if !defined(_little_endian_) && !defined(_big_endian_)
+    static_assert(false, "Platform endianness is not supported");
+#endif
+
+template <bool IsSigned>
+class TInteger128 {
+public:
+    TInteger128() noexcept = default;
+
+#if defined(_little_endian_)
+    constexpr TInteger128(const ui64 high, const ui64 low) noexcept
+        : Low_(low)
+        , High_(high)
+    {
+    }
+#elif defined(_big_endian_)
+    constexpr TInteger128(const ui64 high, const ui64 low) noexcept
+        : High_(high)
+        , Low_(low)
+    {
+    }
+#endif
+
+    constexpr TInteger128(const TInteger128<!IsSigned> other) noexcept
+        : TInteger128{GetHigh(other), GetLow(other)}
+    {
+    }
+
+#if defined(_little_endian_)
+    constexpr TInteger128(const char other) noexcept
+        : Low_{static_cast<ui64>(other)}
+        , High_{0}
+    {
+    }
+
+    constexpr TInteger128(const ui8 other) noexcept
+        : Low_{other}
+        , High_{0}
+    {
+    }
+
+    constexpr TInteger128(const ui16 other) noexcept
+        : Low_{other}
+        , High_{0}
+    {
+    }
+
+    constexpr TInteger128(const ui32 other) noexcept
+        : Low_{other}
+        , High_{0}
+    {
+    }
+
+    constexpr TInteger128(const ui64 other) noexcept
+        : Low_{other}
+        , High_{0}
+    {
+    }
+
+#if defined(Y_HAVE_INT128)
+    constexpr TInteger128(const unsigned __int128 other) noexcept
+        : Low_{static_cast<ui64>(other & ~ui64{0})}
+        , High_{static_cast<ui64>(other >> 64)}
+    {
+    }
+#endif
+
+    constexpr TInteger128(const i8 other) noexcept
+        : Low_{static_cast<ui64>(other)}
+        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0}
+    {
+    }
+
+    constexpr TInteger128(const i16 other) noexcept
+        : Low_{static_cast<ui64>(other)}
+        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0}
+    {
+    }
+
+    constexpr TInteger128(const i32 other) noexcept
+        : Low_(static_cast<ui64>(other))
+        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0}
+    {
+    }
+
+    constexpr TInteger128(const i64 other) noexcept
+        : Low_(static_cast<ui64>(other))
+        , High_{other < 0 ? std::numeric_limits<ui64>::max() : 0}
+    {
+    }
+
+#if defined(Y_HAVE_INT128)
+    template <bool IsSigned2 = IsSigned, std::enable_if_t<!IsSigned2, bool> = false>
+    constexpr TInteger128(const signed __int128 other) noexcept
+        : Low_{static_cast<ui64>(other & ~ui64{0})}
+        , High_{static_cast<ui64>(static_cast<unsigned __int128>(other) >> 64)}
+    {
+    }
+
+    template <bool IsSigned2 = IsSigned, typename std::enable_if_t<IsSigned2, bool> = false>
+    constexpr TInteger128(const signed __int128 other) noexcept
+        : Low_{static_cast<ui64>(other & ~ui64(0))}
+        , High_{static_cast<ui64>(other >> 64)}
+    {
+    }
+#endif
+
+#elif defined(_big_endian_)
+    static_assert(false, "Big-endian will be later");
+#endif // _little_endian_ or _big_endian_
+
+    constexpr TInteger128& operator=(const char other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+    constexpr TInteger128& operator=(const ui8 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+    constexpr TInteger128& operator=(const ui16 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+    constexpr TInteger128& operator=(const ui32 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+    constexpr TInteger128& operator=(const ui64 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+#if defined(Y_HAVE_INT128)
+    constexpr TInteger128& operator=(const unsigned __int128 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+#endif
+
+    constexpr TInteger128& operator=(const i8 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+    constexpr TInteger128& operator=(const i16 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+    constexpr TInteger128& operator=(const i32 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+    constexpr TInteger128& operator=(const i64 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+
+#if defined(Y_HAVE_INT128)
+    constexpr TInteger128& operator=(const signed __int128 other) noexcept {
+        *this = TInteger128{other};
+        return *this;
+    }
+#endif // Y_HAVE_INT128
+
+    constexpr TInteger128& operator+=(const TInteger128 other) noexcept {
+        return *this = *this + other;
+    }
+
+    constexpr TInteger128& operator-=(const TInteger128 other) noexcept {
+        return *this = *this - other;
+    }
+
+    constexpr TInteger128& operator*=(const TInteger128 other) noexcept {
+        return *this = *this * other;
+    }
+
+    constexpr TInteger128& operator&=(const TInteger128 other) noexcept {
+        return *this = *this & other;
+    }
+
+    constexpr TInteger128& operator^=(const TInteger128 other) noexcept {
         return *this = *this ^ other;
-    } 
- 
-    constexpr TInteger128& operator|=(const TInteger128 other) noexcept { 
-        return *this = *this | other; 
-    } 
- 
-    constexpr TInteger128& operator<<=(int n) noexcept { 
-        *this = *this << n; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator>>=(int n) noexcept { 
-        *this = *this >> n; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128& operator++() noexcept { 
-        *this += 1; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128 operator++(int) noexcept { 
-        const TInteger128 ret{*this}; 
-        this->operator++(); 
-        return ret; 
-    } 
- 
-    constexpr TInteger128& operator--() noexcept { 
-        *this -= 1; 
-        return *this; 
-    } 
- 
-    constexpr TInteger128 operator--(int) noexcept { 
-        const TInteger128 ret{*this}; 
-        this->operator--(); 
-        return ret; 
-    } 
- 
-    explicit constexpr operator bool() const noexcept { 
-        return Low_ || High_; 
-    } 
- 
-    explicit constexpr operator char() const noexcept { 
-        return static_cast<char>(Low_); 
-    } 
- 
-    explicit constexpr operator ui8() const noexcept { 
-        return static_cast<ui8>(Low_); 
-    } 
- 
-    explicit constexpr operator i8() const noexcept { 
-        return static_cast<i8>(Low_); 
-    } 
- 
-    explicit constexpr operator ui16() const noexcept { 
-        return static_cast<ui16>(Low_); 
-    } 
- 
-    explicit constexpr operator i16() const noexcept { 
-        return static_cast<i16>(Low_); 
-    } 
- 
-    explicit constexpr operator ui32() const noexcept { 
-        return static_cast<ui32>(Low_); 
-    } 
- 
-    explicit constexpr operator i32() const noexcept { 
-        return static_cast<i32>(Low_); 
-    } 
- 
-    explicit constexpr operator ui64() const noexcept { 
-        return static_cast<ui64>(Low_); 
-    } 
- 
-    explicit constexpr operator i64() const noexcept { 
-        return static_cast<i64>(Low_); 
-    } 
- 
-#if defined(Y_HAVE_INT128) 
-    explicit constexpr operator unsigned __int128() const noexcept { 
-        return (static_cast<unsigned __int128>(High_) << 64) + Low_; 
-    } 
- 
-    explicit constexpr operator signed __int128() const noexcept { 
-        return (static_cast<__int128>(High_) << 64) + Low_; 
-    } 
-#endif 
- 
-private: 
-#if defined(_little_endian_) 
-    ui64 Low_; 
-    ui64 High_; 
-#elif defined(_big_endian_) 
-    ui64 High_; 
-    ui64 Low_; 
-#endif 
-    template <bool IsSigned2> 
-    friend constexpr ui64 GetHigh(TInteger128<IsSigned2> value) noexcept; 
- 
-    template <bool IsSigned2> 
-    friend constexpr ui64 GetLow(TInteger128<IsSigned2> value) noexcept; 
- 
-    friend IOutputStream& operator<<(IOutputStream& out, const TInteger128& other); 
-}; // class TInteger128 
- 
-using ui128 = TInteger128<false>; 
-using i128 = TInteger128<true>; 
- 
-constexpr ui128 operator+(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator+( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator-(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator-( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator-(ui128 num) noexcept; 
-constexpr  i128 operator-( i128 num) noexcept; 
-constexpr ui128 operator*(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator*( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator/(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator/( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator%(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator%( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator|(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator|( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator&(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator&( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator^(ui128 lhs, ui128 rhs) noexcept; 
-constexpr  i128 operator^( i128 lhs,  i128 rhs) noexcept; 
-constexpr ui128 operator<<(ui128 lhs, int n) noexcept; 
-constexpr  i128 operator<<( i128 lhs, int n) noexcept; 
-constexpr ui128 operator>>(ui128 lhs, int n) noexcept; 
-constexpr  i128 operator>>( i128 lhs, int n) noexcept; 
- 
-template <bool IsSigned> 
-size_t MostSignificantBit(const TInteger128<IsSigned> v); 
- 
-namespace std { 
-    //// type traits 
-    template <bool IsSigned> 
-    struct is_integral<TInteger128<IsSigned>> : public std::true_type{}; 
- 
-    template <bool IsSigned> 
-    struct is_class<TInteger128<IsSigned>> : public std::false_type{}; 
- 
-    template <> 
-    struct is_signed<ui128> : public std::false_type{}; 
- 
-    template <> 
-    struct is_signed<i128> : public std::true_type{}; 
-} 
- 
-template <bool IsSigned> 
-constexpr ui64 GetHigh(const TInteger128<IsSigned> value) noexcept { 
-    return value.High_; 
-} 
- 
-template <bool IsSigned> 
-constexpr ui64 GetLow(const TInteger128<IsSigned> value) noexcept { 
-    return value.Low_; 
-} 
- 
-template <class T, std::enable_if_t<std::is_same_v<std::remove_cv_t<T>, i128>>* = nullptr> 
-constexpr ui128 operator-(const ui128 lhs, const T rhs) noexcept { 
-    return lhs - static_cast<ui128>(rhs); 
-} 
- 
-template <class T, std::enable_if_t<std::is_same_v<std::remove_cv_t<T>, ui128>>* = nullptr> 
-constexpr ui128 operator-(const i128 lhs, const T rhs) noexcept { 
-    return static_cast<ui128>(lhs) - rhs; 
-} 
- 
-// specialize std templates 
-namespace std { 
-    // numeric limits 
-    // see full list at https://en.cppreference.com/w/cpp/types/numeric_limits 
-    template <bool IsSigned> 
-    struct numeric_limits<TInteger128<IsSigned>> { 
-        static constexpr bool is_specialized = true; 
-        static constexpr bool is_signed = IsSigned; 
-        static constexpr bool is_integer = true; 
-        static constexpr bool is_exact = true; 
-        static constexpr bool has_infinity = false; 
-        static constexpr bool has_quiet_NAN = false; 
-        static constexpr bool has_signaling_NAN = false; 
-        static constexpr float_denorm_style has_denorm = std::denorm_absent; 
-        static constexpr bool has_denorm_loss = false; 
-        static constexpr float_round_style round_style = std::round_toward_zero; 
-        static constexpr bool is_iec559 = false; 
-        static constexpr bool is_bounded = true; 
-        static constexpr bool is_modulo = true; 
-        static constexpr int digits = CHAR_BIT * sizeof(ui128) - (IsSigned ? 1 : 0); 
-        static constexpr int digits10 = 38; // std::numeric_limits<ui128>::digits * std::log10(2); 
-        static constexpr int max_digits10 = 0; 
-        static constexpr int radix = 2; 
-        static constexpr int min_exponent = 0; 
-        static constexpr int min_exponent10 = 0; 
-        static constexpr int max_exponent = 0; 
-        static constexpr int max_exponent10 = 0; 
-        static constexpr bool traps = std::numeric_limits<ui64>::traps; // same as of any other ui* 
-        static constexpr bool tinyness_before = false; 
- 
-        static constexpr TInteger128<IsSigned> min() noexcept { 
-            if constexpr (IsSigned) { 
-                return TInteger128<IsSigned>{ 
-                    static_cast<ui64>(std::numeric_limits<i64>::min()), 
-                    0 
-                }; 
-            } 
-            else { 
-                return 0; 
-            } 
-        } 
- 
-        static constexpr TInteger128<IsSigned> lowest() noexcept { 
-            return min(); 
-        } 
- 
-        static constexpr TInteger128<IsSigned> max() noexcept { 
-            if constexpr (IsSigned) { 
-                return TInteger128<IsSigned>{ 
-                    static_cast<ui64>(std::numeric_limits<i64>::max()), 
-                    std::numeric_limits<ui64>::max() 
-                }; 
-            } 
-            else { 
-                return TInteger128<IsSigned>{ 
-                    std::numeric_limits<ui64>::max(), 
-                    std::numeric_limits<ui64>::max() 
-                }; 
-            } 
-        } 
- 
-        static constexpr TInteger128<IsSigned> epsilon() noexcept { 
-            return 0; 
-        } 
- 
-        static constexpr TInteger128<IsSigned> round_error() noexcept { 
-            return 0; 
-        } 
- 
-        static constexpr TInteger128<IsSigned> infinity() noexcept { 
-            return 0; 
-        } 
- 
-        static constexpr TInteger128<IsSigned> quiet_NAN() noexcept { 
-            return 0; 
-        } 
- 
-        static constexpr TInteger128<IsSigned> signaling_NAN() noexcept { 
-            return 0; 
-        } 
- 
-        static constexpr TInteger128<IsSigned> denorm_min() noexcept { 
-            return 0; 
-        } 
-    }; 
- 
-    constexpr bool signbit(const ui128 arg) noexcept { 
-        Y_UNUSED(arg); 
-        return false; 
-    } 
- 
-    constexpr bool signbit(const i128 arg) noexcept { 
-        return GetHigh(arg) & 0x8000000000000000; 
-    } 
- 
-    constexpr ui128 abs(const ui128 arg) noexcept { 
-        return arg; 
-    } 
- 
-    constexpr i128 abs(const i128 arg) noexcept { 
-        return signbit(arg) ? (-arg) : arg; 
-    } 
-} 
- 
-constexpr bool operator==(const ui128 lhs, const ui128 rhs) noexcept { 
-    return GetLow(lhs) == GetLow(rhs) && GetHigh(lhs) == GetHigh(rhs); 
-} 
- 
-constexpr bool operator==(const i128 lhs, const i128 rhs) noexcept { 
-    return GetLow(lhs) == GetLow(rhs) && GetHigh(lhs) == GetHigh(rhs); 
-} 
- 
-constexpr bool operator!=(const ui128 lhs, const ui128 rhs) noexcept { 
-    return !(lhs == rhs); 
-} 
- 
-constexpr bool operator!=(const i128 lhs, const i128 rhs) noexcept { 
-    return !(lhs == rhs); 
-} 
- 
-constexpr bool operator<(const ui128 lhs, const ui128 rhs) noexcept { 
-    if (GetHigh(lhs) != GetHigh(rhs)) { 
-        return GetHigh(lhs) < GetHigh(rhs); 
-    } 
- 
-    return GetLow(lhs) < GetLow(rhs); 
-} 
- 
-constexpr bool operator<(const i128 lhs, const i128 rhs) noexcept { 
-    if (lhs == 0 && rhs == 0) { 
-        return false; 
-    } 
- 
-    const bool lhsIsNegative = std::signbit(lhs); 
-    const bool rhsIsNegative = std::signbit(rhs); 
- 
-    if (lhsIsNegative && !rhsIsNegative) { 
-        return true; 
-    } 
- 
-    if (!lhsIsNegative && rhsIsNegative) { 
-        return false; 
-    } 
- 
-    // both are negative or both are positive 
-    if (GetHigh(lhs) != GetHigh(rhs)) { 
-        return GetHigh(lhs) < GetHigh(rhs); 
-    } 
- 
-    return GetLow(lhs) < GetLow(rhs); 
-} 
- 
-constexpr bool operator>(const ui128 lhs, const ui128 rhs) noexcept { 
-    return rhs < lhs; 
-} 
- 
-constexpr bool operator>(const i128 lhs, const i128 rhs) noexcept { 
-    return rhs < lhs; 
-} 
- 
-constexpr bool operator<=(const ui128 lhs, const ui128 rhs) noexcept { 
-    return !(rhs < lhs); 
-} 
- 
-constexpr bool operator<=(const i128 lhs, const i128 rhs) noexcept { 
-    return !(rhs < lhs); 
-} 
- 
-constexpr bool operator>=(const ui128 lhs, const ui128 rhs) noexcept { 
-    return !(lhs < rhs); 
-} 
- 
-constexpr bool operator>=(const i128 lhs, const i128 rhs) noexcept { 
-    return !(lhs < rhs); 
-} 
- 
-constexpr ui128 operator+(const ui128 lhs, const ui128 rhs) noexcept { 
-    const ui128 result{GetHigh(lhs) + GetHigh(rhs), GetLow(lhs) + GetLow(rhs)}; 
-    if (GetLow(result) < GetLow(lhs)) { 
-        return ui128{GetHigh(result) + 1, GetLow(result)}; 
-    } 
-    return result; 
-} 
- 
-constexpr i128 operator+(const i128 lhs, const i128 rhs) noexcept { 
-    const i128 result{GetHigh(lhs) + GetHigh(rhs), GetLow(lhs) + GetLow(rhs)}; 
-    if (GetLow(result) < GetLow(lhs)) { 
-        return i128{GetHigh(result) + 1, GetLow(result)}; 
-    } 
-    return result; 
-} 
- 
-constexpr ui128 operator-(const ui128 lhs, const ui128 rhs) noexcept { 
-    const ui128 result{GetHigh(lhs) - GetHigh(rhs), GetLow(lhs) - GetLow(rhs)}; 
-    if (GetLow(result) > GetLow(lhs)) { // underflow 
-        return ui128{GetHigh(result) - 1, GetLow(result)}; 
-    } 
-    return result; 
-} 
- 
-constexpr i128 operator-(const i128 lhs, const i128 rhs) noexcept { 
-    const i128 result{GetHigh(lhs) - GetHigh(rhs), GetLow(lhs) - GetLow(rhs)}; 
-    if (GetLow(result) > GetLow(lhs)) { // underflow 
-        return i128{GetHigh(result) - 1, GetLow(result)}; 
-    } 
-    return result; 
-} 
- 
-constexpr ui128 operator-(const ui128 num) noexcept { 
-    const ui128 result{~GetHigh(num), ~GetLow(num) + 1}; 
-    if (GetLow(result) == 0) { 
-        return ui128{GetHigh(result) + 1, GetLow(result)}; 
-    } 
-    return result; 
-} 
- 
-constexpr i128 operator-(const i128 num) noexcept { 
-    const i128 result{~GetHigh(num), ~GetLow(num) + 1}; 
-    if (GetLow(result) == 0) { 
-        return i128{GetHigh(result) + 1, GetLow(result)}; 
-    } 
-    return result; 
-} 
- 
-constexpr ui128 operator*(const ui128 lhs, const ui128 rhs) noexcept { 
-    if (rhs == 0) { 
-        return 0; 
-    } 
-    if (rhs == 1) { 
-        return lhs; 
-    } 
- 
-    ui128 result{}; 
-    ui128 t = rhs; 
- 
-    for (size_t i = 0; i < 128; ++i) { 
-        if ((t & 1) != 0) { 
-            result += (lhs << i); 
-        } 
- 
-        t = t >> 1; 
-    } 
- 
-    return result; 
-} 
- 
-constexpr i128 operator*(const i128 lhs, const i128 rhs) noexcept { 
-    if (rhs == 0) { 
-        return 0; 
-    } 
-    if (rhs == 1) { 
-        return lhs; 
-    } 
- 
-    i128 result{}; 
-    i128 t = rhs; 
- 
-    for (size_t i = 0; i < 128; ++i) { 
-        if ((t & 1) != 0) { 
-            result += (lhs << i); 
-        } 
- 
-        t = t >> 1; 
-    } 
- 
-    return result; 
-} 
- 
-namespace NPrivateInt128 { 
-    // NOTE: division by zero is UB and can be changed in future 
-    constexpr void DivMod128(const ui128 lhs, const ui128 rhs, ui128* const quo, ui128* const rem) { 
-        if (!quo && !rem) { 
-            return; 
-        } 
- 
-        constexpr size_t n_udword_bits = sizeof(ui64) * CHAR_BIT; 
-        constexpr size_t n_utword_bits = sizeof(ui128) * CHAR_BIT; 
- 
-        ui128 q{}; 
-        ui128 r{}; 
- 
-        unsigned sr{}; 
- 
-        /* special cases, X is unknown, K != 0 */ 
-        if (GetHigh(lhs) == 0) 
-        { 
-            if (GetHigh(rhs) == 0) 
-            { 
-                /* 0 X 
-                 * --- 
-                 * 0 X 
-                 */ 
-                if (rem) { 
-                    *rem = GetLow(lhs) % GetLow(rhs); 
-                } 
-                if (quo) { 
-                    *quo = GetLow(lhs) / GetLow(rhs); 
-                } 
-                return; 
-            } 
-            /* 0 X 
-             * --- 
-             * K X 
-             */ 
-            if (rem) { 
-                *rem = GetLow(lhs); 
-            } 
-            if (quo) { 
-                *quo = 0; 
-            } 
-            return; 
-        } 
-        /* n.s.high != 0 */ 
-        if (GetLow(rhs) == 0) 
-        { 
-            if (GetHigh(rhs) == 0) 
-            { 
-                /* K X 
-                 * --- 
-                 * 0 0 
-                 */ 
-                if (rem) { 
-                    *rem = GetHigh(lhs) % GetLow(rhs); 
-                } 
-                if (quo) { 
-                    *quo = GetHigh(lhs) / GetLow(rhs); 
-                } 
-                return; 
-            } 
-            /* d.s.high != 0 */ 
-            if (GetLow(lhs) == 0) 
-            { 
-                /* K 0 
-                 * --- 
-                 * K 0 
-                 */ 
-                if (rem) { 
-                    *rem = ui128{GetHigh(lhs) % GetHigh(rhs), 0}; 
-                } 
-                if (quo) { 
-                    *quo = GetHigh(lhs) / GetHigh(rhs); 
-                } 
-                return; 
-            } 
-            /* K K 
-             * --- 
-             * K 0 
-             */ 
-            if ((GetHigh(rhs) & (GetHigh(rhs) - 1)) == 0)     /* if d is a power of 2 */ 
-            { 
-                if (rem) { 
-                    *rem = ui128{GetHigh(lhs) & (GetHigh(rhs) - 1), GetLow(lhs)}; 
-                } 
-                if (quo) { 
-                    *quo = GetHigh(lhs) >> CountLeadingZeroBits(GetHigh(rhs)); 
-                } 
-                return; 
-            } 
-            /* K K 
-             * --- 
-             * K 0 
-             */ 
-            sr = CountLeadingZeroBits(GetHigh(rhs)) - CountLeadingZeroBits(GetHigh(lhs)); 
-            /* 0 <= sr <= n_udword_bits - 2 or sr large */ 
-            if (sr > n_udword_bits - 2) 
-            { 
-                if (rem) { 
-                    *rem = lhs; 
-                } 
-                if (quo) { 
-                    *quo = 0; 
-                } 
-                return; 
-            } 
-            ++sr; 
-            /* 1 <= sr <= n_udword_bits - 1 */ 
-            /* q.all = n.all << (n_utword_bits - sr); */ 
-            q = ui128{ 
-                GetLow(lhs) << (n_udword_bits - sr), 
-                0 
-            }; 
-            r = ui128{ 
-                GetHigh(lhs) >> sr, 
-                (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr) 
-            }; 
-        } 
-        else  /* d.s.low != 0 */ 
-        { 
-            if (GetHigh(rhs) == 0) 
-            { 
-                /* K X 
-                * --- 
-                * 0 K 
-                */ 
-                if ((GetLow(rhs) & (GetLow(rhs) - 1)) == 0)     /* if d is a power of 2 */ 
-                { 
-                    if (rem) { 
-                        *rem = ui128{0, GetLow(lhs) & (GetLow(rhs) - 1)}; 
-                    } 
-                    if (GetLow(rhs) == 1) { 
-                        if (quo) { 
-                            *quo = lhs; 
-                        } 
-                        return; 
-                    } 
-                    sr = CountTrailingZeroBits(GetLow(rhs)); 
-                    if (quo) { 
-                        *quo = ui128{ 
-                            GetHigh(lhs) >> sr, 
-                            (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr) 
-                        }; 
-                        return; 
-                    } 
-                } 
-                /* K X 
-                * --- 
-                * 0 K 
-                */ 
-                sr = 1 + n_udword_bits + CountLeadingZeroBits(GetLow(rhs)) 
-                                    - CountLeadingZeroBits(GetHigh(lhs)); 
-                /* 2 <= sr <= n_utword_bits - 1 
-                * q.all = n.all << (n_utword_bits - sr); 
-                * r.all = n.all >> sr; 
-                */ 
-                if (sr == n_udword_bits) 
-                { 
-                    q = ui128{GetLow(lhs), 0}; 
-                    r = ui128{0, GetHigh(lhs)}; 
-                } 
-                else if (sr < n_udword_bits)  // 2 <= sr <= n_udword_bits - 1 
-                { 
-                    q = ui128{ 
-                        GetLow(lhs) << (n_udword_bits - sr), 
-                        0 
-                    }; 
-                    r = ui128{ 
-                        GetHigh(lhs) >> sr, 
-                        (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr) 
-                    }; 
-                } 
-                else              // n_udword_bits + 1 <= sr <= n_utword_bits - 1 
-                { 
-                    q = ui128{ 
-                        (GetHigh(lhs) << (n_utword_bits - sr)) | (GetLow(lhs) >> (sr - n_udword_bits)), 
-                        GetLow(lhs) << (n_utword_bits - sr) 
-                    }; 
-                    r = ui128{ 
-                        0, 
-                        GetHigh(lhs) >> (sr - n_udword_bits) 
-                    }; 
-                } 
-            } 
-            else 
-            { 
-                /* K X 
-                * --- 
-                * K K 
-                */ 
-                sr = CountLeadingZeroBits(GetHigh(rhs)) - CountLeadingZeroBits(GetHigh(lhs)); 
-                /*0 <= sr <= n_udword_bits - 1 or sr large */ 
-                if (sr > n_udword_bits - 1) 
-                { 
-                    if (rem) { 
-                        *rem = lhs; 
-                    } 
-                    if (quo) { 
-                        *quo = 0; 
-                    } 
-                    return; 
-                } 
-                ++sr; 
-                /* 1 <= sr <= n_udword_bits 
-                * q.all = n.all << (n_utword_bits - sr); 
-                * r.all = n.all >> sr; 
-                */ 
-                if (sr == n_udword_bits) 
-                { 
-                    q = ui128{ 
-                        GetLow(lhs), 
-                        0 
-                    }; 
-                    r = ui128{ 
-                        0, 
-                        GetHigh(lhs) 
-                    }; 
-                } 
-                else 
-                { 
-                    r = ui128{ 
-                        GetHigh(lhs) >> sr, 
-                        (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr) 
-                    }; 
-                    q = ui128{ 
-                        GetLow(lhs) << (n_udword_bits - sr), 
-                        0 
-                    }; 
-                } 
-            } 
-        } 
-        /* Not a special case 
-         * q and r are initialized with: 
-         * q = n << (128 - sr); 
-         * r = n >> sr; 
-         * 1 <= sr <= 128 - 1 
-         */ 
-        ui32 carry = 0; 
-        for (; sr > 0; --sr) 
-        { 
-            /* r:q = ((r:q)  << 1) | carry */ 
-            r = ui128{ 
-                (GetHigh(r) << 1) | (GetLow(r)  >> (n_udword_bits - 1)), 
-                (GetLow(r)  << 1) | (GetHigh(q) >> (n_udword_bits - 1)) 
-            }; 
-            q = ui128{ 
-                (GetHigh(q) << 1) | (GetLow(q)  >> (n_udword_bits - 1)), 
-                (GetLow(q)  << 1) | carry 
-            }; 
-            carry = 0; 
-            if (r >= rhs) { 
-                r -= rhs; 
-                carry = 1; 
-            } 
-        } 
-        q = (q << 1) | carry; 
-        if (rem) { 
-            *rem = r; 
-        } 
-        if (quo) { 
-            *quo = q; 
-        } 
-    } 
- 
-    struct TSignedDivisionResult { 
-        i128 Quotient; 
-        i128 Remainder; 
-    }; 
- 
-    constexpr TSignedDivisionResult Divide(i128 lhs, i128 rhs) noexcept; 
-} 
- 
-constexpr ui128 operator/(const ui128 lhs, const ui128 rhs) noexcept { 
-    ui128 quotient{}; 
-    NPrivateInt128::DivMod128(lhs, rhs, &quotient, nullptr); 
-    return quotient; 
-} 
- 
-constexpr i128 operator/(const i128 lhs, const i128 rhs) noexcept { 
-    i128 a = std::abs(lhs); 
-    i128 b = std::abs(rhs); 
- 
-    ui128 quotient{}; 
-    NPrivateInt128::DivMod128(a, b, &quotient, nullptr); 
-    if (std::signbit(lhs) ^ std::signbit(rhs)) { 
-        quotient = -quotient; 
-    } 
-    return quotient; 
-} 
- 
-constexpr ui128 operator%(const ui128 lhs, const ui128 rhs) noexcept { 
-    ui128 remainder{}; 
-    NPrivateInt128::DivMod128(lhs, rhs, nullptr, &remainder); 
-    return remainder; 
-} 
- 
-constexpr i128 operator%(const i128 lhs, const i128 rhs) noexcept { 
-    i128 a = std::abs(lhs); 
-    i128 b = std::abs(rhs); 
-    ui128 remainder{}; 
-    NPrivateInt128::DivMod128(a, b, nullptr, &remainder); 
-    if (std::signbit(lhs)) { 
-        remainder = -remainder; 
-    } 
-    return remainder; 
-} 
- 
-constexpr ui128 operator<<(const ui128 lhs, int n) noexcept { 
-    if (n < 64) { 
-        if (n != 0) { 
-            return 
-                ui128{ 
-                    (GetHigh(lhs) << n) | (GetLow(lhs) >> (64 - n)), 
-                    GetLow(lhs) << n 
-                }; 
-        } 
-        return lhs; 
-    } 
-    return ui128{GetLow(lhs) << (n - 64), 0}; 
-} 
- 
-constexpr ui128 operator>>(const ui128 lhs, int n) noexcept { 
-    if (n < 64) { 
-        if (n != 0) { 
-            return 
-                ui128{ 
-                    GetHigh(lhs) >> n, 
-                    (GetLow(lhs) >> n) | (GetHigh(lhs) << (64 - n)) 
-                }; 
-        } 
-        return lhs; 
-    } 
-    return ui128{0, GetHigh(lhs) >> (n - 64)}; 
-} 
- 
- 
-constexpr bool operator!(const ui128 num) noexcept { 
-    return !GetHigh(num) && !GetLow(num); 
-} 
- 
-constexpr ui128 operator~(const ui128 num) noexcept { 
-    return ui128{~GetHigh(num), ~GetLow(num)}; 
-} 
- 
-constexpr ui128 operator|(const ui128 lhs, const ui128 rhs) noexcept { 
-    return ui128{GetHigh(lhs) | GetHigh(rhs), GetLow(lhs) | GetLow(rhs)}; 
-} 
- 
-constexpr ui128 operator&(const ui128 lhs, const ui128 rhs) noexcept { 
-    return ui128{GetHigh(lhs) & GetHigh(rhs), GetLow(lhs) & GetLow(rhs)}; 
-} 
- 
-constexpr  ui128 operator^(const ui128 lhs, const ui128 rhs) noexcept { 
-    return ui128{GetHigh(lhs) ^ GetHigh(rhs), GetLow(lhs) ^ GetLow(rhs)}; 
-} 
- 
- 
-IOutputStream& operator<<(IOutputStream& out, const ui128& other); 
- 
-// For THashMap 
-template <> 
-struct THash<ui128> { 
-    inline size_t operator()(const ui128& num) const { 
-        return THash<ui64>()(GetHigh(num)) + THash<ui64>()(GetLow(num)); 
-    } 
-}; 
- 
-template <> 
-class TSerializer<ui128> { 
-public: 
-    static void Save(IOutputStream* out, const ui128& Number); 
-    static void Load(IInputStream* in, ui128& Number); 
-}; 
- 
-template <> 
-inline TString ToString<ui128>(const ui128& number) { 
-    return TStringBuilder{} << number; 
-} 
- 
-template <> 
-inline ui128 FromStringImpl<ui128>(const char* data, size_t length) { 
-    if (length < 20) { 
-        return ui128{ FromString<ui64>(data, length) }; 
-    } else { 
-        ui128 result = 0; 
-        const TStringBuf string(data, length); 
-        for (auto&& c : string) { 
-            if (!std::isdigit(c)) { 
+    }
+
+    constexpr TInteger128& operator|=(const TInteger128 other) noexcept {
+        return *this = *this | other;
+    }
+
+    constexpr TInteger128& operator<<=(int n) noexcept {
+        *this = *this << n;
+        return *this;
+    }
+
+    constexpr TInteger128& operator>>=(int n) noexcept {
+        *this = *this >> n;
+        return *this;
+    }
+
+    constexpr TInteger128& operator++() noexcept {
+        *this += 1;
+        return *this;
+    }
+
+    constexpr TInteger128 operator++(int) noexcept {
+        const TInteger128 ret{*this};
+        this->operator++();
+        return ret;
+    }
+
+    constexpr TInteger128& operator--() noexcept {
+        *this -= 1;
+        return *this;
+    }
+
+    constexpr TInteger128 operator--(int) noexcept {
+        const TInteger128 ret{*this};
+        this->operator--();
+        return ret;
+    }
+
+    explicit constexpr operator bool() const noexcept {
+        return Low_ || High_;
+    }
+
+    explicit constexpr operator char() const noexcept {
+        return static_cast<char>(Low_);
+    }
+
+    explicit constexpr operator ui8() const noexcept {
+        return static_cast<ui8>(Low_);
+    }
+
+    explicit constexpr operator i8() const noexcept {
+        return static_cast<i8>(Low_);
+    }
+
+    explicit constexpr operator ui16() const noexcept {
+        return static_cast<ui16>(Low_);
+    }
+
+    explicit constexpr operator i16() const noexcept {
+        return static_cast<i16>(Low_);
+    }
+
+    explicit constexpr operator ui32() const noexcept {
+        return static_cast<ui32>(Low_);
+    }
+
+    explicit constexpr operator i32() const noexcept {
+        return static_cast<i32>(Low_);
+    }
+
+    explicit constexpr operator ui64() const noexcept {
+        return static_cast<ui64>(Low_);
+    }
+
+    explicit constexpr operator i64() const noexcept {
+        return static_cast<i64>(Low_);
+    }
+
+#if defined(Y_HAVE_INT128)
+    explicit constexpr operator unsigned __int128() const noexcept {
+        return (static_cast<unsigned __int128>(High_) << 64) + Low_;
+    }
+
+    explicit constexpr operator signed __int128() const noexcept {
+        return (static_cast<__int128>(High_) << 64) + Low_;
+    }
+#endif
+
+private:
+#if defined(_little_endian_)
+    ui64 Low_;
+    ui64 High_;
+#elif defined(_big_endian_)
+    ui64 High_;
+    ui64 Low_;
+#endif
+    template <bool IsSigned2>
+    friend constexpr ui64 GetHigh(TInteger128<IsSigned2> value) noexcept;
+
+    template <bool IsSigned2>
+    friend constexpr ui64 GetLow(TInteger128<IsSigned2> value) noexcept;
+
+    friend IOutputStream& operator<<(IOutputStream& out, const TInteger128& other);
+}; // class TInteger128
+
+using ui128 = TInteger128<false>;
+using i128 = TInteger128<true>;
+
+constexpr ui128 operator+(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator+( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator-(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator-( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator-(ui128 num) noexcept;
+constexpr  i128 operator-( i128 num) noexcept;
+constexpr ui128 operator*(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator*( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator/(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator/( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator%(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator%( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator|(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator|( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator&(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator&( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator^(ui128 lhs, ui128 rhs) noexcept;
+constexpr  i128 operator^( i128 lhs,  i128 rhs) noexcept;
+constexpr ui128 operator<<(ui128 lhs, int n) noexcept;
+constexpr  i128 operator<<( i128 lhs, int n) noexcept;
+constexpr ui128 operator>>(ui128 lhs, int n) noexcept;
+constexpr  i128 operator>>( i128 lhs, int n) noexcept;
+
+template <bool IsSigned>
+size_t MostSignificantBit(const TInteger128<IsSigned> v);
+
+namespace std {
+    //// type traits
+    template <bool IsSigned>
+    struct is_integral<TInteger128<IsSigned>> : public std::true_type{};
+
+    template <bool IsSigned>
+    struct is_class<TInteger128<IsSigned>> : public std::false_type{};
+
+    template <>
+    struct is_signed<ui128> : public std::false_type{};
+
+    template <>
+    struct is_signed<i128> : public std::true_type{};
+}
+
+template <bool IsSigned>
+constexpr ui64 GetHigh(const TInteger128<IsSigned> value) noexcept {
+    return value.High_;
+}
+
+template <bool IsSigned>
+constexpr ui64 GetLow(const TInteger128<IsSigned> value) noexcept {
+    return value.Low_;
+}
+
+template <class T, std::enable_if_t<std::is_same_v<std::remove_cv_t<T>, i128>>* = nullptr>
+constexpr ui128 operator-(const ui128 lhs, const T rhs) noexcept {
+    return lhs - static_cast<ui128>(rhs);
+}
+
+template <class T, std::enable_if_t<std::is_same_v<std::remove_cv_t<T>, ui128>>* = nullptr>
+constexpr ui128 operator-(const i128 lhs, const T rhs) noexcept {
+    return static_cast<ui128>(lhs) - rhs;
+}
+
+// specialize std templates
+namespace std {
+    // numeric limits
+    // see full list at https://en.cppreference.com/w/cpp/types/numeric_limits
+    template <bool IsSigned>
+    struct numeric_limits<TInteger128<IsSigned>> {
+        static constexpr bool is_specialized = true;
+        static constexpr bool is_signed = IsSigned;
+        static constexpr bool is_integer = true;
+        static constexpr bool is_exact = true;
+        static constexpr bool has_infinity = false;
+        static constexpr bool has_quiet_NAN = false;
+        static constexpr bool has_signaling_NAN = false;
+        static constexpr float_denorm_style has_denorm = std::denorm_absent;
+        static constexpr bool has_denorm_loss = false;
+        static constexpr float_round_style round_style = std::round_toward_zero;
+        static constexpr bool is_iec559 = false;
+        static constexpr bool is_bounded = true;
+        static constexpr bool is_modulo = true;
+        static constexpr int digits = CHAR_BIT * sizeof(ui128) - (IsSigned ? 1 : 0);
+        static constexpr int digits10 = 38; // std::numeric_limits<ui128>::digits * std::log10(2);
+        static constexpr int max_digits10 = 0;
+        static constexpr int radix = 2;
+        static constexpr int min_exponent = 0;
+        static constexpr int min_exponent10 = 0;
+        static constexpr int max_exponent = 0;
+        static constexpr int max_exponent10 = 0;
+        static constexpr bool traps = std::numeric_limits<ui64>::traps; // same as of any other ui*
+        static constexpr bool tinyness_before = false;
+
+        static constexpr TInteger128<IsSigned> min() noexcept {
+            if constexpr (IsSigned) {
+                return TInteger128<IsSigned>{
+                    static_cast<ui64>(std::numeric_limits<i64>::min()),
+                    0
+                };
+            }
+            else {
+                return 0;
+            }
+        }
+
+        static constexpr TInteger128<IsSigned> lowest() noexcept {
+            return min();
+        }
+
+        static constexpr TInteger128<IsSigned> max() noexcept {
+            if constexpr (IsSigned) {
+                return TInteger128<IsSigned>{
+                    static_cast<ui64>(std::numeric_limits<i64>::max()),
+                    std::numeric_limits<ui64>::max()
+                };
+            }
+            else {
+                return TInteger128<IsSigned>{
+                    std::numeric_limits<ui64>::max(),
+                    std::numeric_limits<ui64>::max()
+                };
+            }
+        }
+
+        static constexpr TInteger128<IsSigned> epsilon() noexcept {
+            return 0;
+        }
+
+        static constexpr TInteger128<IsSigned> round_error() noexcept {
+            return 0;
+        }
+
+        static constexpr TInteger128<IsSigned> infinity() noexcept {
+            return 0;
+        }
+
+        static constexpr TInteger128<IsSigned> quiet_NAN() noexcept {
+            return 0;
+        }
+
+        static constexpr TInteger128<IsSigned> signaling_NAN() noexcept {
+            return 0;
+        }
+
+        static constexpr TInteger128<IsSigned> denorm_min() noexcept {
+            return 0;
+        }
+    };
+
+    constexpr bool signbit(const ui128 arg) noexcept {
+        Y_UNUSED(arg);
+        return false;
+    }
+
+    constexpr bool signbit(const i128 arg) noexcept {
+        return GetHigh(arg) & 0x8000000000000000;
+    }
+
+    constexpr ui128 abs(const ui128 arg) noexcept {
+        return arg;
+    }
+
+    constexpr i128 abs(const i128 arg) noexcept {
+        return signbit(arg) ? (-arg) : arg;
+    }
+}
+
+constexpr bool operator==(const ui128 lhs, const ui128 rhs) noexcept {
+    return GetLow(lhs) == GetLow(rhs) && GetHigh(lhs) == GetHigh(rhs);
+}
+
+constexpr bool operator==(const i128 lhs, const i128 rhs) noexcept {
+    return GetLow(lhs) == GetLow(rhs) && GetHigh(lhs) == GetHigh(rhs);
+}
+
+constexpr bool operator!=(const ui128 lhs, const ui128 rhs) noexcept {
+    return !(lhs == rhs);
+}
+
+constexpr bool operator!=(const i128 lhs, const i128 rhs) noexcept {
+    return !(lhs == rhs);
+}
+
+constexpr bool operator<(const ui128 lhs, const ui128 rhs) noexcept {
+    if (GetHigh(lhs) != GetHigh(rhs)) {
+        return GetHigh(lhs) < GetHigh(rhs);
+    }
+
+    return GetLow(lhs) < GetLow(rhs);
+}
+
+constexpr bool operator<(const i128 lhs, const i128 rhs) noexcept {
+    if (lhs == 0 && rhs == 0) {
+        return false;
+    }
+
+    const bool lhsIsNegative = std::signbit(lhs);
+    const bool rhsIsNegative = std::signbit(rhs);
+
+    if (lhsIsNegative && !rhsIsNegative) {
+        return true;
+    }
+
+    if (!lhsIsNegative && rhsIsNegative) {
+        return false;
+    }
+
+    // both are negative or both are positive
+    if (GetHigh(lhs) != GetHigh(rhs)) {
+        return GetHigh(lhs) < GetHigh(rhs);
+    }
+
+    return GetLow(lhs) < GetLow(rhs);
+}
+
+constexpr bool operator>(const ui128 lhs, const ui128 rhs) noexcept {
+    return rhs < lhs;
+}
+
+constexpr bool operator>(const i128 lhs, const i128 rhs) noexcept {
+    return rhs < lhs;
+}
+
+constexpr bool operator<=(const ui128 lhs, const ui128 rhs) noexcept {
+    return !(rhs < lhs);
+}
+
+constexpr bool operator<=(const i128 lhs, const i128 rhs) noexcept {
+    return !(rhs < lhs);
+}
+
+constexpr bool operator>=(const ui128 lhs, const ui128 rhs) noexcept {
+    return !(lhs < rhs);
+}
+
+constexpr bool operator>=(const i128 lhs, const i128 rhs) noexcept {
+    return !(lhs < rhs);
+}
+
+constexpr ui128 operator+(const ui128 lhs, const ui128 rhs) noexcept {
+    const ui128 result{GetHigh(lhs) + GetHigh(rhs), GetLow(lhs) + GetLow(rhs)};
+    if (GetLow(result) < GetLow(lhs)) {
+        return ui128{GetHigh(result) + 1, GetLow(result)};
+    }
+    return result;
+}
+
+constexpr i128 operator+(const i128 lhs, const i128 rhs) noexcept {
+    const i128 result{GetHigh(lhs) + GetHigh(rhs), GetLow(lhs) + GetLow(rhs)};
+    if (GetLow(result) < GetLow(lhs)) {
+        return i128{GetHigh(result) + 1, GetLow(result)};
+    }
+    return result;
+}
+
+constexpr ui128 operator-(const ui128 lhs, const ui128 rhs) noexcept {
+    const ui128 result{GetHigh(lhs) - GetHigh(rhs), GetLow(lhs) - GetLow(rhs)};
+    if (GetLow(result) > GetLow(lhs)) { // underflow
+        return ui128{GetHigh(result) - 1, GetLow(result)};
+    }
+    return result;
+}
+
+constexpr i128 operator-(const i128 lhs, const i128 rhs) noexcept {
+    const i128 result{GetHigh(lhs) - GetHigh(rhs), GetLow(lhs) - GetLow(rhs)};
+    if (GetLow(result) > GetLow(lhs)) { // underflow
+        return i128{GetHigh(result) - 1, GetLow(result)};
+    }
+    return result;
+}
+
+constexpr ui128 operator-(const ui128 num) noexcept {
+    const ui128 result{~GetHigh(num), ~GetLow(num) + 1};
+    if (GetLow(result) == 0) {
+        return ui128{GetHigh(result) + 1, GetLow(result)};
+    }
+    return result;
+}
+
+constexpr i128 operator-(const i128 num) noexcept {
+    const i128 result{~GetHigh(num), ~GetLow(num) + 1};
+    if (GetLow(result) == 0) {
+        return i128{GetHigh(result) + 1, GetLow(result)};
+    }
+    return result;
+}
+
+constexpr ui128 operator*(const ui128 lhs, const ui128 rhs) noexcept {
+    if (rhs == 0) {
+        return 0;
+    }
+    if (rhs == 1) {
+        return lhs;
+    }
+
+    ui128 result{};
+    ui128 t = rhs;
+
+    for (size_t i = 0; i < 128; ++i) {
+        if ((t & 1) != 0) {
+            result += (lhs << i);
+        }
+
+        t = t >> 1;
+    }
+
+    return result;
+}
+
+constexpr i128 operator*(const i128 lhs, const i128 rhs) noexcept {
+    if (rhs == 0) {
+        return 0;
+    }
+    if (rhs == 1) {
+        return lhs;
+    }
+
+    i128 result{};
+    i128 t = rhs;
+
+    for (size_t i = 0; i < 128; ++i) {
+        if ((t & 1) != 0) {
+            result += (lhs << i);
+        }
+
+        t = t >> 1;
+    }
+
+    return result;
+}
+
+namespace NPrivateInt128 {
+    // NOTE: division by zero is UB and can be changed in future
+    constexpr void DivMod128(const ui128 lhs, const ui128 rhs, ui128* const quo, ui128* const rem) {
+        if (!quo && !rem) {
+            return;
+        }
+
+        constexpr size_t n_udword_bits = sizeof(ui64) * CHAR_BIT;
+        constexpr size_t n_utword_bits = sizeof(ui128) * CHAR_BIT;
+
+        ui128 q{};
+        ui128 r{};
+
+        unsigned sr{};
+
+        /* special cases, X is unknown, K != 0 */
+        if (GetHigh(lhs) == 0)
+        {
+            if (GetHigh(rhs) == 0)
+            {
+                /* 0 X
+                 * ---
+                 * 0 X
+                 */
+                if (rem) {
+                    *rem = GetLow(lhs) % GetLow(rhs);
+                }
+                if (quo) {
+                    *quo = GetLow(lhs) / GetLow(rhs);
+                }
+                return;
+            }
+            /* 0 X
+             * ---
+             * K X
+             */
+            if (rem) {
+                *rem = GetLow(lhs);
+            }
+            if (quo) {
+                *quo = 0;
+            }
+            return;
+        }
+        /* n.s.high != 0 */
+        if (GetLow(rhs) == 0)
+        {
+            if (GetHigh(rhs) == 0)
+            {
+                /* K X
+                 * ---
+                 * 0 0
+                 */
+                if (rem) {
+                    *rem = GetHigh(lhs) % GetLow(rhs);
+                }
+                if (quo) {
+                    *quo = GetHigh(lhs) / GetLow(rhs);
+                }
+                return;
+            }
+            /* d.s.high != 0 */
+            if (GetLow(lhs) == 0)
+            {
+                /* K 0
+                 * ---
+                 * K 0
+                 */
+                if (rem) {
+                    *rem = ui128{GetHigh(lhs) % GetHigh(rhs), 0};
+                }
+                if (quo) {
+                    *quo = GetHigh(lhs) / GetHigh(rhs);
+                }
+                return;
+            }
+            /* K K
+             * ---
+             * K 0
+             */
+            if ((GetHigh(rhs) & (GetHigh(rhs) - 1)) == 0)     /* if d is a power of 2 */
+            {
+                if (rem) {
+                    *rem = ui128{GetHigh(lhs) & (GetHigh(rhs) - 1), GetLow(lhs)};
+                }
+                if (quo) {
+                    *quo = GetHigh(lhs) >> CountLeadingZeroBits(GetHigh(rhs));
+                }
+                return;
+            }
+            /* K K
+             * ---
+             * K 0
+             */
+            sr = CountLeadingZeroBits(GetHigh(rhs)) - CountLeadingZeroBits(GetHigh(lhs));
+            /* 0 <= sr <= n_udword_bits - 2 or sr large */
+            if (sr > n_udword_bits - 2)
+            {
+                if (rem) {
+                    *rem = lhs;
+                }
+                if (quo) {
+                    *quo = 0;
+                }
+                return;
+            }
+            ++sr;
+            /* 1 <= sr <= n_udword_bits - 1 */
+            /* q.all = n.all << (n_utword_bits - sr); */
+            q = ui128{
+                GetLow(lhs) << (n_udword_bits - sr),
+                0
+            };
+            r = ui128{
+                GetHigh(lhs) >> sr,
+                (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr)
+            };
+        }
+        else  /* d.s.low != 0 */
+        {
+            if (GetHigh(rhs) == 0)
+            {
+                /* K X
+                * ---
+                * 0 K
+                */
+                if ((GetLow(rhs) & (GetLow(rhs) - 1)) == 0)     /* if d is a power of 2 */
+                {
+                    if (rem) {
+                        *rem = ui128{0, GetLow(lhs) & (GetLow(rhs) - 1)};
+                    }
+                    if (GetLow(rhs) == 1) {
+                        if (quo) {
+                            *quo = lhs;
+                        }
+                        return;
+                    }
+                    sr = CountTrailingZeroBits(GetLow(rhs));
+                    if (quo) {
+                        *quo = ui128{
+                            GetHigh(lhs) >> sr,
+                            (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr)
+                        };
+                        return;
+                    }
+                }
+                /* K X
+                * ---
+                * 0 K
+                */
+                sr = 1 + n_udword_bits + CountLeadingZeroBits(GetLow(rhs))
+                                    - CountLeadingZeroBits(GetHigh(lhs));
+                /* 2 <= sr <= n_utword_bits - 1
+                * q.all = n.all << (n_utword_bits - sr);
+                * r.all = n.all >> sr;
+                */
+                if (sr == n_udword_bits)
+                {
+                    q = ui128{GetLow(lhs), 0};
+                    r = ui128{0, GetHigh(lhs)};
+                }
+                else if (sr < n_udword_bits)  // 2 <= sr <= n_udword_bits - 1
+                {
+                    q = ui128{
+                        GetLow(lhs) << (n_udword_bits - sr),
+                        0
+                    };
+                    r = ui128{
+                        GetHigh(lhs) >> sr,
+                        (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr)
+                    };
+                }
+                else              // n_udword_bits + 1 <= sr <= n_utword_bits - 1
+                {
+                    q = ui128{
+                        (GetHigh(lhs) << (n_utword_bits - sr)) | (GetLow(lhs) >> (sr - n_udword_bits)),
+                        GetLow(lhs) << (n_utword_bits - sr)
+                    };
+                    r = ui128{
+                        0,
+                        GetHigh(lhs) >> (sr - n_udword_bits)
+                    };
+                }
+            }
+            else
+            {
+                /* K X
+                * ---
+                * K K
+                */
+                sr = CountLeadingZeroBits(GetHigh(rhs)) - CountLeadingZeroBits(GetHigh(lhs));
+                /*0 <= sr <= n_udword_bits - 1 or sr large */
+                if (sr > n_udword_bits - 1)
+                {
+                    if (rem) {
+                        *rem = lhs;
+                    }
+                    if (quo) {
+                        *quo = 0;
+                    }
+                    return;
+                }
+                ++sr;
+                /* 1 <= sr <= n_udword_bits
+                * q.all = n.all << (n_utword_bits - sr);
+                * r.all = n.all >> sr;
+                */
+                if (sr == n_udword_bits)
+                {
+                    q = ui128{
+                        GetLow(lhs),
+                        0
+                    };
+                    r = ui128{
+                        0,
+                        GetHigh(lhs)
+                    };
+                }
+                else
+                {
+                    r = ui128{
+                        GetHigh(lhs) >> sr,
+                        (GetHigh(lhs) << (n_udword_bits - sr)) | (GetLow(lhs) >> sr)
+                    };
+                    q = ui128{
+                        GetLow(lhs) << (n_udword_bits - sr),
+                        0
+                    };
+                }
+            }
+        }
+        /* Not a special case
+         * q and r are initialized with:
+         * q = n << (128 - sr);
+         * r = n >> sr;
+         * 1 <= sr <= 128 - 1
+         */
+        ui32 carry = 0;
+        for (; sr > 0; --sr)
+        {
+            /* r:q = ((r:q)  << 1) | carry */
+            r = ui128{
+                (GetHigh(r) << 1) | (GetLow(r)  >> (n_udword_bits - 1)),
+                (GetLow(r)  << 1) | (GetHigh(q) >> (n_udword_bits - 1))
+            };
+            q = ui128{
+                (GetHigh(q) << 1) | (GetLow(q)  >> (n_udword_bits - 1)),
+                (GetLow(q)  << 1) | carry
+            };
+            carry = 0;
+            if (r >= rhs) {
+                r -= rhs;
+                carry = 1;
+            }
+        }
+        q = (q << 1) | carry;
+        if (rem) {
+            *rem = r;
+        }
+        if (quo) {
+            *quo = q;
+        }
+    }
+
+    struct TSignedDivisionResult {
+        i128 Quotient;
+        i128 Remainder;
+    };
+
+    constexpr TSignedDivisionResult Divide(i128 lhs, i128 rhs) noexcept;
+}
+
+constexpr ui128 operator/(const ui128 lhs, const ui128 rhs) noexcept {
+    ui128 quotient{};
+    NPrivateInt128::DivMod128(lhs, rhs, &quotient, nullptr);
+    return quotient;
+}
+
+constexpr i128 operator/(const i128 lhs, const i128 rhs) noexcept {
+    i128 a = std::abs(lhs);
+    i128 b = std::abs(rhs);
+
+    ui128 quotient{};
+    NPrivateInt128::DivMod128(a, b, &quotient, nullptr);
+    if (std::signbit(lhs) ^ std::signbit(rhs)) {
+        quotient = -quotient;
+    }
+    return quotient;
+}
+
+constexpr ui128 operator%(const ui128 lhs, const ui128 rhs) noexcept {
+    ui128 remainder{};
+    NPrivateInt128::DivMod128(lhs, rhs, nullptr, &remainder);
+    return remainder;
+}
+
+constexpr i128 operator%(const i128 lhs, const i128 rhs) noexcept {
+    i128 a = std::abs(lhs);
+    i128 b = std::abs(rhs);
+    ui128 remainder{};
+    NPrivateInt128::DivMod128(a, b, nullptr, &remainder);
+    if (std::signbit(lhs)) {
+        remainder = -remainder;
+    }
+    return remainder;
+}
+
+constexpr ui128 operator<<(const ui128 lhs, int n) noexcept {
+    if (n < 64) {
+        if (n != 0) {
+            return
+                ui128{
+                    (GetHigh(lhs) << n) | (GetLow(lhs) >> (64 - n)),
+                    GetLow(lhs) << n
+                };
+        }
+        return lhs;
+    }
+    return ui128{GetLow(lhs) << (n - 64), 0};
+}
+
+constexpr ui128 operator>>(const ui128 lhs, int n) noexcept {
+    if (n < 64) {
+        if (n != 0) {
+            return
+                ui128{
+                    GetHigh(lhs) >> n,
+                    (GetLow(lhs) >> n) | (GetHigh(lhs) << (64 - n))
+                };
+        }
+        return lhs;
+    }
+    return ui128{0, GetHigh(lhs) >> (n - 64)};
+}
+
+
+constexpr bool operator!(const ui128 num) noexcept {
+    return !GetHigh(num) && !GetLow(num);
+}
+
+constexpr ui128 operator~(const ui128 num) noexcept {
+    return ui128{~GetHigh(num), ~GetLow(num)};
+}
+
+constexpr ui128 operator|(const ui128 lhs, const ui128 rhs) noexcept {
+    return ui128{GetHigh(lhs) | GetHigh(rhs), GetLow(lhs) | GetLow(rhs)};
+}
+
+constexpr ui128 operator&(const ui128 lhs, const ui128 rhs) noexcept {
+    return ui128{GetHigh(lhs) & GetHigh(rhs), GetLow(lhs) & GetLow(rhs)};
+}
+
+constexpr  ui128 operator^(const ui128 lhs, const ui128 rhs) noexcept {
+    return ui128{GetHigh(lhs) ^ GetHigh(rhs), GetLow(lhs) ^ GetLow(rhs)};
+}
+
+
+IOutputStream& operator<<(IOutputStream& out, const ui128& other);
+
+// For THashMap
+template <>
+struct THash<ui128> {
+    inline size_t operator()(const ui128& num) const {
+        return THash<ui64>()(GetHigh(num)) + THash<ui64>()(GetLow(num));
+    }
+};
+
+template <>
+class TSerializer<ui128> {
+public:
+    static void Save(IOutputStream* out, const ui128& Number);
+    static void Load(IInputStream* in, ui128& Number);
+};
+
+template <>
+inline TString ToString<ui128>(const ui128& number) {
+    return TStringBuilder{} << number;
+}
+
+template <>
+inline ui128 FromStringImpl<ui128>(const char* data, size_t length) {
+    if (length < 20) {
+        return ui128{ FromString<ui64>(data, length) };
+    } else {
+        ui128 result = 0;
+        const TStringBuf string(data, length);
+        for (auto&& c : string) {
+            if (!std::isdigit(c)) {
                 ythrow TFromStringException() << "Unexpected symbol \""sv << c << "\""sv;
-            } 
- 
-            ui128 x1 = result; 
-            ui128 x2 = x1 + x1; 
-            ui128 x4 = x2 + x2; 
-            ui128 x8 = x4 + x4; 
-            ui128 x10 = x8 + x2; 
-            ui128 s = c - '0'; 
-            result = x10 + s; 
- 
-            if (GetHigh(result) < GetHigh(x1)) { 
+            }
+
+            ui128 x1 = result;
+            ui128 x2 = x1 + x1;
+            ui128 x4 = x2 + x2;
+            ui128 x8 = x4 + x4;
+            ui128 x10 = x8 + x2;
+            ui128 s = c - '0';
+            result = x10 + s;
+
+            if (GetHigh(result) < GetHigh(x1)) {
                 ythrow TFromStringException() << TStringBuf("Integer overflow");
-            } 
-        } 
- 
-        return result; 
-    } 
-} 
- 
-#if defined(Y_HAVE_INT128) 
-template <> 
-inline TString ToString<unsigned __int128>(const unsigned __int128& number) { 
-    return ToString(ui128{number}); 
-} 
- 
-template <> 
-inline unsigned __int128 FromStringImpl<unsigned __int128>(const char* data, size_t length) { 
-    return static_cast<unsigned __int128>(FromString<ui128>(data, length)); 
-} 
-#endif 
- 
-// operators 
- 
- 
-namespace NPrivateInt128 { 
-    // very naive algorithm of division 
-    // no contract for divide by zero (i.e. it is UB) (may be changed in future) 
-    constexpr TSignedDivisionResult Divide(i128 lhs, i128 rhs) noexcept { 
-        TSignedDivisionResult result {}; 
- 
-        // check trivial cases 
-        // X/0 = +/- inf, X%0 = X 
-        if (rhs == 0) { 
-            // UB, let's return: `X / 0 = +inf`, and `X % 0 = X` 
-            result.Quotient = std::signbit(lhs) ? std::numeric_limits<i128>::min() : std::numeric_limits<i128>::max(); 
-            result.Remainder = lhs; 
-        } 
- 
-        // 0/Y = 0, 0%Y = 0 
-        else if (lhs == 0) { 
-            result.Quotient = 0; 
-            result.Remainder = 0; 
-        } 
- 
-        // X/1 = X, X%1 = 0 
-        else if (rhs == 1) { 
-            result.Quotient = lhs; 
-            result.Remainder = 0; 
-        } 
- 
-        // X/-1 = -X, X%(-1) = 0 
-        else if (rhs == -1) { 
-            result.Quotient = -lhs; 
-            result.Remainder = 0; 
-        } 
- 
-        // abs(X)<abs(Y), X/Y = 0, X%Y = X 
-        else if (std::abs(lhs) < std::abs(rhs)) { 
-            result.Quotient = 0; 
-            result.Remainder = lhs; 
-        } 
- 
-        else if (lhs == rhs) { 
-            result.Quotient = 1; 
-            result.Remainder = 0; 
-        } 
- 
-        else if (lhs == -rhs) { 
-            result.Quotient = -1; 
-            result.Remainder = 0; 
-        } 
- 
-        else if (std::abs(lhs) > std::abs(rhs)) { 
-            const bool quotientMustBeNegative = std::signbit(lhs) ^ std::signbit(rhs); 
-            const bool remainderMustBeNegative = std::signbit(lhs); 
- 
-            lhs = std::abs(lhs); 
-            rhs = std::abs(rhs); 
- 
-            // result is division of two ui64 
-            if (GetHigh(lhs) == 0 && GetHigh(rhs) == 0) { 
-                result.Quotient = GetLow(lhs) / GetLow(rhs); 
-                result.Remainder = GetLow(lhs) % GetLow(rhs); 
-            } 
- 
-            // naive shift-and-subtract 
-            // https://stackoverflow.com/questions/5386377/division-without-using 
-            i128 denominator = rhs; 
-            result.Quotient = 0; 
-            result.Remainder = lhs; 
- 
-            const size_t shift = MostSignificantBit(lhs) - MostSignificantBit(denominator); 
-            denominator <<= shift; 
- 
-            for (size_t i = 0; i <= shift; ++i) { 
-                result.Quotient <<= 1; 
-                if (result.Remainder >= denominator) { 
-                    result.Remainder -= denominator; 
-                    result.Quotient |= 1; 
-                } 
-                denominator >>= 1; 
-            } 
- 
-            if (quotientMustBeNegative) { 
-                result.Quotient = -result.Quotient; 
-            } 
- 
-            if (remainderMustBeNegative) { 
-                result.Remainder = -result.Remainder; 
-            } 
-        } 
- 
-        return result; 
-    } 
-} // namespace NPrivateInt128 
- 
-constexpr i128 operator<<(const i128 lhs, int n) noexcept { 
-    if (n < 64) { 
-        if (n != 0) { 
-            return 
-                i128{ 
-                    (GetHigh(lhs) << n) | (GetLow(lhs) >> (64 - n)), 
-                    GetLow(lhs) << n 
-                }; 
-        } 
-        return lhs; 
-    } 
-    return i128{GetLow(lhs) << (n - 64), 0}; 
-} 
- 
-constexpr i128 operator>>(const i128 lhs, int n) noexcept { 
-    if (n < 64) { 
-        if (n != 0) { 
-            return 
-                i128{ 
-                    GetHigh(lhs) >> n, 
-                    (GetLow(lhs) >> n) | (GetHigh(lhs) << (64 - n)) 
-                }; 
-        } 
-        return lhs; 
-    } 
-    return i128{0, GetHigh(lhs) >> (n - 64)}; 
-} 
- 
-constexpr bool operator!(const i128 num) noexcept { 
-    return !GetHigh(num) && !GetLow(num); 
-} 
- 
-constexpr i128 operator~(const i128 num) noexcept { 
-    return i128{~GetHigh(num), ~GetLow(num)}; 
-} 
- 
-constexpr i128 operator|(const i128 lhs, const i128 rhs) noexcept { 
-    return i128{GetHigh(lhs) | GetHigh(rhs), GetLow(lhs) | GetLow(rhs)}; 
-} 
- 
-constexpr i128 operator&(const i128 lhs, const i128 rhs) noexcept { 
-    return i128{GetHigh(lhs) & GetHigh(rhs), GetLow(lhs) & GetLow(rhs)}; 
-} 
- 
-constexpr i128 operator^(const i128 lhs, const i128 rhs) noexcept { 
-    return i128{GetHigh(lhs) ^ GetHigh(rhs), GetLow(lhs) ^ GetLow(rhs)}; 
-} 
- 
- 
-IOutputStream& operator<<(IOutputStream& out, const i128& other); 
- 
-// For THashMap 
-template <> 
-struct THash<i128> { 
-    inline size_t operator()(const i128& num) const { 
-        return THash<ui64>()(GetHigh(num)) + THash<ui64>()(GetLow(num)); 
-    } 
-}; 
- 
-template <> 
-class TSerializer<i128> { 
-public: 
-    static void Save(IOutputStream* out, const i128& Number); 
-    static void Load(IInputStream* in, i128& Number); 
-}; 
- 
-template <> 
-inline TString ToString<i128>(const i128& number) { 
-    return TStringBuilder{} << number; 
-} 
- 
-template <> 
-inline i128 FromStringImpl<i128>(const char* data, size_t length) { 
-    if (length < 20) { 
-        return i128{ FromString<ui64>(data, length) }; 
-    } else { 
-        i128 result = 0; 
-        const TStringBuf string(data, length); 
-        for (auto&& c : string) { 
-            if (!std::isdigit(c)) { 
+            }
+        }
+
+        return result;
+    }
+}
+
+#if defined(Y_HAVE_INT128)
+template <>
+inline TString ToString<unsigned __int128>(const unsigned __int128& number) {
+    return ToString(ui128{number});
+}
+
+template <>
+inline unsigned __int128 FromStringImpl<unsigned __int128>(const char* data, size_t length) {
+    return static_cast<unsigned __int128>(FromString<ui128>(data, length));
+}
+#endif
+
+// operators
+
+
+namespace NPrivateInt128 {
+    // very naive algorithm of division
+    // no contract for divide by zero (i.e. it is UB) (may be changed in future)
+    constexpr TSignedDivisionResult Divide(i128 lhs, i128 rhs) noexcept {
+        TSignedDivisionResult result {};
+
+        // check trivial cases
+        // X/0 = +/- inf, X%0 = X
+        if (rhs == 0) {
+            // UB, let's return: `X / 0 = +inf`, and `X % 0 = X`
+            result.Quotient = std::signbit(lhs) ? std::numeric_limits<i128>::min() : std::numeric_limits<i128>::max();
+            result.Remainder = lhs;
+        }
+
+        // 0/Y = 0, 0%Y = 0
+        else if (lhs == 0) {
+            result.Quotient = 0;
+            result.Remainder = 0;
+        }
+
+        // X/1 = X, X%1 = 0
+        else if (rhs == 1) {
+            result.Quotient = lhs;
+            result.Remainder = 0;
+        }
+
+        // X/-1 = -X, X%(-1) = 0
+        else if (rhs == -1) {
+            result.Quotient = -lhs;
+            result.Remainder = 0;
+        }
+
+        // abs(X)<abs(Y), X/Y = 0, X%Y = X
+        else if (std::abs(lhs) < std::abs(rhs)) {
+            result.Quotient = 0;
+            result.Remainder = lhs;
+        }
+
+        else if (lhs == rhs) {
+            result.Quotient = 1;
+            result.Remainder = 0;
+        }
+
+        else if (lhs == -rhs) {
+            result.Quotient = -1;
+            result.Remainder = 0;
+        }
+
+        else if (std::abs(lhs) > std::abs(rhs)) {
+            const bool quotientMustBeNegative = std::signbit(lhs) ^ std::signbit(rhs);
+            const bool remainderMustBeNegative = std::signbit(lhs);
+
+            lhs = std::abs(lhs);
+            rhs = std::abs(rhs);
+
+            // result is division of two ui64
+            if (GetHigh(lhs) == 0 && GetHigh(rhs) == 0) {
+                result.Quotient = GetLow(lhs) / GetLow(rhs);
+                result.Remainder = GetLow(lhs) % GetLow(rhs);
+            }
+
+            // naive shift-and-subtract
+            // https://stackoverflow.com/questions/5386377/division-without-using
+            i128 denominator = rhs;
+            result.Quotient = 0;
+            result.Remainder = lhs;
+
+            const size_t shift = MostSignificantBit(lhs) - MostSignificantBit(denominator);
+            denominator <<= shift;
+
+            for (size_t i = 0; i <= shift; ++i) {
+                result.Quotient <<= 1;
+                if (result.Remainder >= denominator) {
+                    result.Remainder -= denominator;
+                    result.Quotient |= 1;
+                }
+                denominator >>= 1;
+            }
+
+            if (quotientMustBeNegative) {
+                result.Quotient = -result.Quotient;
+            }
+
+            if (remainderMustBeNegative) {
+                result.Remainder = -result.Remainder;
+            }
+        }
+
+        return result;
+    }
+} // namespace NPrivateInt128
+
+constexpr i128 operator<<(const i128 lhs, int n) noexcept {
+    if (n < 64) {
+        if (n != 0) {
+            return
+                i128{
+                    (GetHigh(lhs) << n) | (GetLow(lhs) >> (64 - n)),
+                    GetLow(lhs) << n
+                };
+        }
+        return lhs;
+    }
+    return i128{GetLow(lhs) << (n - 64), 0};
+}
+
+constexpr i128 operator>>(const i128 lhs, int n) noexcept {
+    if (n < 64) {
+        if (n != 0) {
+            return
+                i128{
+                    GetHigh(lhs) >> n,
+                    (GetLow(lhs) >> n) | (GetHigh(lhs) << (64 - n))
+                };
+        }
+        return lhs;
+    }
+    return i128{0, GetHigh(lhs) >> (n - 64)};
+}
+
+constexpr bool operator!(const i128 num) noexcept {
+    return !GetHigh(num) && !GetLow(num);
+}
+
+constexpr i128 operator~(const i128 num) noexcept {
+    return i128{~GetHigh(num), ~GetLow(num)};
+}
+
+constexpr i128 operator|(const i128 lhs, const i128 rhs) noexcept {
+    return i128{GetHigh(lhs) | GetHigh(rhs), GetLow(lhs) | GetLow(rhs)};
+}
+
+constexpr i128 operator&(const i128 lhs, const i128 rhs) noexcept {
+    return i128{GetHigh(lhs) & GetHigh(rhs), GetLow(lhs) & GetLow(rhs)};
+}
+
+constexpr i128 operator^(const i128 lhs, const i128 rhs) noexcept {
+    return i128{GetHigh(lhs) ^ GetHigh(rhs), GetLow(lhs) ^ GetLow(rhs)};
+}
+
+
+IOutputStream& operator<<(IOutputStream& out, const i128& other);
+
+// For THashMap
+template <>
+struct THash<i128> {
+    inline size_t operator()(const i128& num) const {
+        return THash<ui64>()(GetHigh(num)) + THash<ui64>()(GetLow(num));
+    }
+};
+
+template <>
+class TSerializer<i128> {
+public:
+    static void Save(IOutputStream* out, const i128& Number);
+    static void Load(IInputStream* in, i128& Number);
+};
+
+template <>
+inline TString ToString<i128>(const i128& number) {
+    return TStringBuilder{} << number;
+}
+
+template <>
+inline i128 FromStringImpl<i128>(const char* data, size_t length) {
+    if (length < 20) {
+        return i128{ FromString<ui64>(data, length) };
+    } else {
+        i128 result = 0;
+        const TStringBuf string(data, length);
+        for (auto&& c : string) {
+            if (!std::isdigit(c)) {
                 ythrow TFromStringException() << "Unexpected symbol \""sv << c << "\""sv;
-            } 
- 
-            i128 x1 = result; 
-            i128 x2 = x1 + x1; 
-            i128 x4 = x2 + x2; 
-            i128 x8 = x4 + x4; 
-            i128 x10 = x8 + x2; 
-            i128 s = c - '0'; 
-            result = x10 + s; 
- 
-            if (GetHigh(result) < GetHigh(x1)) { 
+            }
+
+            i128 x1 = result;
+            i128 x2 = x1 + x1;
+            i128 x4 = x2 + x2;
+            i128 x8 = x4 + x4;
+            i128 x10 = x8 + x2;
+            i128 s = c - '0';
+            result = x10 + s;
+
+            if (GetHigh(result) < GetHigh(x1)) {
                 ythrow TFromStringException() << TStringBuf("Integer overflow");
-            } 
-        } 
- 
-        return result; 
-    } 
-} 
- 
-#if defined(Y_HAVE_INT128) 
-template <> 
-inline TString ToString<signed __int128>(const signed __int128& number) { 
-    return ToString(i128{number}); 
-} 
- 
-template <> 
-inline signed __int128 FromStringImpl<signed __int128>(const char* data, size_t length) { 
-    return static_cast<signed __int128>(FromString<i128>(data, length)); 
-} 
-#endif 
- 
-template <bool IsSigned> 
-Y_FORCE_INLINE size_t MostSignificantBit(const TInteger128<IsSigned> v) { 
-    if (ui64 hi = GetHigh(v)) { 
-        return MostSignificantBit(hi) + 64; 
-    } 
-    return MostSignificantBit(GetLow(v)); 
-} 
+            }
+        }
+
+        return result;
+    }
+}
+
+#if defined(Y_HAVE_INT128)
+template <>
+inline TString ToString<signed __int128>(const signed __int128& number) {
+    return ToString(i128{number});
+}
+
+template <>
+inline signed __int128 FromStringImpl<signed __int128>(const char* data, size_t length) {
+    return static_cast<signed __int128>(FromString<i128>(data, length));
+}
+#endif
+
+template <bool IsSigned>
+Y_FORCE_INLINE size_t MostSignificantBit(const TInteger128<IsSigned> v) {
+    if (ui64 hi = GetHigh(v)) {
+        return MostSignificantBit(hi) + 64;
+    }
+    return MostSignificantBit(GetLow(v));
+}