library PRBMathUD60x18 {
	/// @dev Half the SCALE number.
	uint256 internal constant HALF_SCALE = 5e17;

	/// @dev log2(e) as an unsigned 60.18-decimal fixed-point number.
	uint256 internal constant LOG2_E = 1_442695040888963407;

	/// @dev The maximum value an unsigned 60.18-decimal fixed-point number can have.
	uint256 internal constant MAX_UD60x18 =
		115792089237316195423570985008687907853269984665640564039457_584007913129639935;

	/// @dev The maximum whole value an unsigned 60.18-decimal fixed-point number can have.
	uint256 internal constant MAX_WHOLE_UD60x18 =
		115792089237316195423570985008687907853269984665640564039457_000000000000000000;

	/// @dev How many trailing decimals can be represented.
	uint256 internal constant SCALE = 1e18;

	/// @notice Calculates the arithmetic average of x and y, rounding down.
	/// @param x The first operand as an unsigned 60.18-decimal fixed-point number.
	/// @param y The second operand as an unsigned 60.18-decimal fixed-point number.
	/// @return result The arithmetic average as an unsigned 60.18-decimal fixed-point number.
	function avg(uint256 x, uint256 y) internal pure returns (uint256 result) {
		// The operations can never overflow.
		unchecked {
			// The last operand checks if both x and y are odd and if that is the case, we add 1 to the result. We need
			// to do this because if both numbers are odd, the 0.5 remainder gets truncated twice.
			result = (x >> 1) + (y >> 1) + (x & y & 1);
		}
	}

	/// @notice Yields the least unsigned 60.18 decimal fixed-point number greater than or equal to x.
	///
	/// @dev Optimized for fractional value inputs, because for every whole value there are (1e18 - 1) fractional counterparts.
	/// See https://en.wikipedia.org/wiki/Floor_and_ceiling_functions.
	///
	/// Requirements:
	/// - x must be less than or equal to MAX_WHOLE_UD60x18.
	///
	/// @param x The unsigned 60.18-decimal fixed-point number to ceil.
	/// @param result The least integer greater than or equal to x, as an unsigned 60.18-decimal fixed-point number.
	function ceil(uint256 x) internal pure returns (uint256 result) {
		if (x > MAX_WHOLE_UD60x18) {
			revert PRBMathUD60x18__CeilOverflow(x);
		}
		assembly {
			// Equivalent to "x % SCALE" but faster.
			let remainder := mod(x, SCALE)

			// Equivalent to "SCALE - remainder" but faster.
			let delta := sub(SCALE, remainder)

			// Equivalent to "x + delta * (remainder > 0 ? 1 : 0)" but faster.
			result := add(x, mul(delta, gt(remainder, 0)))
		}
	}

	/// @notice Divides two unsigned 60.18-decimal fixed-point numbers, returning a new unsigned 60.18-decimal fixed-point number.
	///
	/// @dev Uses mulDiv to enable overflow-safe multiplication and division.
	///
	/// Requirements:
	/// - The denominator cannot be zero.
	///
	/// @param x The numerator as an unsigned 60.18-decimal fixed-point number.
	/// @param y The denominator as an unsigned 60.18-decimal fixed-point number.
	/// @param result The quotient as an unsigned 60.18-decimal fixed-point number.
	function div(uint256 x, uint256 y) internal pure returns (uint256 result) {
		result = PRBMath.mulDiv(x, SCALE, y);
	}

	/// @notice Returns Euler's number as an unsigned 60.18-decimal fixed-point number.
	/// @dev See https://en.wikipedia.org/wiki/E_(mathematical_constant).
	function e() internal pure returns (uint256 result) {
		result = 2_718281828459045235;
	}

	/// @notice Calculates the natural exponent of x.
	///
	/// @dev Based on the insight that e^x = 2^(x * log2(e)).
	///
	/// Requirements:
	/// - All from "log2".
	/// - x must be less than 133.084258667509499441.
	///
	/// @param x The exponent as an unsigned 60.18-decimal fixed-point number.
	/// @return result The result as an unsigned 60.18-decimal fixed-point number.
	function exp(uint256 x) internal pure returns (uint256 result) {
		// Without this check, the value passed to "exp2" would be greater than 192.
		if (x >= 133_084258667509499441) {
			revert PRBMathUD60x18__ExpInputTooBig(x);
		}

		// Do the fixed-point multiplication inline to save gas.
		unchecked {
			uint256 doubleScaleProduct = x * LOG2_E;
			result = exp2((doubleScaleProduct + HALF_SCALE) / SCALE);
		}
	}

	/// @notice Calculates the binary exponent of x using the binary fraction method.
	///
	/// @dev See https://ethereum.stackexchange.com/q/79903/24693.
	///
	/// Requirements:
	/// - x must be 192 or less.
	/// - The result must fit within MAX_UD60x18.
	///
	/// @param x The exponent as an unsigned 60.18-decimal fixed-point number.
	/// @return result The result as an unsigned 60.18-decimal fixed-point number.
	function exp2(uint256 x) internal pure returns (uint256 result) {
		// 2^192 doesn't fit within the 192.64-bit format used internally in this function.
		if (x >= 192e18) {
			revert PRBMathUD60x18__Exp2InputTooBig(x);
		}

		unchecked {
			// Convert x to the 192.64-bit fixed-point format.
			uint256 x192x64 = (x << 64) / SCALE;

			// Pass x to the PRBMath.exp2 function, which uses the 192.64-bit fixed-point number representation.
			result = PRBMath.exp2(x192x64);
		}
	}

	/// @notice Yields the greatest unsigned 60.18 decimal fixed-point number less than or equal to x.
	/// @dev Optimized for fractional value inputs, because for every whole value there are (1e18 - 1) fractional counterparts.
	/// See https://en.wikipedia.org/wiki/Floor_and_ceiling_functions.
	/// @param x The unsigned 60.18-decimal fixed-point number to floor.
	/// @param result The greatest integer less than or equal to x, as an unsigned 60.18-decimal fixed-point number.
	function floor(uint256 x) internal pure returns (uint256 result) {
		assembly {
			// Equivalent to "x % SCALE" but faster.
			let remainder := mod(x, SCALE)

			// Equivalent to "x - remainder * (remainder > 0 ? 1 : 0)" but faster.
			result := sub(x, mul(remainder, gt(remainder, 0)))
		}
	}

	/// @notice Yields the excess beyond the floor of x.
	/// @dev Based on the odd function definition https://en.wikipedia.org/wiki/Fractional_part.
	/// @param x The unsigned 60.18-decimal fixed-point number to get the fractional part of.
	/// @param result The fractional part of x as an unsigned 60.18-decimal fixed-point number.
	function frac(uint256 x) internal pure returns (uint256 result) {
		assembly {
			result := mod(x, SCALE)
		}
	}

	/// @notice Converts a number from basic integer form to unsigned 60.18-decimal fixed-point representation.
	///
	/// @dev Requirements:
	/// - x must be less than or equal to MAX_UD60x18 divided by SCALE.
	///
	/// @param x The basic integer to convert.
	/// @param result The same number in unsigned 60.18-decimal fixed-point representation.
	function fromUint(uint256 x) internal pure returns (uint256 result) {
		unchecked {
			if (x > MAX_UD60x18 / SCALE) {
				revert PRBMathUD60x18__FromUintOverflow(x);
			}
			result = x * SCALE;
		}
	}

	/// @notice Calculates geometric mean of x and y, i.e. sqrt(x * y), rounding down.
	///
	/// @dev Requirements:
	/// - x * y must fit within MAX_UD60x18, lest it overflows.
	///
	/// @param x The first operand as an unsigned 60.18-decimal fixed-point number.
	/// @param y The second operand as an unsigned 60.18-decimal fixed-point number.
	/// @return result The result as an unsigned 60.18-decimal fixed-point number.
	function gm(uint256 x, uint256 y) internal pure returns (uint256 result) {
		if (x == 0) {
			return 0;
		}

		unchecked {
			// Checking for overflow this way is faster than letting Solidity do it.
			uint256 xy = x * y;
			if (xy / x != y) {
				revert PRBMathUD60x18__GmOverflow(x, y);
			}

			// We don't need to multiply by the SCALE here because the x*y product had already picked up a factor of SCALE
			// during multiplication. See the comments within the "sqrt" function.
			result = PRBMath.sqrt(xy);
		}
	}

	/// @notice Calculates 1 / x, rounding toward zero.
	///
	/// @dev Requirements:
	/// - x cannot be zero.
	///
	/// @param x The unsigned 60.18-decimal fixed-point number for which to calculate the inverse.
	/// @return result The inverse as an unsigned 60.18-decimal fixed-point number.
	function inv(uint256 x) internal pure returns (uint256 result) {
		unchecked {
			// 1e36 is SCALE * SCALE.
			result = 1e36 / x;
		}
	}

	/// @notice Calculates the natural logarithm of x.
	///
	/// @dev Based on the insight that ln(x) = log2(x) / log2(e).
	///
	/// Requirements:
	/// - All from "log2".
	///
	/// Caveats:
	/// - All from "log2".
	/// - This doesn't return exactly 1 for 2.718281828459045235, for that we would need more fine-grained precision.
	///
	/// @param x The unsigned 60.18-decimal fixed-point number for which to calculate the natural logarithm.
	/// @return result The natural logarithm as an unsigned 60.18-decimal fixed-point number.
	function ln(uint256 x) internal pure returns (uint256 result) {
		// Do the fixed-point multiplication inline to save gas. This is overflow-safe because the maximum value that log2(x)
		// can return is 196205294292027477728.
		unchecked {
			result = (log2(x) * SCALE) / LOG2_E;
		}
	}

	/// @notice Calculates the common logarithm of x.
	///
	/// @dev First checks if x is an exact power of ten and it stops if yes. If it's not, calculates the common
	/// logarithm based on the insight that log10(x) = log2(x) / log2(10).
	///
	/// Requirements:
	/// - All from "log2".
	///
	/// Caveats:
	/// - All from "log2".
	///
	/// @param x The unsigned 60.18-decimal fixed-point number for which to calculate the common logarithm.
	/// @return result The common logarithm as an unsigned 60.18-decimal fixed-point number.
	function log10(uint256 x) internal pure returns (uint256 result) {
		if (x < SCALE) {
			revert PRBMathUD60x18__LogInputTooSmall(x);
		}

		// Note that the "mul" in this block is the assembly multiplication operation, not the "mul" function defined
		// in this contract.
		// prettier-ignore
		assembly {
			switch x
			case 1 { result := mul(SCALE, sub(0, 18)) }
			case 10 { result := mul(SCALE, sub(1, 18)) }
			case 100 { result := mul(SCALE, sub(2, 18)) }
			case 1000 { result := mul(SCALE, sub(3, 18)) }
			case 10000 { result := mul(SCALE, sub(4, 18)) }
			case 100000 { result := mul(SCALE, sub(5, 18)) }
			case 1000000 { result := mul(SCALE, sub(6, 18)) }
			case 10000000 { result := mul(SCALE, sub(7, 18)) }
			case 100000000 { result := mul(SCALE, sub(8, 18)) }
			case 1000000000 { result := mul(SCALE, sub(9, 18)) }
			case 10000000000 { result := mul(SCALE, sub(10, 18)) }
			case 100000000000 { result := mul(SCALE, sub(11, 18)) }
			case 1000000000000 { result := mul(SCALE, sub(12, 18)) }
			case 10000000000000 { result := mul(SCALE, sub(13, 18)) }
			case 100000000000000 { result := mul(SCALE, sub(14, 18)) }
			case 1000000000000000 { result := mul(SCALE, sub(15, 18)) }
			case 10000000000000000 { result := mul(SCALE, sub(16, 18)) }
			case 100000000000000000 { result := mul(SCALE, sub(17, 18)) }
			case 1000000000000000000 { result := 0 }
			case 10000000000000000000 { result := SCALE }
			case 100000000000000000000 { result := mul(SCALE, 2) }
			case 1000000000000000000000 { result := mul(SCALE, 3) }
			case 10000000000000000000000 { result := mul(SCALE, 4) }
			case 100000000000000000000000 { result := mul(SCALE, 5) }
			case 1000000000000000000000000 { result := mul(SCALE, 6) }
			case 10000000000000000000000000 { result := mul(SCALE, 7) }
			case 100000000000000000000000000 { result := mul(SCALE, 8) }
			case 1000000000000000000000000000 { result := mul(SCALE, 9) }
			case 10000000000000000000000000000 { result := mul(SCALE, 10) }
			case 100000000000000000000000000000 { result := mul(SCALE, 11) }
			case 1000000000000000000000000000000 { result := mul(SCALE, 12) }
			case 10000000000000000000000000000000 { result := mul(SCALE, 13) }
			case 100000000000000000000000000000000 { result := mul(SCALE, 14) }
			case 1000000000000000000000000000000000 { result := mul(SCALE, 15) }
			case 10000000000000000000000000000000000 { result := mul(SCALE, 16) }
			case 100000000000000000000000000000000000 { result := mul(SCALE, 17) }
			case 1000000000000000000000000000000000000 { result := mul(SCALE, 18) }
			case 10000000000000000000000000000000000000 { result := mul(SCALE, 19) }
			case 100000000000000000000000000000000000000 { result := mul(SCALE, 20) }
			case 1000000000000000000000000000000000000000 { result := mul(SCALE, 21) }
			case 10000000000000000000000000000000000000000 { result := mul(SCALE, 22) }
			case 100000000000000000000000000000000000000000 { result := mul(SCALE, 23) }
			case 1000000000000000000000000000000000000000000 { result := mul(SCALE, 24) }
			case 10000000000000000000000000000000000000000000 { result := mul(SCALE, 25) }
			case 100000000000000000000000000000000000000000000 { result := mul(SCALE, 26) }
			case 1000000000000000000000000000000000000000000000 { result := mul(SCALE, 27) }
			case 10000000000000000000000000000000000000000000000 { result := mul(SCALE, 28) }
			case 100000000000000000000000000000000000000000000000 { result := mul(SCALE, 29) }
			case 1000000000000000000000000000000000000000000000000 { result := mul(SCALE, 30) }
			case 10000000000000000000000000000000000000000000000000 { result := mul(SCALE, 31) }
			case 100000000000000000000000000000000000000000000000000 { result := mul(SCALE, 32) }
			case 1000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 33) }
			case 10000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 34) }
			case 100000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 35) }
			case 1000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 36) }
			case 10000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 37) }
			case 100000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 38) }
			case 1000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 39) }
			case 10000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 40) }
			case 100000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 41) }
			case 1000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 42) }
			case 10000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 43) }
			case 100000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 44) }
			case 1000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 45) }
			case 10000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 46) }
			case 100000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 47) }
			case 1000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 48) }
			case 10000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 49) }
			case 100000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 50) }
			case 1000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 51) }
			case 10000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 52) }
			case 100000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 53) }
			case 1000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 54) }
			case 10000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 55) }
			case 100000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 56) }
			case 1000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 57) }
			case 10000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 58) }
			case 100000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(SCALE, 59) }
			default {
				result := MAX_UD60x18
			}
		}

		if (result == MAX_UD60x18) {
			// Do the fixed-point division inline to save gas. The denominator is log2(10).
			unchecked {
				result = (log2(x) * SCALE) / 3_321928094887362347;
			}
		}
	}

	/// @notice Calculates the binary logarithm of x.
	///
	/// @dev Based on the iterative approximation algorithm.
	/// https://en.wikipedia.org/wiki/Binary_logarithm#Iterative_approximation
	///
	/// Requirements:
	/// - x must be greater than or equal to SCALE, otherwise the result would be negative.
	///
	/// Caveats:
	/// - The results are nor perfectly accurate to the last decimal, due to the lossy precision of the iterative approximation.
	///
	/// @param x The unsigned 60.18-decimal fixed-point number for which to calculate the binary logarithm.
	/// @return result The binary logarithm as an unsigned 60.18-decimal fixed-point number.
	function log2(uint256 x) internal pure returns (uint256 result) {
		if (x < SCALE) {
			revert PRBMathUD60x18__LogInputTooSmall(x);
		}
		unchecked {
			// Calculate the integer part of the logarithm and add it to the result and finally calculate y = x * 2^(-n).
			uint256 n = PRBMath.mostSignificantBit(x / SCALE);

			// The integer part of the logarithm as an unsigned 60.18-decimal fixed-point number. The operation can't overflow
			// because n is maximum 255 and SCALE is 1e18.
			result = n * SCALE;

			// This is y = x * 2^(-n).
			uint256 y = x >> n;

			// If y = 1, the fractional part is zero.
			if (y == SCALE) {
				return result;
			}

			// Calculate the fractional part via the iterative approximation.
			// The "delta >>= 1" part is equivalent to "delta /= 2", but shifting bits is faster.
			for (uint256 delta = HALF_SCALE; delta > 0; delta >>= 1) {
				y = (y * y) / SCALE;

				// Is y^2 > 2 and so in the range [2,4)?
				if (y >= 2 * SCALE) {
					// Add the 2^(-m) factor to the logarithm.
					result += delta;

					// Corresponds to z/2 on Wikipedia.
					y >>= 1;
				}
			}
		}
	}

	/// @notice Multiplies two unsigned 60.18-decimal fixed-point numbers together, returning a new unsigned 60.18-decimal
	/// fixed-point number.
	/// @dev See the documentation for the "PRBMath.mulDivFixedPoint" function.
	/// @param x The multiplicand as an unsigned 60.18-decimal fixed-point number.
	/// @param y The multiplier as an unsigned 60.18-decimal fixed-point number.
	/// @return result The product as an unsigned 60.18-decimal fixed-point number.
	function mul(uint256 x, uint256 y) internal pure returns (uint256 result) {
		result = PRBMath.mulDivFixedPoint(x, y);
	}

	/// @notice Returns PI as an unsigned 60.18-decimal fixed-point number.
	function pi() internal pure returns (uint256 result) {
		result = 3_141592653589793238;
	}

	/// @notice Raises x to the power of y.
	///
	/// @dev Based on the insight that x^y = 2^(log2(x) * y).
	///
	/// Requirements:
	/// - All from "exp2", "log2" and "mul".
	///
	/// Caveats:
	/// - All from "exp2", "log2" and "mul".
	/// - Assumes 0^0 is 1.
	///
	/// @param x Number to raise to given power y, as an unsigned 60.18-decimal fixed-point number.
	/// @param y Exponent to raise x to, as an unsigned 60.18-decimal fixed-point number.
	/// @return result x raised to power y, as an unsigned 60.18-decimal fixed-point number.
	function pow(uint256 x, uint256 y) internal pure returns (uint256 result) {
		if (x == 0) {
			result = y == 0 ? SCALE : uint256(0);
		} else {
			result = exp2(mul(log2(x), y));
		}
	}

	/// @notice Raises x (unsigned 60.18-decimal fixed-point number) to the power of y (basic unsigned integer) using the
	/// famous algorithm "exponentiation by squaring".
	///
	/// @dev See https://en.wikipedia.org/wiki/Exponentiation_by_squaring
	///
	/// Requirements:
	/// - The result must fit within MAX_UD60x18.
	///
	/// Caveats:
	/// - All from "mul".
	/// - Assumes 0^0 is 1.
	///
	/// @param x The base as an unsigned 60.18-decimal fixed-point number.
	/// @param y The exponent as an uint256.
	/// @return result The result as an unsigned 60.18-decimal fixed-point number.
	function powu(uint256 x, uint256 y) internal pure returns (uint256 result) {
		// Calculate the first iteration of the loop in advance.
		result = y & 1 > 0 ? x : SCALE;

		// Equivalent to "for(y /= 2; y > 0; y /= 2)" but faster.
		for (y >>= 1; y > 0; y >>= 1) {
			x = PRBMath.mulDivFixedPoint(x, x);

			// Equivalent to "y % 2 == 1" but faster.
			if (y & 1 > 0) {
				result = PRBMath.mulDivFixedPoint(result, x);
			}
		}
	}

	/// @notice Returns 1 as an unsigned 60.18-decimal fixed-point number.
	function scale() internal pure returns (uint256 result) {
		result = SCALE;
	}

	/// @notice Calculates the square root of x, rounding down.
	/// @dev Uses the Babylonian method https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method.
	///
	/// Requirements:
	/// - x must be less than MAX_UD60x18 / SCALE.
	///
	/// @param x The unsigned 60.18-decimal fixed-point number for which to calculate the square root.
	/// @return result The result as an unsigned 60.18-decimal fixed-point .
	function sqrt(uint256 x) internal pure returns (uint256 result) {
		unchecked {
			if (x > MAX_UD60x18 / SCALE) {
				revert PRBMathUD60x18__SqrtOverflow(x);
			}
			// Multiply x by the SCALE to account for the factor of SCALE that is picked up when multiplying two unsigned
			// 60.18-decimal fixed-point numbers together (in this case, those two numbers are both the square root).
			result = PRBMath.sqrt(x * SCALE);
		}
	}

	/// @notice Converts a unsigned 60.18-decimal fixed-point number to basic integer form, rounding down in the process.
	/// @param x The unsigned 60.18-decimal fixed-point number to convert.
	/// @return result The same number in basic integer form.
	function toUint(uint256 x) internal pure returns (uint256 result) {
		unchecked {
			result = x / SCALE;
		}
	}
}
/// @title PRBMathUD60x18
/// @author Paul Razvan Berg
/// @notice Smart contract library for advanced fixed-point math that works with uint256 numbers considered to have 18
/// trailing decimals. We call this number representation unsigned 60.18-decimal fixed-point, since there can be up to 60
/// digits in the integer part and up to 18 decimals in the fractional part. The numbers are bound by the minimum and the
/// maximum values permitted by the Solidity type uint256.
function scale() internal pure returns (uint256 result) {
	result = SCALE;
}

/// @notice Returns 1 as an unsigned 60.18-decimal fixed-point number.