Contract 0xda57aaf912619bf10e8e585e932e20d941269733 1

// SPDX-License-Identifier: BUSL-1.1
pragma solidity =0.8.9;
pragma abicoder v2;

import "@openzeppelin/contracts/utils/Context.sol";
import "@openzeppelin/contracts/utils/math/Math.sol";
import "@openzeppelin/contracts/utils/math/SafeCast.sol";
import "@openzeppelin/contracts/token/ERC20/IERC20.sol";
import "@openzeppelin/contracts/token/ERC20/utils/SafeERC20.sol";
import "./interfaces/IGrid.sol";
import "./interfaces/IWETHMinimum.sol";
import "./interfaces/callback/IGridSwapCallback.sol";
import "./interfaces/callback/IGridPlaceMakerOrderCallback.sol";
import "./interfaces/callback/IGridFlashCallback.sol";
import "./interfaces/IGridEvents.sol";
import "./interfaces/IGridStructs.sol";
import "./interfaces/IGridParameters.sol";
import "./interfaces/IGridDeployer.sol";
import "./interfaces/IPriceOracle.sol";
import "./libraries/BoundaryMath.sol";
import "./libraries/BoundaryBitmap.sol";
import "./libraries/BundleMath.sol";
import "./libraries/Uint128Math.sol";
import "./libraries/Uint160Math.sol";
import "./libraries/SwapMath.sol";

/// @title The implementation of a Gridex grid
contract Grid is IGrid, IGridStructs, IGridEvents, IGridParameters, Context {
    using SafeCast for uint256;
    using BoundaryBitmap for mapping(int16 => uint256);
    using BundleMath for Bundle;

    address public immutable override token0;
    address public immutable override token1;
    int24 public immutable override resolution;

    address private immutable weth9;
    address private immutable priceOracle;

    int24 public immutable takerFee;

    Slot0 public override slot0;

    mapping(int24 => Boundary) public override boundaries0;
    mapping(int24 => Boundary) public override boundaries1;
    mapping(int16 => uint256) public override boundaryBitmaps0;
    mapping(int16 => uint256) public override boundaryBitmaps1;

    uint256 private _orderId;
    mapping(uint256 => Order) public override orders;

    uint64 private _bundleId;
    mapping(uint64 => Bundle) public override bundles;

    mapping(address => TokensOwed) public override tokensOweds;

    /// @dev Used to receive Ether when settling and collecting orders
    receive() external payable {}

    constructor() {
        (token0, token1, resolution, takerFee, priceOracle, weth9) = IGridDeployer(_msgSender()).parameters();
    }

    modifier lock() {
        // G_PL: Grid locked
        require(slot0.unlocked, "G_GL");
        slot0.unlocked = false;
        _;
        slot0.unlocked = true;
    }

    /// @inheritdoc IGrid
    function initialize(
        InitializeParameters memory parameters,
        bytes calldata data
    ) external override returns (uint256[] memory orderIds0, uint256[] memory orderIds1) {
        // G_GAI: grid already initialized
        require(slot0.priceX96 == 0, "G_GAI");
        // G_POR: price out of range
        require(BoundaryMath.isPriceX96InRange(parameters.priceX96), "G_POR");
        // G_T0OE: token0 orders must be non-empty
        require(parameters.orders0.length > 0, "G_ONE");
        // G_T1OE: token1 orders must be non-empty
        require(parameters.orders1.length > 0, "G_ONE");

        IPriceOracle(priceOracle).register(token0, token1, resolution);

        int24 boundary = BoundaryMath.getBoundaryAtPriceX96(parameters.priceX96);
        slot0 = Slot0({
            priceX96: parameters.priceX96,
            boundary: boundary,
            blockTimestamp: uint32(block.timestamp),
            unlocked: false // still keep the grid locked to prevent reentrancy
        });
        // emits an Initialize event before placing orders
        emit Initialize(parameters.priceX96, boundary);

        // places orders for token0 and token1
        uint256 amount0Total;
        (orderIds0, amount0Total) = _placeMakerOrderInBatch(parameters.recipient, true, parameters.orders0);
        uint256 amount1Total;
        (orderIds1, amount1Total) = _placeMakerOrderInBatch(parameters.recipient, false, parameters.orders1);
        (uint256 balance0Before, uint256 balance1Before) = (_balance0(), _balance1());

        IGridPlaceMakerOrderCallback(_msgSender()).gridexPlaceMakerOrderCallback(amount0Total, amount1Total, data);

        (uint256 balance0After, uint256 balance1After) = (_balance0(), _balance1());
        // G_TPF: token pay failed
        require(
            balance0After - balance0Before >= amount0Total && balance1After - balance1Before >= amount1Total,
            "G_TPF"
        );

        slot0.unlocked = true;
    }

    /// @inheritdoc IGrid
    function placeMakerOrder(
        PlaceOrderParameters memory parameters,
        bytes calldata data
    ) external override lock returns (uint256 orderId) {
        orderId = _nextOrderId();

        _processPlaceOrder(orderId, parameters.recipient, parameters.zero, parameters.boundaryLower, parameters.amount);

        _processPlaceOrderReceiveAndCallback(parameters.zero, parameters.amount, data);
    }

    /// @inheritdoc IGrid
    function placeMakerOrderInBatch(
        PlaceOrderInBatchParameters memory parameters,
        bytes calldata data
    ) external override lock returns (uint256[] memory orderIds) {
        uint256 amountTotal;
        (orderIds, amountTotal) = _placeMakerOrderInBatch(parameters.recipient, parameters.zero, parameters.orders);
        _processPlaceOrderReceiveAndCallback(parameters.zero, amountTotal, data);
    }

    function _placeMakerOrderInBatch(
        address recipient,
        bool zero,
        BoundaryLowerWithAmountParameters[] memory parameters
    ) private returns (uint256[] memory orderIds, uint256 amountTotal) {
        orderIds = new uint256[](parameters.length);
        uint256 orderId = _nextOrderIdInBatch(parameters.length);

        for (uint256 i = 0; i < parameters.length; ) {
            BoundaryLowerWithAmountParameters memory each = parameters[i];

            _processPlaceOrder(orderId, recipient, zero, each.boundaryLower, each.amount);
            orderIds[i] = orderId;

            unchecked {
                // next order id
                orderId++;
                i++;
            }

            amountTotal += each.amount;
        }
    }

    function _processPlaceOrder(
        uint256 orderId,
        address recipient,
        bool zero,
        int24 boundaryLower,
        uint128 amount
    ) private {
        // G_OAZ: order amount is zero
        require(amount > 0, "G_OAZ");
        // G_IBL: invalid boundary lower
        require(
            boundaryLower >= BoundaryMath.MIN_BOUNDARY &&
                boundaryLower + resolution <= BoundaryMath.MAX_BOUNDARY &&
                BoundaryMath.isValidBoundary(boundaryLower, resolution),
            "G_IBL"
        );

        // updates the boundary
        Boundary storage boundary = _boundaryAt(boundaryLower, zero);
        Bundle storage bundle;
        uint64 bundleId = boundary.bundle1Id;
        // 1. If bundle1 has been initialized, add the order to bundle1 directly
        // 2. If bundle0 is not initialized, add the order to bundle0 after initialization
        // 3. If bundle0 has been initialized, and bundle0 has been used,
        //    then bundle1 is initialized and the order is added to bundle1, otherwise, it is added to bundle0
        if (bundleId > 0) {
            bundle = bundles[bundleId];
            bundle.addLiquidity(amount);
        } else {
            uint64 bundle0Id = boundary.bundle0Id;
            if (bundle0Id == 0) {
                // initializes new bundle
                (bundleId, bundle) = _nextBundle(boundaryLower, zero);
                boundary.bundle0Id = bundleId;

                bundle.makerAmountTotal = amount;
                bundle.makerAmountRemaining = amount;
            } else {
                bundleId = bundle0Id;
                bundle = bundles[bundleId];

                uint128 makerAmountTotal = bundle.makerAmountTotal;
                uint128 makerAmountRemaining = bundle.makerAmountRemaining;

                if (makerAmountRemaining < makerAmountTotal) {
                    // initializes new bundle
                    (bundleId, bundle) = _nextBundle(boundaryLower, zero);
                    boundary.bundle1Id = bundleId;

                    bundle.makerAmountTotal = amount;
                    bundle.makerAmountRemaining = amount;
                } else {
                    bundle.addLiquidityWithAmount(makerAmountTotal, makerAmountRemaining, amount);
                }
            }
        }

        // saves order
        orders[orderId] = Order({owner: recipient, bundleId: bundleId, amount: amount});
        emit PlaceMakerOrder(orderId, recipient, bundleId, zero, boundaryLower, amount);

        // If the current boundary has no liquidity, it must be flipped
        uint128 makerAmountRemainingForBoundary = boundary.makerAmountRemaining;

        if (makerAmountRemainingForBoundary == 0) _flipBoundary(boundaryLower, zero);

        boundary.makerAmountRemaining = makerAmountRemainingForBoundary + amount;
    }

    function _processPlaceOrderReceiveAndCallback(bool zero, uint256 amount, bytes calldata data) private {
        // tokens to be received
        (address tokenToReceive, uint256 amount0, uint256 amount1) = zero
            ? (token0, amount, uint256(0))
            : (token1, uint256(0), amount);
        uint256 balanceBefore = IERC20(tokenToReceive).balanceOf(address(this));
        IGridPlaceMakerOrderCallback(_msgSender()).gridexPlaceMakerOrderCallback(amount0, amount1, data);
        uint256 balanceAfter = IERC20(tokenToReceive).balanceOf(address(this));
        // G_TPF: token pay failed
        require(balanceAfter - balanceBefore >= amount, "G_TPF");
    }

    /// @inheritdoc IGrid
    function swap(
        address recipient,
        bool zeroForOne,
        int256 amountSpecified,
        uint160 priceLimitX96,
        bytes calldata data
    ) external override returns (int256 amount0, int256 amount1) {
        // G_ASZ: amount specified cannot be zero
        require(amountSpecified != 0, "G_ASZ");

        Slot0 memory slot0Cache = slot0;
        // G_PL: Grid locked
        require(slot0Cache.unlocked, "G_GL");
        // G_PLO: price limit over range
        require(zeroForOne ? priceLimitX96 < slot0Cache.priceX96 : priceLimitX96 > slot0Cache.priceX96, "G_PLO");

        // we lock the grid before swap
        slot0.unlocked = false;

        SwapState memory state = SwapState({
            zeroForOne: zeroForOne,
            amountSpecifiedRemaining: amountSpecified,
            amountInputCalculated: 0,
            feeAmountInputCalculated: 0,
            amountOutputCalculated: 0,
            priceX96: slot0Cache.priceX96,
            priceLimitX96: priceLimitX96,
            boundary: slot0Cache.boundary,
            boundaryLower: BoundaryMath.getBoundaryLowerAtBoundary(slot0Cache.boundary, resolution),
            initializedBoundaryLowerPriceX96: 0,
            initializedBoundaryUpperPriceX96: 0,
            stopSwap: false
        });

        mapping(int16 => uint256) storage counterBoundaryBitmap = _boundaryBitmaps(!zeroForOne);
        mapping(int24 => Boundary) storage counterBoundaries = _boundaries(!zeroForOne);
        while (state.amountSpecifiedRemaining != 0 && !state.stopSwap) {
            int24 boundaryNext;
            bool initialized;
            (
                boundaryNext,
                initialized,
                state.initializedBoundaryLowerPriceX96,
                state.initializedBoundaryUpperPriceX96
            ) = counterBoundaryBitmap.nextInitializedBoundary(
                state.boundary,
                state.priceX96,
                counterBoundaries[state.boundaryLower].makerAmountRemaining > 0,
                resolution,
                state.boundaryLower,
                state.zeroForOne
            );
            if (!initialized) break;

            // swap for boundary
            state.stopSwap = _processSwapForBoundary(counterBoundaryBitmap, counterBoundaries, boundaryNext, state);
        }

        // updates slot0
        if (state.priceX96 != slot0Cache.priceX96) {
            state.boundary = BoundaryMath.getBoundaryAtPriceX96(state.priceX96);
            uint32 blockTimestamp;
            // We only update the oracle in the first transaction of each block, using only the boundary
            // before the update to improve the security of the oracle
            if (
                slot0Cache.boundary != state.boundary &&
                slot0Cache.blockTimestamp != (blockTimestamp = uint32(block.timestamp))
            ) {
                IPriceOracle(priceOracle).update(slot0Cache.boundary, blockTimestamp);
                slot0.blockTimestamp = blockTimestamp;
            }

            (slot0.priceX96, slot0.boundary) = (state.priceX96, state.boundary);
        }

        (amount0, amount1) = _processTransferForSwap(state, recipient, data);
        emit Swap(_msgSender(), recipient, amount0, amount1, state.priceX96, state.boundary);

        // we unlock the grid after swap
        slot0.unlocked = true;
    }

    /// @dev Process swap for a given boundary
    /// @param counterBoundaryBitmap The boundary bitmap of the opposite side. When zeroForOne is true,
    /// it is the boundary bitmap of token1, otherwise it is the boundary bitmap of token0
    /// @param counterBoundaries The boundary of the opposite side. When zeroForOne is true,
    /// it is the boundary of token1, otherwise it is the boundary of token0
    /// @param boundaryNext The next boundary where liquidity exists
    /// @param state The state of the swap
    /// @return stopSwap stopSwap = true if the amount of swapped out is 0,
    /// or when the specified price limit is reached
    function _processSwapForBoundary(
        mapping(int16 => uint256) storage counterBoundaryBitmap,
        mapping(int24 => Boundary) storage counterBoundaries,
        int24 boundaryNext,
        SwapState memory state
    ) private returns (bool stopSwap) {
        SwapForBoundaryState memory swapForBoundaryState = SwapForBoundaryState({
            boundaryLowerPriceX96: state.initializedBoundaryLowerPriceX96,
            boundaryUpperPriceX96: state.initializedBoundaryUpperPriceX96,
            boundaryPriceX96: 0,
            priceX96: 0
        });
        // resets the current priceX96 to the price range
        (swapForBoundaryState.boundaryPriceX96, swapForBoundaryState.priceX96) = state.zeroForOne
            ? (
                swapForBoundaryState.boundaryLowerPriceX96,
                Uint160Math.minUint160(swapForBoundaryState.boundaryUpperPriceX96, state.priceX96)
            )
            : (
                swapForBoundaryState.boundaryUpperPriceX96,
                Uint160Math.maxUint160(swapForBoundaryState.boundaryLowerPriceX96, state.priceX96)
            );

        // when the price has reached the specified price limit, swapping stops
        if (
            (state.zeroForOne && swapForBoundaryState.priceX96 <= state.priceLimitX96) ||
            (!state.zeroForOne && swapForBoundaryState.priceX96 >= state.priceLimitX96)
        ) {
            return true;
        }

        Boundary storage boundary = counterBoundaries[boundaryNext];
        SwapMath.ComputeSwapStep memory step = SwapMath.computeSwapStep(
            swapForBoundaryState.priceX96,
            swapForBoundaryState.boundaryPriceX96,
            state.priceLimitX96,
            state.amountSpecifiedRemaining,
            boundary.makerAmountRemaining,
            takerFee
        );
        // when the amount of swapped out tokens is 0, swapping stops
        if (step.amountOut == 0) return true;

        // updates taker amount input and fee amount input
        state.amountInputCalculated = state.amountInputCalculated + step.amountIn;
        state.feeAmountInputCalculated = state.feeAmountInputCalculated + step.feeAmount;
        state.amountOutputCalculated = state.amountOutputCalculated + step.amountOut;
        state.amountSpecifiedRemaining = state.amountSpecifiedRemaining < 0
            ? state.amountSpecifiedRemaining + int256(uint256(step.amountOut))
            : state.amountSpecifiedRemaining - step.amountIn.toInt256() - int256(uint256(step.feeAmount));

        {
            Bundle storage bundle0 = bundles[boundary.bundle0Id];
            UpdateBundleForTakerParameters memory parameters = bundle0.updateForTaker(
                step.amountIn,
                step.amountOut,
                step.feeAmount
            );
            emit ChangeBundleForSwap(
                boundary.bundle0Id,
                -int256(uint256(parameters.amountOutUsed)),
                parameters.amountInUsed,
                parameters.takerFeeForMakerAmountUsed
            );

            // bundle0 has been fully filled
            if (bundle0.makerAmountRemaining == 0) {
                _activateBundle1(boundary);

                if (parameters.amountOutRemaining > 0) {
                    Bundle storage bundle1 = bundles[boundary.bundle0Id];
                    parameters = bundle1.updateForTaker(
                        parameters.amountInRemaining,
                        parameters.amountOutRemaining,
                        parameters.takerFeeForMakerAmountRemaining
                    );
                    emit ChangeBundleForSwap(
                        boundary.bundle0Id,
                        -int256(uint256(parameters.amountOutUsed)),
                        parameters.amountInUsed,
                        parameters.takerFeeForMakerAmountUsed
                    );
                    // bundle1 has been fully filled
                    if (bundle1.makerAmountRemaining == 0) {
                        _activateBundle1(boundary);
                    }
                }
            }
        }

        // updates remaining maker amount
        uint128 makerAmountRemaining;
        unchecked {
            makerAmountRemaining = boundary.makerAmountRemaining - step.amountOut;
        }
        boundary.makerAmountRemaining = makerAmountRemaining;
        // this boundary has been fully filled
        if (makerAmountRemaining == 0) counterBoundaryBitmap.flipBoundary(boundaryNext, resolution);

        state.priceX96 = step.priceNextX96;
        // when the price has reached the specified lower price, the boundary should equal to boundaryNext,
        // otherwise swapping stops and the boundary is recomputed
        state.boundary = boundaryNext;
        state.boundaryLower = boundaryNext;

        return false;
    }

    function _processTransferForSwap(
        SwapState memory state,
        address recipient,
        bytes calldata data
    ) private returns (int256 amount0, int256 amount1) {
        uint256 amountInputTotal = state.amountInputCalculated + state.feeAmountInputCalculated;
        uint256 amountOutputTotal = state.amountOutputCalculated;
        address tokenToPay;
        address tokenToReceive;
        (tokenToPay, tokenToReceive, amount0, amount1) = state.zeroForOne
            ? (token1, token0, SafeCast.toInt256(amountInputTotal), -SafeCast.toInt256(amountOutputTotal))
            : (token0, token1, -SafeCast.toInt256(amountOutputTotal), SafeCast.toInt256(amountInputTotal));

        // pays token to recipient
        SafeERC20.safeTransfer(IERC20(tokenToPay), recipient, amountOutputTotal);

        uint256 balanceBefore = IERC20(tokenToReceive).balanceOf(address(this));
        // receives token
        IGridSwapCallback(_msgSender()).gridexSwapCallback(amount0, amount1, data);
        uint256 balanceAfter = IERC20(tokenToReceive).balanceOf(address(this));
        // G_TRF: token to receive failed
        require(balanceAfter - balanceBefore >= amountInputTotal, "G_TRF");
    }

    /// @inheritdoc IGrid
    function settleMakerOrder(uint256 orderId) external override lock returns (uint128 amount0, uint128 amount1) {
        (amount0, amount1) = _settleMakerOrder(orderId);

        TokensOwed storage tokensOwed = tokensOweds[_msgSender()];
        if (amount0 > 0) tokensOwed.token0 = tokensOwed.token0 + amount0;
        if (amount1 > 0) tokensOwed.token1 = tokensOwed.token1 + amount1;
    }

    function _settleMakerOrder(uint256 orderId) private returns (uint128 amount0, uint128 amount1) {
        (bool zero, uint128 makerAmountOut, uint128 takerAmountOut, uint128 takerFeeAmountOut) = _processSettleOrder(
            orderId
        );
        (amount0, amount1) = zero
            ? (makerAmountOut, takerAmountOut + takerFeeAmountOut)
            : (takerAmountOut + takerFeeAmountOut, makerAmountOut);
    }

    /// @inheritdoc IGrid
    function settleMakerOrderAndCollect(
        address recipient,
        uint256 orderId,
        bool unwrapWETH9
    ) external override lock returns (uint128 amount0, uint128 amount1) {
        (amount0, amount1) = _settleMakerOrder(orderId);

        _collect(recipient, amount0, amount1, unwrapWETH9);
    }

    /// @inheritdoc IGrid
    function settleMakerOrderAndCollectInBatch(
        address recipient,
        uint256[] memory orderIds,
        bool unwrapWETH9
    ) external override lock returns (uint128 amount0Total, uint128 amount1Total) {
        (amount0Total, amount1Total) = _settleMakerOrderInBatch(orderIds);

        _collect(recipient, amount0Total, amount1Total, unwrapWETH9);
    }

    function _settleMakerOrderInBatch(
        uint256[] memory orderIds
    ) private returns (uint128 amount0Total, uint128 amount1Total) {
        for (uint256 i = 0; i < orderIds.length; i++) {
            (
                bool zero,
                uint128 makerAmountOut,
                uint128 takerAmountOut,
                uint128 takerFeeAmountOut
            ) = _processSettleOrder(orderIds[i]);
            (amount0Total, amount1Total) = zero
                ? (amount0Total + makerAmountOut, amount1Total + takerAmountOut + takerFeeAmountOut)
                : (amount0Total + takerAmountOut + takerFeeAmountOut, amount1Total + makerAmountOut);
        }
    }

    function _processSettleOrder(
        uint256 orderId
    ) private returns (bool zero, uint128 makerAmountOut, uint128 takerAmountOut, uint128 takerFeeAmountOut) {
        Order memory order = orders[orderId];
        // G_COO: caller is not the order owner
        require(order.owner == _msgSender(), "G_COO");

        // deletes order from storage
        delete orders[orderId];

        Bundle storage bundle = bundles[order.bundleId];
        zero = bundle.zero;

        uint128 makerAmountTotalNew;
        (makerAmountOut, takerAmountOut, takerFeeAmountOut, makerAmountTotalNew) = bundle.removeLiquidity(order.amount);

        emit ChangeBundleForSettleOrder(
            order.bundleId,
            -int256(uint256(order.amount)),
            -int256(uint256(makerAmountOut))
        );

        // removes liquidity from boundary
        Boundary storage boundary = _boundaryAt(bundle.boundaryLower, zero);
        uint64 bundle0Id = boundary.bundle0Id;
        if (bundle0Id == order.bundleId || boundary.bundle1Id == order.bundleId) {
            uint128 makerAmountRemaining = boundary.makerAmountRemaining - makerAmountOut;
            boundary.makerAmountRemaining = makerAmountRemaining;
            // all bundle liquidity is removed
            if (makerAmountTotalNew == 0) {
                // when the liquidity of bundle0 is fully removed:
                // 1. Activate directly when bundle1 has been initialized
                // 2. Reuse bundle0 to save gas
                if (bundle0Id == order.bundleId && boundary.bundle1Id > 0) _activateBundle1(boundary);
                if (makerAmountRemaining == 0) _flipBoundary(bundle.boundaryLower, zero);
            }
        }

        emit SettleMakerOrder(orderId, makerAmountOut, takerAmountOut, takerFeeAmountOut);
    }

    function _collect(address recipient, uint128 amount0, uint128 amount1, bool unwrapWETH9) private {
        if (amount0 > 0) {
            _collectSingle(recipient, token0, amount0, unwrapWETH9);
        }
        if (amount1 > 0) {
            _collectSingle(recipient, token1, amount1, unwrapWETH9);
        }
        emit Collect(_msgSender(), recipient, amount0, amount1);
    }

    function _collectSingle(address recipient, address token, uint128 amount, bool unwrapWETH9) private {
        if (unwrapWETH9 && token == weth9) {
            IWETHMinimum(token).withdraw(amount);
            Address.sendValue(payable(recipient), amount);
        } else {
            SafeERC20.safeTransfer(IERC20(token), recipient, amount);
        }
    }

    /// @inheritdoc IGrid
    function flash(address recipient, uint256 amount0, uint256 amount1, bytes calldata data) external override lock {
        uint256 balance0Before;
        uint256 balance1Before;

        if (amount0 > 0) {
            balance0Before = _balance0();
            SafeERC20.safeTransfer(IERC20(token0), recipient, amount0);
        }
        if (amount1 > 0) {
            balance1Before = _balance1();
            SafeERC20.safeTransfer(IERC20(token1), recipient, amount1);
        }

        IGridFlashCallback(_msgSender()).gridexFlashCallback(data);

        uint128 paid0;
        uint128 paid1;
        if (amount0 > 0) {
            uint256 balance0After = _balance0();
            paid0 = (balance0After - balance0Before).toUint128();
        }
        if (amount1 > 0) {
            uint256 balance1After = _balance1();
            paid1 = (balance1After - balance1Before).toUint128();
        }

        emit Flash(_msgSender(), recipient, amount0, amount1, paid0, paid1);
    }

    /// @inheritdoc IGrid
    function collect(
        address recipient,
        uint128 amount0Requested,
        uint128 amount1Requested
    ) external override lock returns (uint128 amount0, uint128 amount1) {
        (amount0, amount1) = _collectOwed(tokensOweds[_msgSender()], recipient, amount0Requested, amount1Requested);

        emit Collect(_msgSender(), recipient, amount0, amount1);
    }

    function _collectOwed(
        TokensOwed storage tokensOwed,
        address recipient,
        uint128 amount0Requested,
        uint128 amount1Requested
    ) private returns (uint128 amount0, uint128 amount1) {
        if (amount0Requested > 0) {
            amount0 = Uint128Math.minUint128(amount0Requested, tokensOwed.token0);
            unchecked {
                tokensOwed.token0 = tokensOwed.token0 - amount0;
            }

            SafeERC20.safeTransfer(IERC20(token0), recipient, amount0);
        }
        if (amount1Requested > 0) {
            amount1 = Uint128Math.minUint128(amount1Requested, tokensOwed.token1);
            unchecked {
                tokensOwed.token1 = tokensOwed.token1 - amount1;
            }
            SafeERC20.safeTransfer(IERC20(token1), recipient, amount1);
        }
    }

    function _balance0() private view returns (uint256) {
        return IERC20(token0).balanceOf(address(this));
    }

    function _balance1() private view returns (uint256) {
        return IERC20(token1).balanceOf(address(this));
    }

    /// @dev Returns the next order id
    function _nextOrderId() private returns (uint256 orderId) {
        orderId = ++_orderId;
    }

    /// @dev Returns the next order id in a given batch
    function _nextOrderIdInBatch(uint256 batch) private returns (uint256 orderId) {
        orderId = _orderId;
        _orderId = orderId + batch;
        unchecked {
            return orderId + 1;
        }
    }

    /// @dev Returns the next bundle id
    function _nextBundleId() private returns (uint64 bundleId) {
        bundleId = ++_bundleId;
    }

    /// @dev Creates and returns the next bundle and its corresponding id
    function _nextBundle(int24 boundaryLower, bool zero) private returns (uint64 bundleId, Bundle storage bundle) {
        bundleId = _nextBundleId();
        bundle = bundles[bundleId];
        bundle.boundaryLower = boundaryLower;
        bundle.zero = zero;
    }

    /// @dev Returns a mapping of the boundaries of either token0 or token1
    function _boundaries(bool zero) private view returns (mapping(int24 => Boundary) storage) {
        return zero ? boundaries0 : boundaries1;
    }

    /// @dev Returns the boundary of token0 or token1
    function _boundaryAt(int24 boundary, bool zero) private view returns (Boundary storage) {
        return zero ? boundaries0[boundary] : boundaries1[boundary];
    }

    /// @dev Flip the boundary of token0 or token1
    function _flipBoundary(int24 boundary, bool zero) private {
        _boundaryBitmaps(zero).flipBoundary(boundary, resolution);
    }

    /// @dev Returns the boundary bitmap of token0 or token1
    function _boundaryBitmaps(bool zero) private view returns (mapping(int16 => uint256) storage) {
        return zero ? boundaryBitmaps0 : boundaryBitmaps1;
    }

    /// @dev Closes bundle0 and activates bundle1
    function _activateBundle1(Boundary storage self) internal {
        self.bundle0Id = self.bundle1Id;
        self.bundle1Id = 0;
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

import "./IGridStructs.sol";
import "./IGridParameters.sol";

/// @title The interface for Gridex grid
interface IGrid {
    ///==================================== Grid States  ====================================

    /// @notice The first token in the grid, after sorting by address
    function token0() external view returns (address);

    /// @notice The second token in the grid, after sorting by address
    function token1() external view returns (address);

    /// @notice The step size in initialized boundaries for a grid created with a given fee
    function resolution() external view returns (int24);

    /// @notice The fee paid to the grid denominated in hundredths of a bip, i.e. 1e-6
    function takerFee() external view returns (int24);

    /// @notice The 0th slot of the grid holds a lot of values that can be gas-efficiently accessed
    /// externally as a single method
    /// @return priceX96 The current price of the grid, as a Q64.96
    /// @return boundary The current boundary of the grid
    /// @return blockTimestamp The time the oracle was last updated
    /// @return unlocked Whether the grid is unlocked or not
    function slot0() external view returns (uint160 priceX96, int24 boundary, uint32 blockTimestamp, bool unlocked);

    /// @notice Returns the boundary information of token0
    /// @param boundary The boundary of the grid
    /// @return bundle0Id The unique identifier of bundle0
    /// @return bundle1Id The unique identifier of bundle1
    /// @return makerAmountRemaining The remaining amount of token0 that can be swapped out,
    /// which is the sum of bundle0 and bundle1
    function boundaries0(
        int24 boundary
    ) external view returns (uint64 bundle0Id, uint64 bundle1Id, uint128 makerAmountRemaining);

    /// @notice Returns the boundary information of token1
    /// @param boundary The boundary of the grid
    /// @return bundle0Id The unique identifier of bundle0
    /// @return bundle1Id The unique identifier of bundle1
    /// @return makerAmountRemaining The remaining amount of token1 that can be swapped out,
    /// which is the sum of bundle0 and bundle1
    function boundaries1(
        int24 boundary
    ) external view returns (uint64 bundle0Id, uint64 bundle1Id, uint128 makerAmountRemaining);

    /// @notice Returns 256 packed boundary initialized boolean values for token0
    function boundaryBitmaps0(int16 wordPos) external view returns (uint256 word);

    /// @notice Returns 256 packed boundary initialized boolean values for token1
    function boundaryBitmaps1(int16 wordPos) external view returns (uint256 word);

    /// @notice Returns the amount owed for token0 and token1
    /// @param owner The address of owner
    /// @return token0 The amount of token0 owed
    /// @return token1 The amount of token1 owed
    function tokensOweds(address owner) external view returns (uint128 token0, uint128 token1);

    /// @notice Returns the information of a given bundle
    /// @param bundleId The unique identifier of the bundle
    /// @return boundaryLower The lower boundary of the bundle
    /// @return zero When zero is true, it represents token0, otherwise it represents token1
    /// @return makerAmountTotal The total amount of token0 or token1 that the maker added
    /// @return makerAmountRemaining The remaining amount of token0 or token1 that can be swapped out from the makers
    /// @return takerAmountRemaining The remaining amount of token0 or token1 that have been swapped in from the takers
    /// @return takerFeeAmountRemaining The remaining amount of fees that takers have paid in
    function bundles(
        uint64 bundleId
    )
        external
        view
        returns (
            int24 boundaryLower,
            bool zero,
            uint128 makerAmountTotal,
            uint128 makerAmountRemaining,
            uint128 takerAmountRemaining,
            uint128 takerFeeAmountRemaining
        );

    /// @notice Returns the information of a given order
    /// @param orderId The unique identifier of the order
    /// @return bundleId The unique identifier of the bundle -- represents which bundle this order belongs to
    /// @return owner The address of the owner of the order
    /// @return amount The amount of token0 or token1 to add
    function orders(uint256 orderId) external view returns (uint64 bundleId, address owner, uint128 amount);

    ///==================================== Grid Actions ====================================

    /// @notice Initializes the grid with the given parameters
    /// @dev The caller of this method receives a callback in the form of
    /// IGridPlaceMakerOrderCallback#gridexPlaceMakerOrderCallback.
    /// When initializing the grid, token0 and token1's liquidity must be added simultaneously.
    /// @param parameters The parameters used to initialize the grid
    /// @param data Any data to be passed through to the callback
    /// @return orderIds0 The unique identifiers of the orders for token0
    /// @return orderIds1 The unique identifiers of the orders for token1
    function initialize(
        IGridParameters.InitializeParameters memory parameters,
        bytes calldata data
    ) external returns (uint256[] memory orderIds0, uint256[] memory orderIds1);

    /// @notice Swaps token0 for token1, or vice versa
    /// @dev The caller of this method receives a callback in the form of IGridSwapCallback#gridexSwapCallback
    /// @param recipient The address to receive the output of the swap
    /// @param zeroForOne The swap direction, true for token0 to token1 and false otherwise
    /// @param amountSpecified The amount of the swap, configured as an exactInput (positive)
    /// or an exactOutput (negative)
    /// @param priceLimitX96 Swap price limit: if zeroForOne, the price will not be less than this value after swap,
    /// if oneForZero, it will not be greater than this value after swap, as a Q64.96
    /// @param data Any data to be passed through to the callback
    /// @return amount0 The balance change of the grid's token0. When negative, it will reduce the balance
    /// by the exact amount. When positive, it will increase by at least this amount
    /// @return amount1 The balance change of the grid's token1. When negative, it will reduce the balance
    /// by the exact amount. When positive, it will increase by at least this amount.
    function swap(
        address recipient,
        bool zeroForOne,
        int256 amountSpecified,
        uint160 priceLimitX96,
        bytes calldata data
    ) external returns (int256 amount0, int256 amount1);

    /// @notice Places a maker order on the grid
    /// @dev The caller of this method receives a callback in the form of
    /// IGridPlaceMakerOrderCallback#gridexPlaceMakerOrderCallback
    /// @param parameters The parameters used to place the maker order
    /// @param data Any data to be passed through to the callback
    /// @return orderId The unique identifier of the order
    function placeMakerOrder(
        IGridParameters.PlaceOrderParameters memory parameters,
        bytes calldata data
    ) external returns (uint256 orderId);

    /// @notice Places maker orders on the grid
    /// @dev The caller of this method receives a callback in the form of
    /// IGridPlaceMakerOrderCallback#gridexPlaceMakerOrderCallback
    /// @param parameters The parameters used to place the maker orders
    /// @param data Any data to be passed through to the callback
    /// @return orderIds The unique identifiers of the orders
    function placeMakerOrderInBatch(
        IGridParameters.PlaceOrderInBatchParameters memory parameters,
        bytes calldata data
    ) external returns (uint256[] memory orderIds);

    /// @notice Settles a maker order
    /// @param orderId The unique identifier of the order
    /// @return amount0 The amount of token0 that the maker received
    /// @return amount1 The amount of token1 that the maker received
    function settleMakerOrder(uint256 orderId) external returns (uint128 amount0, uint128 amount1);

    /// @notice Settle maker order and collect
    /// @param recipient The address to receive the output of the settlement
    /// @param orderId The unique identifier of the order
    /// @param unwrapWETH9 Whether to unwrap WETH9 to ETH
    /// @return amount0 The amount of token0 that the maker received
    /// @return amount1 The amount of token1 that the maker received
    function settleMakerOrderAndCollect(
        address recipient,
        uint256 orderId,
        bool unwrapWETH9
    ) external returns (uint128 amount0, uint128 amount1);

    /// @notice Settles maker orders and collects in a batch
    /// @param recipient The address to receive the output of the settlement
    /// @param orderIds The unique identifiers of the orders
    /// @param unwrapWETH9 Whether to unwrap WETH9 to ETH
    /// @return amount0Total The total amount of token0 that the maker received
    /// @return amount1Total The total amount of token1 that the maker received
    function settleMakerOrderAndCollectInBatch(
        address recipient,
        uint256[] memory orderIds,
        bool unwrapWETH9
    ) external returns (uint128 amount0Total, uint128 amount1Total);

    /// @notice For flash swaps. The caller borrows assets and returns them in the callback of the function,
    /// in addition to a fee
    /// @dev The caller of this function receives a callback in the form of IGridFlashCallback#gridexFlashCallback
    /// @param recipient The address which will receive the token0 and token1
    /// @param amount0 The amount of token0 to receive
    /// @param amount1 The amount of token1 to receive
    /// @param data Any data to be passed through to the callback
    function flash(address recipient, uint256 amount0, uint256 amount1, bytes calldata data) external;

    /// @notice Collects tokens owed
    /// @param recipient The address to receive the collected fees
    /// @param amount0Requested The maximum amount of token0 to send.
    /// Set to 0 if fees should only be collected in token1.
    /// @param amount1Requested The maximum amount of token1 to send.
    /// Set to 0 if fees should only be collected in token0.
    /// @return amount0 The amount of fees collected in token0
    /// @return amount1 The amount of fees collected in token1
    function collect(
        address recipient,
        uint128 amount0Requested,
        uint128 amount1Requested
    ) external returns (uint128 amount0, uint128 amount1);
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

interface IWETHMinimum {
    function deposit() external payable;

    function transfer(address dst, uint256 wad) external returns (bool);

    function withdraw(uint256) external;

    function approve(address guy, uint256 wad) external returns (bool);

    function balanceOf(address dst) external view returns (uint256);
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

/// @title A contract interface for deploying grids
/// @notice A grid constructor must use the interface to pass arguments to the grid
/// @dev This is necessary to ensure there are no constructor arguments in the grid contract.
/// This keeps the grid init code hash constant, allowing a CREATE2 address to be computed on-chain gas-efficiently.
interface IGridDeployer {
    struct Parameters {
        address token0;
        address token1;
        int24 resolution;
        int24 takerFee;
        address priceOracle;
        address weth9;
    }

    /// @notice Returns the grid creation code
    function gridCreationCode() external view returns (bytes memory);

    /// @notice Getter for the arguments used in constructing the grid. These are set locally during grid creation
    /// @dev Retrieves grid parameters, after being called by the grid constructor
    /// @return token0 The first token in the grid, after sorting by address
    /// @return token1 The second token in the grid, after sorting by address
    /// @return resolution The step size in initialized boundaries for a grid created with a given fee
    /// @return takerFee The taker fee, denominated in hundredths of a bip (i.e. 1e-6)
    /// @return priceOracle The address of the price oracle contract
    /// @return weth9 The address of the WETH9 contract
    function parameters()
        external
        view
        returns (
            address token0,
            address token1,
            int24 resolution,
            int24 takerFee,
            address priceOracle,
            address weth9
        );
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

import "./IGridStructs.sol";

/// @title Events emitted by the grid contract
interface IGridEvents {
    /// @notice Emitted exactly once by a grid when #initialize is first called on the grid
    /// @param priceX96 The initial price of the grid, as a Q64.96
    /// @param boundary The initial boundary of the grid
    event Initialize(uint160 priceX96, int24 boundary);

    /// @notice Emitted when the maker places an order to add liquidity for token0 or token1
    /// @param orderId The unique identifier of the order
    /// @param recipient The address that received the order
    /// @param bundleId The unique identifier of the bundle -- represents which bundle this order belongs to
    /// @param zero When zero is true, it represents token0, otherwise it represents token1
    /// @param boundaryLower The lower boundary of the order
    /// @param amount The amount of token0 or token1 to add
    event PlaceMakerOrder(
        uint256 indexed orderId,
        address indexed recipient,
        uint64 indexed bundleId,
        bool zero,
        int24 boundaryLower,
        uint128 amount
    );

    /// @notice Emitted when settling a single range order
    /// @param orderId The unique identifier of the order
    /// @param makerAmountOut The amount of token0 or token1 that the maker has removed
    /// @param takerAmountOut The amount of token0 or token1 that the taker has submitted
    /// @param takerFeeAmountOut The amount of token0 or token1 fees that the taker has paid
    event SettleMakerOrder(
        uint256 indexed orderId,
        uint128 makerAmountOut,
        uint128 takerAmountOut,
        uint128 takerFeeAmountOut
    );

    /// @notice Emitted when a maker settles an order
    /// @dev When either of the bundle's total maker amount or the remaining maker amount becomes 0,
    /// the bundle is closed
    /// @param bundleId The unique identifier of the bundle
    /// @param makerAmountTotal The change in the total maker amount in the bundle
    /// @param makerAmountRemaining The change in the remaining maker amount in the bundle
    event ChangeBundleForSettleOrder(uint64 indexed bundleId, int256 makerAmountTotal, int256 makerAmountRemaining);

    /// @notice Emitted when a taker is swapping
    /// @dev When the bundle's remaining maker amount becomes 0, the bundle is closed
    /// @param bundleId The unique identifier of the bundle
    /// @param makerAmountRemaining The change in the remaining maker amount in the bundle
    /// @param amountIn The change in the remaining taker amount in the bundle
    /// @param takerFeeAmountIn The change in the remaining taker fee amount in the bundle
    event ChangeBundleForSwap(
        uint64 indexed bundleId,
        int256 makerAmountRemaining,
        uint256 amountIn,
        uint128 takerFeeAmountIn
    );

    /// @notice Emitted by the grid for any swaps between token0 and token1
    /// @param sender The address that initiated the swap call, and that received the callback
    /// @param recipient The address that received the output of the swap
    /// @param amount0 The delta of the token0 balance of the grid
    /// @param amount1 The delta of the token1 balance of the grid
    /// @param priceX96 The price of the grid after the swap, as a Q64.96
    /// @param boundary The log base 1.0001 of the price of the grid after the swap
    event Swap(
        address indexed sender,
        address indexed recipient,
        int256 amount0,
        int256 amount1,
        uint160 priceX96,
        int24 boundary
    );

    /// @notice Emitted by the grid for any flashes of token0/token1
    /// @param sender The address that initiated the flash call, and that received the callback
    /// @param recipient The address that received the tokens from the flash
    /// @param amount0 The amount of token0 that was flashed
    /// @param amount1 The amount of token1 that was flashed
    /// @param paid0 The amount of token0 paid for the flash, which can exceed the amount0 plus the fee
    /// @param paid1 The amount of token1 paid for the flash, which can exceed the amount1 plus the fee
    event Flash(
        address indexed sender,
        address indexed recipient,
        uint256 amount0,
        uint256 amount1,
        uint128 paid0,
        uint128 paid1
    );

    /// @notice Emitted when the collected owed fees are withdrawn by the sender
    /// @param sender The address that collects the fees
    /// @param recipient The address that receives the fees
    /// @param amount0 The amount of token0 fees that is withdrawn
    /// @param amount1 The amount of token1 fees that is withdrawn
    event Collect(address indexed sender, address indexed recipient, uint128 amount0, uint128 amount1);
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

library BoundaryMath {
    int24 public constant MIN_BOUNDARY = -527400;
    int24 public constant MAX_BOUNDARY = 443635;

    /// @dev The minimum value that can be returned from #getPriceX96AtBoundary. Equivalent to getPriceX96AtBoundary(MIN_BOUNDARY)
    uint160 internal constant MIN_RATIO = 989314;
    /// @dev The maximum value that can be returned from #getPriceX96AtBoundary. Equivalent to getPriceX96AtBoundary(MAX_BOUNDARY)
    uint160 internal constant MAX_RATIO = 1461300573427867316570072651998408279850435624081;

    /// @dev Checks if a boundary is divisible by a resolution
    /// @param boundary The boundary to check
    /// @param resolution The step size in initialized boundaries for a grid created with a given fee
    /// @return isValid Whether or not the boundary is valid
    function isValidBoundary(int24 boundary, int24 resolution) internal pure returns (bool isValid) {
        return boundary % resolution == 0;
    }

    /// @dev Checks if a boundary is within the valid range
    /// @param boundary The boundary to check
    /// @return inRange Whether or not the boundary is in range
    function isInRange(int24 boundary) internal pure returns (bool inRange) {
        return boundary >= MIN_BOUNDARY && boundary <= MAX_BOUNDARY;
    }

    /// @dev Checks if a price is within the valid range
    /// @param priceX96 The price to check, as a Q64.96
    /// @return inRange Whether or not the price is in range
    function isPriceX96InRange(uint160 priceX96) internal pure returns (bool inRange) {
        return priceX96 >= MIN_RATIO && priceX96 <= MAX_RATIO;
    }

    /// @notice Calculates the price at a given boundary
    /// @dev priceX96 = pow(1.0001, boundary) * 2**96
    /// @param boundary The boundary to calculate the price at
    /// @return priceX96 The price at the boundary, as a Q64.96
    function getPriceX96AtBoundary(int24 boundary) internal pure returns (uint160 priceX96) {
        unchecked {
            uint256 absBoundary = boundary < 0 ? uint256(-int256(boundary)) : uint24(boundary);

            uint256 ratio = absBoundary & 0x1 != 0
                ? 0xfff97272373d413259a46990580e213a
                : 0x100000000000000000000000000000000;
            if (absBoundary & 0x2 != 0) ratio = (ratio * 0xfff2e50f5f656932ef12357cf3c7fdcc) >> 128;
            if (absBoundary & 0x4 != 0) ratio = (ratio * 0xffe5caca7e10e4e61c3624eaa0941cd0) >> 128;
            if (absBoundary & 0x8 != 0) ratio = (ratio * 0xffcb9843d60f6159c9db58835c926644) >> 128;
            if (absBoundary & 0x10 != 0) ratio = (ratio * 0xff973b41fa98c081472e6896dfb254c0) >> 128;
            if (absBoundary & 0x20 != 0) ratio = (ratio * 0xff2ea16466c96a3843ec78b326b52861) >> 128;
            if (absBoundary & 0x40 != 0) ratio = (ratio * 0xfe5dee046a99a2a811c461f1969c3053) >> 128;
            if (absBoundary & 0x80 != 0) ratio = (ratio * 0xfcbe86c7900a88aedcffc83b479aa3a4) >> 128;
            if (absBoundary & 0x100 != 0) ratio = (ratio * 0xf987a7253ac413176f2b074cf7815e54) >> 128;
            if (absBoundary & 0x200 != 0) ratio = (ratio * 0xf3392b0822b70005940c7a398e4b70f3) >> 128;
            if (absBoundary & 0x400 != 0) ratio = (ratio * 0xe7159475a2c29b7443b29c7fa6e889d9) >> 128;
            if (absBoundary & 0x800 != 0) ratio = (ratio * 0xd097f3bdfd2022b8845ad8f792aa5825) >> 128;
            if (absBoundary & 0x1000 != 0) ratio = (ratio * 0xa9f746462d870fdf8a65dc1f90e061e5) >> 128;
            if (absBoundary & 0x2000 != 0) ratio = (ratio * 0x70d869a156d2a1b890bb3df62baf32f7) >> 128;
            if (absBoundary & 0x4000 != 0) ratio = (ratio * 0x31be135f97d08fd981231505542fcfa6) >> 128;
            if (absBoundary & 0x8000 != 0) ratio = (ratio * 0x9aa508b5b7a84e1c677de54f3e99bc9) >> 128;
            if (absBoundary & 0x10000 != 0) ratio = (ratio * 0x5d6af8dedb81196699c329225ee604) >> 128;
            if (absBoundary & 0x20000 != 0) ratio = (ratio * 0x2216e584f5fa1ea926041bedfe98) >> 128;
            if (absBoundary & 0x40000 != 0) ratio = (ratio * 0x48a170391f7dc42444e8fa2) >> 128;
            if (absBoundary & 0x80000 != 0) ratio = (ratio * 0x149b34ee7ac263) >> 128;

            if (boundary > 0) ratio = type(uint256).max / ratio;

            // this divides by 1<<32 and rounds up to go from a Q128.128 to a Q128.96.
            // due to out boundary input limitations, we then proceed to downcast as the
            // result will always fit within 160 bits.
            // we round up in the division so that getBoundaryAtPriceX96 of the output price is always consistent
            priceX96 = uint160((ratio + 0xffffffff) >> 32);
        }
    }

    /// @notice Calculates the boundary at a given price
    /// @param priceX96 The price to calculate the boundary at, as a Q64.96
    /// @return boundary The boundary at the price
    function getBoundaryAtPriceX96(uint160 priceX96) internal pure returns (int24 boundary) {
        unchecked {
            uint256 ratio = uint256(priceX96) << 32;

            uint256 r = ratio;
            uint256 msb = 0;

            assembly {
                let f := shl(7, gt(r, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF))
                msb := or(msb, f)
                r := shr(f, r)
            }
            assembly {
                let f := shl(6, gt(r, 0xFFFFFFFFFFFFFFFF))
                msb := or(msb, f)
                r := shr(f, r)
            }
            assembly {
                let f := shl(5, gt(r, 0xFFFFFFFF))
                msb := or(msb, f)
                r := shr(f, r)
            }
            assembly {
                let f := shl(4, gt(r, 0xFFFF))
                msb := or(msb, f)
                r := shr(f, r)
            }
            assembly {
                let f := shl(3, gt(r, 0xFF))
                msb := or(msb, f)
                r := shr(f, r)
            }
            assembly {
                let f := shl(2, gt(r, 0xF))
                msb := or(msb, f)
                r := shr(f, r)
            }
            assembly {
                let f := shl(1, gt(r, 0x3))
                msb := or(msb, f)
                r := shr(f, r)
            }
            assembly {
                let f := gt(r, 0x1)
                msb := or(msb, f)
            }

            if (msb >= 128) r = ratio >> (msb - 127);
            else r = ratio << (127 - msb);

            int256 log_2 = (int256(msb) - 128) << 64;

            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(63, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(62, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(61, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(60, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(59, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(58, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(57, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(56, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(55, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(54, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(53, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(52, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(51, f))
                r := shr(f, r)
            }
            assembly {
                r := shr(127, mul(r, r))
                let f := shr(128, r)
                log_2 := or(log_2, shl(50, f))
            }

            int256 log10001 = log_2 * 127869479499801913173570;
            // 128.128 number

            int24 boundaryLow = int24((log10001 - 1701496478404566090792001455681771637) >> 128);
            int24 boundaryHi = int24((log10001 + 289637967442836604689790891002483458648) >> 128);

            boundary = boundaryLow == boundaryHi ? boundaryLow : getPriceX96AtBoundary(boundaryHi) <= priceX96
                ? boundaryHi
                : boundaryLow;
        }
    }

    /// @dev Returns the lower boundary for the given boundary and resolution.
    /// The lower boundary may not be valid (if out of the boundary range)
    /// @param boundary The boundary to get the lower boundary for
    /// @param resolution The step size in initialized boundaries for a grid created with a given fee
    /// @return boundaryLower The lower boundary for the given boundary and resolution
    function getBoundaryLowerAtBoundary(int24 boundary, int24 resolution) internal pure returns (int24 boundaryLower) {
        unchecked {
            return boundary - (((boundary % resolution) + resolution) % resolution);
        }
    }

    /// @dev Rewrite the lower boundary that is not in the range to a valid value
    /// @param boundaryLower The lower boundary to rewrite
    /// @param resolution The step size in initialized boundaries for a grid created with a given fee
    /// @return validBoundaryLower The valid lower boundary
    function rewriteToValidBoundaryLower(
        int24 boundaryLower,
        int24 resolution
    ) internal pure returns (int24 validBoundaryLower) {
        unchecked {
            if (boundaryLower < MIN_BOUNDARY) return boundaryLower + resolution;
            else if (boundaryLower + resolution > MAX_BOUNDARY) return boundaryLower - resolution;
            else return boundaryLower;
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

interface IGridStructs {
    struct Bundle {
        int24 boundaryLower;
        bool zero;
        uint128 makerAmountTotal;
        uint128 makerAmountRemaining;
        uint128 takerAmountRemaining;
        uint128 takerFeeAmountRemaining;
    }

    struct Boundary {
        uint64 bundle0Id;
        uint64 bundle1Id;
        uint128 makerAmountRemaining;
    }

    struct Order {
        uint64 bundleId;
        address owner;
        uint128 amount;
    }

    struct TokensOwed {
        uint128 token0;
        uint128 token1;
    }

    struct Slot0 {
        uint160 priceX96;
        int24 boundary;
        uint32 blockTimestamp;
        bool unlocked;
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

import "./BitMath.sol";
import "./BoundaryMath.sol";

library BoundaryBitmap {
    /// @notice Calculates the position of the bit in the bitmap for a given boundary
    /// @param boundary The boundary for calculating the bit position
    /// @return wordPos The key within the mapping that contains the word storing the bit
    /// @return bitPos The bit position in the word where the flag is stored
    function position(int24 boundary) internal pure returns (int16 wordPos, uint8 bitPos) {
        wordPos = int16(boundary >> 8);
        bitPos = uint8(uint24(boundary));
    }

    /// @notice Flips the boolean value of the initialization state of the given boundary
    /// @param self The mapping that stores the initial state of the boundary
    /// @param boundary The boundary to flip
    /// @param resolution The step size in initialized boundaries for a grid created with a given fee
    function flipBoundary(mapping(int16 => uint256) storage self, int24 boundary, int24 resolution) internal {
        require(boundary % resolution == 0);
        (int16 wordPos, uint8 bitPos) = position(boundary / resolution);
        uint256 mask = 1 << bitPos;
        self[wordPos] ^= mask;
    }

    /// @notice Returns the next initialized boundary as the left boundary (less than)
    /// or the right boundary (more than)
    /// @param self The mapping that stores the initial state of the boundary
    /// @param boundary The starting boundary
    /// @param priceX96 Price of the initial boundary, as a Q64.96
    /// @param currentBoundaryInitialized Whether the starting boundary is initialized or not
    /// @param resolution The step size in initialized boundaries for a grid created with a given fee
    /// @param boundaryLower The starting lower boundary of the grid
    /// @param lte Whether or not to search for the next initialized boundary
    /// to the left (less than or equal to the starting boundary)
    /// @return next The next boundary, regardless of initialization state
    /// @return initialized Whether or not the next boundary is initialized
    /// @return initializedBoundaryLowerPriceX96 If the current boundary has been initialized and can be swapped,
    /// return the current left boundary price, otherwise return 0, as a Q64.96
    /// @return initializedBoundaryUpperPriceX96 If the current boundary has been initialized and can be swapped,
    /// return the current right boundary price, otherwise return 0, as a Q64.96
    function nextInitializedBoundary(
        mapping(int16 => uint256) storage self,
        int24 boundary,
        uint160 priceX96,
        bool currentBoundaryInitialized,
        int24 resolution,
        int24 boundaryLower,
        bool lte
    )
        internal
        view
        returns (
            int24 next,
            bool initialized,
            uint160 initializedBoundaryLowerPriceX96,
            uint160 initializedBoundaryUpperPriceX96
        )
    {
        int24 boundaryUpper = boundaryLower + resolution;
        if (currentBoundaryInitialized) {
            if (lte) {
                uint160 boundaryLowerPriceX96 = BoundaryMath.getPriceX96AtBoundary(boundaryLower);
                if (boundaryLowerPriceX96 < priceX96) {
                    return (
                        boundaryLower,
                        true,
                        boundaryLowerPriceX96,
                        BoundaryMath.getPriceX96AtBoundary(boundaryUpper)
                    );
                }
            } else {
                uint160 boundaryUpperPriceX96 = BoundaryMath.getPriceX96AtBoundary(boundaryUpper);
                if (boundaryUpperPriceX96 > priceX96) {
                    return (
                        boundaryLower,
                        true,
                        BoundaryMath.getPriceX96AtBoundary(boundaryLower),
                        boundaryUpperPriceX96
                    );
                }
            }
        }

        // When the price is rising and the current boundary coincides with the upper boundary, start searching
        // from the lower boundary. Otherwise, start searching from the current boundary
        boundary = !lte && boundaryUpper == boundary ? boundaryLower : boundary;
        while (BoundaryMath.isInRange(boundary)) {
            (next, initialized) = nextInitializedBoundaryWithinOneWord(self, boundary, resolution, lte);
            if (initialized) {
                unchecked {
                    return (
                        next,
                        true,
                        BoundaryMath.getPriceX96AtBoundary(next),
                        BoundaryMath.getPriceX96AtBoundary(next + resolution)
                    );
                }
            }
            boundary = next;
        }
    }

    /// @notice Returns the next initialized boundary contained in the same (or adjacent) word
    /// as the boundary that is either to the left (less than) or right (greater than)
    /// of the given boundary
    /// @param self The mapping that stores the initial state of the boundary
    /// @param boundary The starting boundary
    /// @param resolution The step size in initialized boundaries for a grid created with a given fee
    /// @param lte Whether or not to search to the left (less than or equal to the start boundary)
    /// for the next initialization
    /// @return next The next boundary, regardless of initialization state
    /// @return initialized Whether or not the next boundary is initialized
    function nextInitializedBoundaryWithinOneWord(
        mapping(int16 => uint256) storage self,
        int24 boundary,
        int24 resolution,
        bool lte
    ) internal view returns (int24 next, bool initialized) {
        int24 compressed = boundary / resolution;

        if (lte) {
            // Begin from the word of the next boundary, since the current boundary state is immaterial
            (int16 wordPos, uint8 bitPos) = position(compressed - 1);
            // all the 1s at or to the right of the current bitPos
            uint256 mask = ~uint256(0) >> (type(uint8).max - bitPos);
            uint256 masked = self[wordPos] & mask;

            // If no initialized boundaries exist to the right of the current boundary,
            // return the rightmost boundary in the word
            initialized = masked != 0;
            // Overflow/underflow is possible. The resolution and the boundary should be limited
            // when calling externally to prevent this
            next = initialized
                ? (compressed - 1 - int24(uint24(bitPos - BitMath.mostSignificantBit(masked)))) * resolution
                : (compressed - 1 - int24(uint24(bitPos))) * resolution;
        } else {
            if (boundary < 0 && boundary % resolution != 0) {
                // round towards negative infinity
                --compressed;
            }

            // Begin from the word of the next boundary, since the current boundary state is immaterial
            (int16 wordPos, uint8 bitPos) = position(compressed + 1);
            // all the 1s at or to the left of the bitPos
            uint256 mask = ~uint256(0) << bitPos;
            uint256 masked = self[wordPos] & mask;

            // If no initialized boundaries exist to the left of the current boundary,
            // return the leftmost boundary in the word
            initialized = masked != 0;
            // Overflow/underflow is possible. The resolution and the boundary should be limited
            // when calling externally to prevent this
            next = initialized
                ? (compressed + 1 + int24(uint24(BitMath.leastSignificantBit(masked) - bitPos))) * resolution
                : (compressed + 1 + int24(uint24(type(uint8).max - bitPos))) * resolution;
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

interface IGridParameters {
    /// @dev Parameters for initializing the grid
    struct InitializeParameters {
        /// @dev The initial price of the grid, as a Q64.96.
        /// Price is represented as an amountToken1/amountToken0 Q64.96 value.
        uint160 priceX96;
        /// @dev The address to receive orders
        address recipient;
        /// @dev Represents the order parameters for token0
        BoundaryLowerWithAmountParameters[] orders0;
        /// @dev Represents the order parameters for token1
        BoundaryLowerWithAmountParameters[] orders1;
    }

    /// @dev Parameters for placing an order
    struct PlaceOrderParameters {
        /// @dev The address to receive the order
        address recipient;
        /// @dev When zero is true, it represents token0, otherwise it represents token1
        bool zero;
        /// @dev The lower boundary of the order
        int24 boundaryLower;
        /// @dev The amount of token0 or token1 to add
        uint128 amount;
    }

    struct PlaceOrderInBatchParameters {
        /// @dev The address to receive the order
        address recipient;
        /// @dev When zero is true, it represents token0, otherwise it represents token1
        bool zero;
        BoundaryLowerWithAmountParameters[] orders;
    }

    struct BoundaryLowerWithAmountParameters {
        /// @dev The lower boundary of the order
        int24 boundaryLower;
        /// @dev The amount of token0 or token1 to add
        uint128 amount;
    }

    /// @dev Status during swap
    struct SwapState {
        /// @dev When true, token0 is swapped for token1, otherwise token1 is swapped for token0
        bool zeroForOne;
        /// @dev The remaining amount of the swap, which implicitly configures
        /// the swap as exact input (positive), or exact output (negative)
        int256 amountSpecifiedRemaining;
        /// @dev The calculated amount to be inputted
        uint256 amountInputCalculated;
        /// @dev The calculated amount of fee to be inputted
        uint256 feeAmountInputCalculated;
        /// @dev The calculated amount to be outputted
        uint256 amountOutputCalculated;
        /// @dev The price of the grid, as a Q64.96
        uint160 priceX96;
        uint160 priceLimitX96;
        /// @dev The boundary of the grid
        int24 boundary;
        /// @dev The lower boundary of the grid
        int24 boundaryLower;
        uint160 initializedBoundaryLowerPriceX96;
        uint160 initializedBoundaryUpperPriceX96;
        /// @dev Whether the swap has been completed
        bool stopSwap;
    }

    struct SwapForBoundaryState {
        /// @dev The price indicated by the lower boundary, as a Q64.96
        uint160 boundaryLowerPriceX96;
        /// @dev The price indicated by the upper boundary, as a Q64.96
        uint160 boundaryUpperPriceX96;
        /// @dev The price indicated by the lower or upper boundary, as a Q64.96.
        /// When using token0 to exchange token1, it is equal to boundaryLowerPriceX96,
        /// otherwise it is equal to boundaryUpperPriceX96
        uint160 boundaryPriceX96;
        /// @dev The price of the grid, as a Q64.96
        uint160 priceX96;
    }

    struct UpdateBundleForTakerParameters {
        /// @dev The amount to be swapped in to bundle0
        uint256 amountInUsed;
        /// @dev The remaining amount to be swapped in to bundle1
        uint256 amountInRemaining;
        /// @dev The amount to be swapped out to bundle0
        uint128 amountOutUsed;
        /// @dev The remaining amount to be swapped out to bundle1
        uint128 amountOutRemaining;
        /// @dev The amount to be paid to bundle0
        uint128 takerFeeForMakerAmountUsed;
        /// @dev The amount to be paid to bundle1
        uint128 takerFeeForMakerAmountRemaining;
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

library Uint128Math {
    /// @dev Returns the minimum of the two values
    /// @param a The first value
    /// @param b The second value
    /// @return min The minimum of the two values
    function minUint128(uint128 a, uint128 b) internal pure returns (uint128 min) {
        return a < b ? a : b;
    }

    /// @dev Returns the maximum of the two values
    /// @param a The first value
    /// @param b The second value
    /// @return max The maximum of the two values
    function maxUint128(uint128 a, uint128 b) internal pure returns (uint128 max) {
        return a > b ? a : b;
    }
}

// SPDX-License-Identifier: BUSL-1.1
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/math/Math.sol";
import "@openzeppelin/contracts/utils/math/SafeCast.sol";
import "../interfaces/IGridStructs.sol";
import "../interfaces/IGridParameters.sol";
import "./FixedPointX128.sol";

library BundleMath {
    using SafeCast for uint256;

    /// @dev Updates for a taker
    /// @param self The bundle
    /// @param amountIn The amount of swapped in token by the taker
    /// @param amountOut The amount of swapped out token by the taker. If amountOut is greater than bundle balance, the difference is transferred to bundle1
    /// @param takerFeeForMakerAmount The fee paid by the taker(excluding the protocol fee). If amountOut is greater than bundle balance, the difference is transferred to bundle1
    function updateForTaker(
        IGridStructs.Bundle storage self,
        uint256 amountIn,
        uint128 amountOut,
        uint128 takerFeeForMakerAmount
    ) internal returns (IGridParameters.UpdateBundleForTakerParameters memory parameters) {
        uint128 makerAmountRemaining = self.makerAmountRemaining;
        // the amount out actually paid to the taker
        parameters.amountOutUsed = amountOut <= makerAmountRemaining ? amountOut : makerAmountRemaining;

        if (parameters.amountOutUsed == amountOut) {
            parameters.amountInUsed = amountIn;

            parameters.takerFeeForMakerAmountUsed = takerFeeForMakerAmount;
        } else {
            parameters.amountInUsed = parameters.amountOutUsed * amountIn / amountOut; // amountOutUsed * amountIn may overflow here
            unchecked {
                parameters.amountInRemaining = amountIn - parameters.amountInUsed;

                parameters.amountOutRemaining = amountOut - parameters.amountOutUsed;

                parameters.takerFeeForMakerAmountUsed = uint128(
                    (uint256(parameters.amountOutUsed) * takerFeeForMakerAmount) / amountOut
                );
                parameters.takerFeeForMakerAmountRemaining =
                    takerFeeForMakerAmount -
                    parameters.takerFeeForMakerAmountUsed;
            }
        }

        // updates maker amount remaining
        unchecked {
            self.makerAmountRemaining = makerAmountRemaining - parameters.amountOutUsed;
        }

        self.takerAmountRemaining = self.takerAmountRemaining + (parameters.amountInUsed).toUint128();

        self.takerFeeAmountRemaining = self.takerFeeAmountRemaining + parameters.takerFeeForMakerAmountUsed;
    }

    /// @notice Maker adds liquidity to the bundle
    /// @param self The bundle to be updated
    /// @param makerAmount The amount of token to be added to the bundle
    function addLiquidity(IGridStructs.Bundle storage self, uint128 makerAmount) internal {
        self.makerAmountTotal = self.makerAmountTotal + makerAmount;
        unchecked {
            self.makerAmountRemaining = self.makerAmountRemaining + makerAmount;
        }
    }

    /// @notice Maker adds liquidity to the bundle
    /// @param self The bundle to be updated
    /// @param makerAmountTotal The total amount of token that the maker has added to the bundle
    /// @param makerAmountRemaining The amount of token that the maker has not yet swapped
    /// @param makerAmount The amount of token to be added to the bundle
    function addLiquidityWithAmount(
        IGridStructs.Bundle storage self,
        uint128 makerAmountTotal,
        uint128 makerAmountRemaining,
        uint128 makerAmount
    ) internal {
        self.makerAmountTotal = makerAmountTotal + makerAmount;
        unchecked {
            self.makerAmountRemaining = makerAmountRemaining + makerAmount;
        }
    }

    /// @notice Maker removes liquidity from the bundle
    /// @param self The bundle to be updated
    /// @param makerAmountRaw The amount of liquidity added by the maker when placing an order
    /// @return makerAmountOut The amount of token0 or token1 that the maker will receive
    /// @return takerAmountOut The amount of token1 or token0 that the maker will receive
    /// @return takerFeeAmountOut The amount of fees that the maker will receive
    /// @return makerAmountTotalNew The remaining amount of liquidity added by the maker
    function removeLiquidity(
        IGridStructs.Bundle storage self,
        uint128 makerAmountRaw
    )
        internal
        returns (uint128 makerAmountOut, uint128 takerAmountOut, uint128 takerFeeAmountOut, uint128 makerAmountTotalNew)
    {
        uint128 makerAmountTotal = self.makerAmountTotal;
        uint128 makerAmountRemaining = self.makerAmountRemaining;
        uint128 takerAmountRemaining = self.takerAmountRemaining;
        uint128 takerFeeAmountRemaining = self.takerFeeAmountRemaining;

        unchecked {
            makerAmountTotalNew = makerAmountTotal - makerAmountRaw;
            self.makerAmountTotal = makerAmountTotalNew;

            // This calculation won't overflow because makerAmountRaw divided by
            // makerAmountTotal will always have a value between 0 and 1 (excluding 0), and
            // multiplying that by a uint128 value won't result in an overflow. So the
            // calculation is designed to work within the constraints of the data types being used,
            // without exceeding their maximum values.
            makerAmountOut = uint128((uint256(makerAmountRaw) * makerAmountRemaining) / makerAmountTotal);
            self.makerAmountRemaining = makerAmountRemaining - makerAmountOut;

            takerAmountOut = uint128((uint256(makerAmountRaw) * takerAmountRemaining) / makerAmountTotal);
            self.takerAmountRemaining = takerAmountRemaining - takerAmountOut;

            takerFeeAmountOut = uint128((uint256(makerAmountRaw) * takerFeeAmountRemaining) / makerAmountTotal);
            self.takerFeeAmountRemaining = takerFeeAmountRemaining - takerFeeAmountOut;
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

/// @title The interface for the price oracle
interface IPriceOracle {
    /// @notice Emitted when the capacity of the array in which the oracle can store prices has increased.
    /// @param grid The grid address whose capacity has been increased
    /// @param capacityOld Array capacity before the increase in capacity
    /// @param capacityNew Array capacity after the increase in capacity
    event IncreaseCapacity(address indexed grid, uint16 capacityOld, uint16 capacityNew);

    struct GridPriceData {
        /// @dev The block timestamp of the price data
        uint32 blockTimestamp;
        /// @dev The time-cumulative boundary
        int56 boundaryCumulative;
        /// @dev Whether or not the price data is initialized
        bool initialized;
    }

    struct GridOracleState {
        /// @dev The index of the last updated price
        uint16 index;
        /// @dev The array capacity used by the oracle
        uint16 capacity;
        /// @dev The capacity of the array that the oracle can use
        uint16 capacityNext;
    }

    /// @notice Returns the state of the oracle for a given grid
    /// @param grid The grid to retrieve the state of
    /// @return index The index of the last updated price
    /// @return capacity The array capacity used by the oracle
    /// @return capacityNext The capacity of the array that the oracle can use
    function gridOracleStates(address grid) external view returns (uint16 index, uint16 capacity, uint16 capacityNext);

    /// @notice Returns the price data of the oracle for a given grid and index
    /// @param grid The grid to get the price data of
    /// @param index The index of the price data to get
    /// @return blockTimestamp The block timestamp of the price data
    /// @return boundaryCumulative The time-cumulative boundary
    /// @return initialized Whether or not the price data is initialized
    function gridPriceData(
        address grid,
        uint256 index
    ) external view returns (uint32 blockTimestamp, int56 boundaryCumulative, bool initialized);

    /// @notice Register a grid to the oracle using a given token pair and resolution
    /// @param tokenA The contract address of either token0 or token1
    /// @param tokenB The contract address of the other token
    /// @param resolution The step size in initialized boundaries for a grid created with a given fee
    function register(address tokenA, address tokenB, int24 resolution) external;

    /// @notice Update the oracle price
    /// @param boundary The new boundary to write to the oracle
    /// @param blockTimestamp The timestamp of the oracle price to write
    function update(int24 boundary, uint32 blockTimestamp) external;

    /// @notice Increase the storage capacity of the oracle
    /// @param grid The grid whose capacity is to be increased
    /// @param capacityNext Array capacity after increase in capacity
    function increaseCapacity(address grid, uint16 capacityNext) external;

    /// @notice Get the time-cumulative price for a given time
    /// @param grid Get the price of a grid address
    /// @param secondsAgo The time elapsed (in seconds) to get the boundary for
    /// @return boundaryCumulative The time-cumulative boundary for the given time
    function getBoundaryCumulative(address grid, uint32 secondsAgo) external view returns (int56 boundaryCumulative);

    /// @notice Get a list of time-cumulative boundaries for given times
    /// @param grid The grid address to get the boundaries of
    /// @param secondsAgos A list of times elapsed (in seconds) to get the boundaries for
    /// @return boundaryCumulatives The list of time-cumulative boundaries for the given times
    function getBoundaryCumulatives(
        address grid,
        uint32[] calldata secondsAgos
    ) external view returns (int56[] memory boundaryCumulatives);
}

// SPDX-License-Identifier: BUSL-1.1
pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/math/Math.sol";
import "@openzeppelin/contracts/utils/math/SafeCast.sol";
import "./Uint128Math.sol";
import "./FixedPointX96.sol";
import "./FixedPointX192.sol";

library SwapMath {
    using SafeCast for uint256;

    struct ComputeSwapStep {
        /// @dev The price after swapping the amount in/out
        uint160 priceNextX96;
        /// @dev The amount to be swapped in, of either token0 or token1, based on the direction of the swap
        uint256 amountIn;
        /// @dev The amount to be swapped out, of either token0 or token1, based on the direction of the swap
        uint128 amountOut;
        /// @dev The amount of fees paid by the taker
        uint128 feeAmount;
    }

    /// @notice Calculates the result of the swap through the given boundary parameters
    /// @param priceCurrentX96 The current price of the grid, as a Q64.96
    /// @param boundaryPriceX96 It is the upper boundary price when using token1 to exchange for token0.
    /// Otherwise, it is the lower boundary price, as a Q64.96
    /// @param priceLimitX96 The price limit of the swap, as a Q64.96
    /// @param amountRemaining The remaining amount to be swapped in (positive) or swapped out (negative)
    /// @param makerAmount The remaining amount of token0 or token1 that can be swapped out from the makers
    /// @param takerFeePips The taker fee, denominated in hundredths of a bip (i.e. 1e-6)
    /// @return step The result of the swap step
    function computeSwapStep(
        uint160 priceCurrentX96,
        uint160 boundaryPriceX96,
        uint160 priceLimitX96,
        int256 amountRemaining,
        uint128 makerAmount,
        int24 takerFeePips
    ) internal pure returns (ComputeSwapStep memory step) {
        if (amountRemaining > 0) {
            return
                computeSwapStepForExactIn(
                    priceCurrentX96,
                    boundaryPriceX96,
                    priceLimitX96,
                    uint256(amountRemaining),
                    makerAmount,
                    takerFeePips
                );
        } else {
            uint256 absAmountRemaining;
            unchecked {
                absAmountRemaining = uint256(-amountRemaining);
            }
            return
                computeSwapStepForExactOut(
                    priceCurrentX96,
                    boundaryPriceX96,
                    priceLimitX96,
                    // The converted value will not overflow. The maximum amount of liquidity
                    // allowed in each boundary is less than or equal to uint128.
                    absAmountRemaining > makerAmount ? makerAmount : uint128(absAmountRemaining),
                    makerAmount,
                    takerFeePips
                );
        }
    }

    function computeSwapStepForExactIn(
        uint160 priceCurrentX96,
        uint160 boundaryPriceX96,
        uint160 priceLimitX96,
        uint256 takerAmountInRemaining,
        uint128 makerAmount,
        int24 takerFeePips
    ) internal pure returns (ComputeSwapStep memory step) {
        if (!_priceInRange(priceCurrentX96, boundaryPriceX96, priceLimitX96)) {
            return
                _computeSwapStepForExactIn(
                    priceCurrentX96,
                    boundaryPriceX96,
                    takerAmountInRemaining,
                    makerAmount,
                    takerFeePips
                );
        } else {
            step.amountOut = _computeAmountOutForPriceLimit(
                priceCurrentX96,
                boundaryPriceX96,
                priceLimitX96,
                makerAmount
            );

            step = _computeSwapStepForExactOut(
                priceCurrentX96,
                boundaryPriceX96,
                step.amountOut,
                makerAmount,
                takerFeePips
            );
            return
                step.amountIn + step.feeAmount > takerAmountInRemaining // the remaining amount in is not enough to reach the limit price
                    ? _computeSwapStepForExactIn(
                        priceCurrentX96,
                        boundaryPriceX96,
                        takerAmountInRemaining,
                        makerAmount,
                        takerFeePips
                    )
                    : step;
        }
    }

    function _computeSwapStepForExactIn(
        uint160 priceCurrentX96,
        uint160 boundaryPriceX96,
        uint256 takerAmountInRemaining,
        uint128 makerAmount,
        int24 takerFeePips
    ) private pure returns (ComputeSwapStep memory step) {
        bool zeroForOne = priceCurrentX96 >= boundaryPriceX96;

        uint256 takerAmountInWithoutFee = Math.mulDiv(takerAmountInRemaining, 1e6 - uint256(uint24(takerFeePips)), 1e6);

        uint160 priceDeltaX96;
        unchecked {
            priceDeltaX96 = zeroForOne ? priceCurrentX96 - boundaryPriceX96 : boundaryPriceX96 - priceCurrentX96;
        }

        uint256 amountOut;
        if (zeroForOne) {
            // (2 * takerAmountIn * priceCurrent) / (2 - (priceMax - priceCurrent) * takerAmountIn / makerAmount)
            uint256 numerator = 2 * takerAmountInWithoutFee * priceCurrentX96;

            uint256 denominator = Math.mulDiv(
                priceDeltaX96,
                takerAmountInWithoutFee,
                makerAmount,
                Math.Rounding.Up // round up
            );

            amountOut = numerator / (FixedPointX96.Q_2 + denominator);
        } else {
            // ((2 * takerAmountIn * (1/priceCurrent) / (2 - (1/priceMax - 1/priceCurrent) * takerAmountIn / makerAmount))
            // Specifically divide first, then multiply to ensure that the amountOut is smaller
            uint256 numerator = 2 * takerAmountInWithoutFee * (FixedPointX192.Q / priceCurrentX96);

            uint256 reversePriceDeltaX96 = Math.ceilDiv(
                FixedPointX192.Q,
                priceCurrentX96 // round up
            ) - (FixedPointX192.Q / boundaryPriceX96);
            uint256 denominator = Math.mulDiv(
                reversePriceDeltaX96,
                takerAmountInWithoutFee,
                makerAmount,
                Math.Rounding.Up // round up
            );
            amountOut = numerator / (FixedPointX96.Q_2 + denominator);
        }

        if (amountOut > makerAmount) {
            step.priceNextX96 = boundaryPriceX96;
            step.amountOut = makerAmount;
            (step.amountIn, step.feeAmount) = _computeAmountInAndFeeAmount(
                zeroForOne,
                priceCurrentX96,
                boundaryPriceX96,
                makerAmount,
                Math.Rounding.Down,
                takerFeePips
            );
        } else {
            step.amountOut = amountOut.toUint128();
            step.priceNextX96 = _computePriceNextX96(
                zeroForOne,
                priceCurrentX96,
                priceDeltaX96,
                step.amountOut,
                makerAmount
            );
            step.amountIn = takerAmountInWithoutFee;
            unchecked {
                step.feeAmount = (takerAmountInRemaining - takerAmountInWithoutFee).toUint128();
            }
        }
    }

    function computeSwapStepForExactOut(
        uint160 priceCurrentX96,
        uint160 boundaryPriceX96,
        uint160 priceLimitX96,
        uint128 takerAmountOutRemaining,
        uint128 makerAmount,
        int24 takerFeePips
    ) internal pure returns (ComputeSwapStep memory step) {
        // if the limit price is not within the range, it will be calculated directly
        if (!_priceInRange(priceCurrentX96, boundaryPriceX96, priceLimitX96)) {
            return
                _computeSwapStepForExactOut(
                    priceCurrentX96,
                    boundaryPriceX96,
                    takerAmountOutRemaining,
                    makerAmount,
                    takerFeePips
                );
        }

        // otherwise calculate the new takerAmountRemaining value
        uint128 availableAmountOut = _computeAmountOutForPriceLimit(
            priceCurrentX96,
            boundaryPriceX96,
            priceLimitX96,
            makerAmount
        );

        return
            _computeSwapStepForExactOut(
                priceCurrentX96,
                boundaryPriceX96,
                Uint128Math.minUint128(availableAmountOut, takerAmountOutRemaining),
                makerAmount,
                takerFeePips
            );
    }

    /// @dev Checks if the price limit is within the range
    /// @param priceCurrentX96 The current price of the grid, as a Q64.96
    /// @param boundaryPriceX96 It is the upper boundary price when using token1 to exchange for token0.
    /// Otherwise, it is the lower boundary price, as a Q64.96
    /// @param priceLimitX96 The price limit of the swap, as a Q64.96
    /// @return True if the price limit is within the range
    function _priceInRange(
        uint160 priceCurrentX96,
        uint160 boundaryPriceX96,
        uint160 priceLimitX96
    ) private pure returns (bool) {
        return
            priceCurrentX96 >= boundaryPriceX96
                ? (priceLimitX96 > boundaryPriceX96 && priceLimitX96 <= priceCurrentX96)
                : (priceLimitX96 >= priceCurrentX96 && priceLimitX96 < boundaryPriceX96);
    }

    function _computeSwapStepForExactOut(
        uint160 priceCurrentX96,
        uint160 boundaryPriceX96,
        uint128 takerAmountOutRemaining,
        uint128 makerAmount,
        int24 takerFeePips
    ) private pure returns (ComputeSwapStep memory step) {
        bool zeroForOne = priceCurrentX96 >= boundaryPriceX96;

        uint160 priceDeltaX96;
        Math.Rounding priceNextRounding;
        unchecked {
            (priceDeltaX96, priceNextRounding) = zeroForOne
                ? (priceCurrentX96 - boundaryPriceX96, Math.Rounding.Down)
                : (boundaryPriceX96 - priceCurrentX96, Math.Rounding.Up);
        }

        step.priceNextX96 = _computePriceNextX96(
            zeroForOne,
            priceCurrentX96,
            priceDeltaX96,
            takerAmountOutRemaining,
            makerAmount
        );

        (step.amountIn, step.feeAmount) = _computeAmountInAndFeeAmount(
            zeroForOne,
            priceCurrentX96,
            step.priceNextX96,
            takerAmountOutRemaining,
            priceNextRounding,
            takerFeePips
        );
        step.amountOut = takerAmountOutRemaining;
    }

    function _computePriceNextX96(
        bool zeroForOne,
        uint160 priceCurrentX96,
        uint160 priceDeltaX96,
        uint160 takerAmountOut,
        uint128 makerAmount
    ) private pure returns (uint160) {
        uint256 priceDeltaX96WithRate = Math.mulDiv(priceDeltaX96, takerAmountOut, makerAmount, Math.Rounding.Up);
        unchecked {
            return
                zeroForOne
                    ? (priceCurrentX96 - priceDeltaX96WithRate).toUint160()
                    : (priceCurrentX96 + priceDeltaX96WithRate).toUint160();
        }
    }

    function _computeAmountInAndFeeAmount(
        bool zeroForOne,
        uint160 priceCurrentX96,
        uint160 priceNextX96,
        uint128 amountOut,
        Math.Rounding priceNextRounding,
        int24 takerFeePips
    ) private pure returns (uint256 amountIn, uint128 feeAmount) {
        uint160 priceAvgX96;
        unchecked {
            uint256 priceAccumulateX96 = uint256(priceCurrentX96) + priceNextX96;
            priceAccumulateX96 = priceNextRounding == Math.Rounding.Up ? priceAccumulateX96 + 1 : priceAccumulateX96;
            priceAvgX96 = uint160(priceAccumulateX96 >> 1);
        }

        amountIn = zeroForOne
            ? Math.mulDiv(amountOut, FixedPointX96.Q, priceAvgX96, Math.Rounding.Up)
            : Math.mulDiv(priceAvgX96, amountOut, FixedPointX96.Q, Math.Rounding.Up);

        // feeAmount = amountIn * takerFeePips / (1e6 - takerFeePips)
        feeAmount = Math
            .mulDiv(uint24(takerFeePips), amountIn, 1e6 - uint24(takerFeePips), Math.Rounding.Up)
            .toUint128();
    }

    function _computeAmountOutForPriceLimit(
        uint160 priceCurrentX96,
        uint160 boundaryPriceX96,
        uint160 priceLimitX96,
        uint128 makerAmount
    ) private pure returns (uint128 availableAmountOut) {
        uint160 priceLimitDeltaX96;
        uint160 priceMaxDeltaX96;
        unchecked {
            (priceLimitDeltaX96, priceMaxDeltaX96) = priceLimitX96 >= priceCurrentX96
                ? (priceLimitX96 - priceCurrentX96, boundaryPriceX96 - priceCurrentX96)
                : (priceCurrentX96 - priceLimitX96, priceCurrentX96 - boundaryPriceX96);
        }

        uint256 tempX96 = _divUpForPriceX96(priceLimitDeltaX96, priceMaxDeltaX96);
        availableAmountOut = Math.mulDiv(tempX96, makerAmount, FixedPointX96.Q, Math.Rounding.Up).toUint128();
    }

    function _divUpForPriceX96(uint160 aX96, uint160 bX96) private pure returns (uint256) {
        if (aX96 == 0) {
            return 0;
        }
        unchecked {
            // never overflows
            uint256 tempX96 = uint256(aX96) * FixedPointX96.Q;
            // (a + b - 1) / b can overflow on addition, so we distribute
            return (tempX96 - 1) / bX96 + 1;
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

library Uint160Math {
    /// @dev Returns the minimum of the two values
    /// @param a The first value
    /// @param b The second value
    /// @return min The minimum of the two values
    function minUint160(uint160 a, uint160 b) internal pure returns (uint160 min) {
        return a < b ? a : b;
    }

    /// @dev Returns the maximum of the two values
    /// @param a The first value
    /// @param b The second value
    /// @return max The maximum of the two values
    function maxUint160(uint160 a, uint160 b) internal pure returns (uint160 max) {
        return a > b ? a : b;
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

/// @title Callback for IGrid#placeMakerOrder
/// @notice Any contract that calls IGrid#placeMakerOrder must implement this interface
interface IGridPlaceMakerOrderCallback {
    /// @notice Called to `msg.sender` after executing a place maker order via IGrid#placeMakerOrder
    /// @dev In this implementation, you are required to pay the grid tokens owed for the maker order.
    /// The caller of the method must be a grid deployed by the canonical GridFactory.
    /// At most one of amount0 and amount1 is a positive number
    /// @param amount0 The grid will receive the amount of token0 upon placement of the maker order.
    /// In the receiving case, the callback must send this amount of token0 to the grid
    /// @param amount1 The grid will receive the amount of token1 upon placement of the maker order.
    /// In the receiving case, the callback must send this amount of token1 to the grid
    /// @param data Any data passed through by the caller via the IGrid#placeMakerOrder call
    function gridexPlaceMakerOrderCallback(uint256 amount0, uint256 amount1, bytes calldata data) external;
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

/// @title Callback for IGrid#swap
/// @notice Any contract that calls IGrid#swap must implement this interface
interface IGridSwapCallback {
    /// @notice Called to `msg.sender` after executing a swap via IGrid#swap
    /// @dev In this implementation, you are required to pay the grid tokens owed for the swap.
    /// The caller of the method must be a grid deployed by the canonical GridFactory.
    /// If there is no token swap, both amount0Delta and amount1Delta are 0
    /// @param amount0Delta The grid will send or receive the amount of token0 upon completion of the swap.
    /// In the receiving case, the callback must send this amount of token0 to the grid
    /// @param amount1Delta The grid will send or receive the quantity of token1 upon completion of the swap.
    /// In the receiving case, the callback must send this amount of token1 to the grid
    /// @param data Any data passed through by the caller via the IGrid#swap call
    function gridexSwapCallback(int256 amount0Delta, int256 amount1Delta, bytes calldata data) external;
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

/// @title Callback for IGrid#flash
/// @notice Any contract that calls IGrid#flash must implement this interface
interface IGridFlashCallback {
    /// @notice Called to `msg.sender` after executing a flash via IGrid#flash
    /// @dev In this implementation, you are required to repay the grid the tokens owed for the flash.
    /// The caller of the method must be a grid deployed by the canonical GridFactory.
    /// @param data Any data passed through by the caller via the [email protected] call
    function gridexFlashCallback(bytes calldata data) external;
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/Context.sol)

pragma solidity ^0.8.0;

/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }

    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/math/Math.sol)

pragma solidity ^0.8.0;

/**
 * @dev Standard math utilities missing in the Solidity language.
 */
library Math {
    enum Rounding {
        Down, // Toward negative infinity
        Up, // Toward infinity
        Zero // Toward zero
    }

    /**
     * @dev Returns the largest of two numbers.
     */
    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a >= b ? a : b;
    }

    /**
     * @dev Returns the smallest of two numbers.
     */
    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        return a < b ? a : b;
    }

    /**
     * @dev Returns the average of two numbers. The result is rounded towards
     * zero.
     */
    function average(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b) / 2 can overflow.
        return (a & b) + (a ^ b) / 2;
    }

    /**
     * @dev Returns the ceiling of the division of two numbers.
     *
     * This differs from standard division with `/` in that it rounds up instead
     * of rounding down.
     */
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b - 1) / b can overflow on addition, so we distribute.
        return a == 0 ? 0 : (a - 1) / b + 1;
    }

    /**
     * @notice Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
     * @dev Original credit to Remco Bloemen under MIT license (https://xn--2-umb.com/21/muldiv)
     * with further edits by Uniswap Labs also under MIT license.
     */
    function mulDiv(
        uint256 x,
        uint256 y,
        uint256 denominator
    ) internal pure returns (uint256 result) {
        unchecked {
            // 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
            // use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
            // variables such that product = prod1 * 2^256 + prod0.
            uint256 prod0; // Least significant 256 bits of the product
            uint256 prod1; // Most significant 256 bits of the product
            assembly {
                let mm := mulmod(x, y, not(0))
                prod0 := mul(x, y)
                prod1 := sub(sub(mm, prod0), lt(mm, prod0))
            }

            // Handle non-overflow cases, 256 by 256 division.
            if (prod1 == 0) {
                return prod0 / denominator;
            }

            // Make sure the result is less than 2^256. Also prevents denominator == 0.
            require(denominator > prod1);

            ///////////////////////////////////////////////
            // 512 by 256 division.
            ///////////////////////////////////////////////

            // Make division exact by subtracting the remainder from [prod1 prod0].
            uint256 remainder;
            assembly {
                // Compute remainder using mulmod.
                remainder := mulmod(x, y, denominator)

                // Subtract 256 bit number from 512 bit number.
                prod1 := sub(prod1, gt(remainder, prod0))
                prod0 := sub(prod0, remainder)
            }

            // Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
            // See https://cs.stackexchange.com/q/138556/92363.

            // Does not overflow because the denominator cannot be zero at this stage in the function.
            uint256 twos = denominator & (~denominator + 1);
            assembly {
                // Divide denominator by twos.
                denominator := div(denominator, twos)

                // Divide [prod1 prod0] by twos.
                prod0 := div(prod0, twos)

                // Flip twos such that it is 2^256 / twos. If twos is zero, then it becomes one.
                twos := add(div(sub(0, twos), twos), 1)
            }

            // Shift in bits from prod1 into prod0.
            prod0 |= prod1 * twos;

            // Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
            // that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
            // four bits. That is, denominator * inv = 1 mod 2^4.
            uint256 inverse = (3 * denominator) ^ 2;

            // Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
            // in modular arithmetic, doubling the correct bits in each step.
            inverse *= 2 - denominator * inverse; // inverse mod 2^8
            inverse *= 2 - denominator * inverse; // inverse mod 2^16
            inverse *= 2 - denominator * inverse; // inverse mod 2^32
            inverse *= 2 - denominator * inverse; // inverse mod 2^64
            inverse *= 2 - denominator * inverse; // inverse mod 2^128
            inverse *= 2 - denominator * inverse; // inverse mod 2^256

            // Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
            // This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
            // less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
            // is no longer required.
            result = prod0 * inverse;
            return result;
        }
    }

    /**
     * @notice Calculates x * y / denominator with full precision, following the selected rounding direction.
     */
    function mulDiv(
        uint256 x,
        uint256 y,
        uint256 denominator,
        Rounding rounding
    ) internal pure returns (uint256) {
        uint256 result = mulDiv(x, y, denominator);
        if (rounding == Rounding.Up && mulmod(x, y, denominator) > 0) {
            result += 1;
        }
        return result;
    }

    /**
     * @dev Returns the square root of a number. It the number is not a perfect square, the value is rounded down.
     *
     * Inspired by Henry S. Warren, Jr.'s "Hacker's Delight" (Chapter 11).
     */
    function sqrt(uint256 a) internal pure returns (uint256) {
        if (a == 0) {
            return 0;
        }

        // For our first guess, we get the biggest power of 2 which is smaller than the square root of the target.
        // We know that the "msb" (most significant bit) of our target number `a` is a power of 2 such that we have
        // `msb(a) <= a < 2*msb(a)`.
        // We also know that `k`, the position of the most significant bit, is such that `msb(a) = 2**k`.
        // This gives `2**k < a <= 2**(k+1)` → `2**(k/2) <= sqrt(a) < 2 ** (k/2+1)`.
        // Using an algorithm similar to the msb conmputation, we are able to compute `result = 2**(k/2)` which is a
        // good first aproximation of `sqrt(a)` with at least 1 correct bit.
        uint256 result = 1;
        uint256 x = a;
        if (x >> 128 > 0) {
            x >>= 128;
            result <<= 64;
        }
        if (x >> 64 > 0) {
            x >>= 64;
            result <<= 32;
        }
        if (x >> 32 > 0) {
            x >>= 32;
            result <<= 16;
        }
        if (x >> 16 > 0) {
            x >>= 16;
            result <<= 8;
        }
        if (x >> 8 > 0) {
            x >>= 8;
            result <<= 4;
        }
        if (x >> 4 > 0) {
            x >>= 4;
            result <<= 2;
        }
        if (x >> 2 > 0) {
            result <<= 1;
        }

        // At this point `result` is an estimation with one bit of precision. We know the true value is a uint128,
        // since it is the square root of a uint256. Newton's method converges quadratically (precision doubles at
        // every iteration). We thus need at most 7 iteration to turn our partial result with one bit of precision
        // into the expected uint128 result.
        unchecked {
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            return min(result, a / result);
        }
    }

    /**
     * @notice Calculates sqrt(a), following the selected rounding direction.
     */
    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256) {
        uint256 result = sqrt(a);
        if (rounding == Rounding.Up && result * result < a) {
            result += 1;
        }
        return result;
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/math/SafeCast.sol)

pragma solidity ^0.8.0;

/**
 * @dev Wrappers over Solidity's uintXX/intXX casting operators with added overflow
 * checks.
 *
 * Downcasting from uint256/int256 in Solidity does not revert on overflow. This can
 * easily result in undesired exploitation or bugs, since developers usually
 * assume that overflows raise errors. `SafeCast` restores this intuition by
 * reverting the transaction when such an operation overflows.
 *
 * Using this library instead of the unchecked operations eliminates an entire
 * class of bugs, so it's recommended to use it always.
 *
 * Can be combined with {SafeMath} and {SignedSafeMath} to extend it to smaller types, by performing
 * all math on `uint256` and `int256` and then downcasting.
 */
library SafeCast {
    /**
     * @dev Returns the downcasted uint248 from uint256, reverting on
     * overflow (when the input is greater than largest uint248).
     *
     * Counterpart to Solidity's `uint248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     *
     * _Available since v4.7._
     */
    function toUint248(uint256 value) internal pure returns (uint248) {
        require(value <= type(uint248).max, "SafeCast: value doesn't fit in 248 bits");
        return uint248(value);
    }

    /**
     * @dev Returns the downcasted uint240 from uint256, reverting on
     * overflow (when the input is greater than largest uint240).
     *
     * Counterpart to Solidity's `uint240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     *
     * _Available since v4.7._
     */
    function toUint240(uint256 value) internal pure returns (uint240) {
        require(value <= type(uint240).max, "SafeCast: value doesn't fit in 240 bits");
        return uint240(value);
    }

    /**
     * @dev Returns the downcasted uint232 from uint256, reverting on
     * overflow (when the input is greater than largest uint232).
     *
     * Counterpart to Solidity's `uint232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     *
     * _Available since v4.7._
     */
    function toUint232(uint256 value) internal pure returns (uint232) {
        require(value <= type(uint232).max, "SafeCast: value doesn't fit in 232 bits");
        return uint232(value);
    }

    /**
     * @dev Returns the downcasted uint224 from uint256, reverting on
     * overflow (when the input is greater than largest uint224).
     *
     * Counterpart to Solidity's `uint224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     *
     * _Available since v4.2._
     */
    function toUint224(uint256 value) internal pure returns (uint224) {
        require(value <= type(uint224).max, "SafeCast: value doesn't fit in 224 bits");
        return uint224(value);
    }

    /**
     * @dev Returns the downcasted uint216 from uint256, reverting on
     * overflow (when the input is greater than largest uint216).
     *
     * Counterpart to Solidity's `uint216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     *
     * _Available since v4.7._
     */
    function toUint216(uint256 value) internal pure returns (uint216) {
        require(value <= type(uint216).max, "SafeCast: value doesn't fit in 216 bits");
        return uint216(value);
    }

    /**
     * @dev Returns the downcasted uint208 from uint256, reverting on
     * overflow (when the input is greater than largest uint208).
     *
     * Counterpart to Solidity's `uint208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     *
     * _Available since v4.7._
     */
    function toUint208(uint256 value) internal pure returns (uint208) {
        require(value <= type(uint208).max, "SafeCast: value doesn't fit in 208 bits");
        return uint208(value);
    }

    /**
     * @dev Returns the downcasted uint200 from uint256, reverting on
     * overflow (when the input is greater than largest uint200).
     *
     * Counterpart to Solidity's `uint200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     *
     * _Available since v4.7._
     */
    function toUint200(uint256 value) internal pure returns (uint200) {
        require(value <= type(uint200).max, "SafeCast: value doesn't fit in 200 bits");
        return uint200(value);
    }

    /**
     * @dev Returns the downcasted uint192 from uint256, reverting on
     * overflow (when the input is greater than largest uint192).
     *
     * Counterpart to Solidity's `uint192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     *
     * _Available since v4.7._
     */
    function toUint192(uint256 value) internal pure returns (uint192) {
        require(value <= type(uint192).max, "SafeCast: value doesn't fit in 192 bits");
        return uint192(value);
    }

    /**
     * @dev Returns the downcasted uint184 from uint256, reverting on
     * overflow (when the input is greater than largest uint184).
     *
     * Counterpart to Solidity's `uint184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     *
     * _Available since v4.7._
     */
    function toUint184(uint256 value) internal pure returns (uint184) {
        require(value <= type(uint184).max, "SafeCast: value doesn't fit in 184 bits");
        return uint184(value);
    }

    /**
     * @dev Returns the downcasted uint176 from uint256, reverting on
     * overflow (when the input is greater than largest uint176).
     *
     * Counterpart to Solidity's `uint176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     *
     * _Available since v4.7._
     */
    function toUint176(uint256 value) internal pure returns (uint176) {
        require(value <= type(uint176).max, "SafeCast: value doesn't fit in 176 bits");
        return uint176(value);
    }

    /**
     * @dev Returns the downcasted uint168 from uint256, reverting on
     * overflow (when the input is greater than largest uint168).
     *
     * Counterpart to Solidity's `uint168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     *
     * _Available since v4.7._
     */
    function toUint168(uint256 value) internal pure returns (uint168) {
        require(value <= type(uint168).max, "SafeCast: value doesn't fit in 168 bits");
        return uint168(value);
    }

    /**
     * @dev Returns the downcasted uint160 from uint256, reverting on
     * overflow (when the input is greater than largest uint160).
     *
     * Counterpart to Solidity's `uint160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     *
     * _Available since v4.7._
     */
    function toUint160(uint256 value) internal pure returns (uint160) {
        require(value <= type(uint160).max, "SafeCast: value doesn't fit in 160 bits");
        return uint160(value);
    }

    /**
     * @dev Returns the downcasted uint152 from uint256, reverting on
     * overflow (when the input is greater than largest uint152).
     *
     * Counterpart to Solidity's `uint152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     *
     * _Available since v4.7._
     */
    function toUint152(uint256 value) internal pure returns (uint152) {
        require(value <= type(uint152).max, "SafeCast: value doesn't fit in 152 bits");
        return uint152(value);
    }

    /**
     * @dev Returns the downcasted uint144 from uint256, reverting on
     * overflow (when the input is greater than largest uint144).
     *
     * Counterpart to Solidity's `uint144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     *
     * _Available since v4.7._
     */
    function toUint144(uint256 value) internal pure returns (uint144) {
        require(value <= type(uint144).max, "SafeCast: value doesn't fit in 144 bits");
        return uint144(value);
    }

    /**
     * @dev Returns the downcasted uint136 from uint256, reverting on
     * overflow (when the input is greater than largest uint136).
     *
     * Counterpart to Solidity's `uint136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     *
     * _Available since v4.7._
     */
    function toUint136(uint256 value) internal pure returns (uint136) {
        require(value <= type(uint136).max, "SafeCast: value doesn't fit in 136 bits");
        return uint136(value);
    }

    /**
     * @dev Returns the downcasted uint128 from uint256, reverting on
     * overflow (when the input is greater than largest uint128).
     *
     * Counterpart to Solidity's `uint128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     *
     * _Available since v2.5._
     */
    function toUint128(uint256 value) internal pure returns (uint128) {
        require(value <= type(uint128).max, "SafeCast: value doesn't fit in 128 bits");
        return uint128(value);
    }

    /**
     * @dev Returns the downcasted uint120 from uint256, reverting on
     * overflow (when the input is greater than largest uint120).
     *
     * Counterpart to Solidity's `uint120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     *
     * _Available since v4.7._
     */
    function toUint120(uint256 value) internal pure returns (uint120) {
        require(value <= type(uint120).max, "SafeCast: value doesn't fit in 120 bits");
        return uint120(value);
    }

    /**
     * @dev Returns the downcasted uint112 from uint256, reverting on
     * overflow (when the input is greater than largest uint112).
     *
     * Counterpart to Solidity's `uint112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     *
     * _Available since v4.7._
     */
    function toUint112(uint256 value) internal pure returns (uint112) {
        require(value <= type(uint112).max, "SafeCast: value doesn't fit in 112 bits");
        return uint112(value);
    }

    /**
     * @dev Returns the downcasted uint104 from uint256, reverting on
     * overflow (when the input is greater than largest uint104).
     *
     * Counterpart to Solidity's `uint104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     *
     * _Available since v4.7._
     */
    function toUint104(uint256 value) internal pure returns (uint104) {
        require(value <= type(uint104).max, "SafeCast: value doesn't fit in 104 bits");
        return uint104(value);
    }

    /**
     * @dev Returns the downcasted uint96 from uint256, reverting on
     * overflow (when the input is greater than largest uint96).
     *
     * Counterpart to Solidity's `uint96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     *
     * _Available since v4.2._
     */
    function toUint96(uint256 value) internal pure returns (uint96) {
        require(value <= type(uint96).max, "SafeCast: value doesn't fit in 96 bits");
        return uint96(value);
    }

    /**
     * @dev Returns the downcasted uint88 from uint256, reverting on
     * overflow (when the input is greater than largest uint88).
     *
     * Counterpart to Solidity's `uint88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     *
     * _Available since v4.7._
     */
    function toUint88(uint256 value) internal pure returns (uint88) {
        require(value <= type(uint88).max, "SafeCast: value doesn't fit in 88 bits");
        return uint88(value);
    }

    /**
     * @dev Returns the downcasted uint80 from uint256, reverting on
     * overflow (when the input is greater than largest uint80).
     *
     * Counterpart to Solidity's `uint80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     *
     * _Available since v4.7._
     */
    function toUint80(uint256 value) internal pure returns (uint80) {
        require(value <= type(uint80).max, "SafeCast: value doesn't fit in 80 bits");
        return uint80(value);
    }

    /**
     * @dev Returns the downcasted uint72 from uint256, reverting on
     * overflow (when the input is greater than largest uint72).
     *
     * Counterpart to Solidity's `uint72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     *
     * _Available since v4.7._
     */
    function toUint72(uint256 value) internal pure returns (uint72) {
        require(value <= type(uint72).max, "SafeCast: value doesn't fit in 72 bits");
        return uint72(value);
    }

    /**
     * @dev Returns the downcasted uint64 from uint256, reverting on
     * overflow (when the input is greater than largest uint64).
     *
     * Counterpart to Solidity's `uint64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     *
     * _Available since v2.5._
     */
    function toUint64(uint256 value) internal pure returns (uint64) {
        require(value <= type(uint64).max, "SafeCast: value doesn't fit in 64 bits");
        return uint64(value);
    }

    /**
     * @dev Returns the downcasted uint56 from uint256, reverting on
     * overflow (when the input is greater than largest uint56).
     *
     * Counterpart to Solidity's `uint56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     *
     * _Available since v4.7._
     */
    function toUint56(uint256 value) internal pure returns (uint56) {
        require(value <= type(uint56).max, "SafeCast: value doesn't fit in 56 bits");
        return uint56(value);
    }

    /**
     * @dev Returns the downcasted uint48 from uint256, reverting on
     * overflow (when the input is greater than largest uint48).
     *
     * Counterpart to Solidity's `uint48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     *
     * _Available since v4.7._
     */
    function toUint48(uint256 value) internal pure returns (uint48) {
        require(value <= type(uint48).max, "SafeCast: value doesn't fit in 48 bits");
        return uint48(value);
    }

    /**
     * @dev Returns the downcasted uint40 from uint256, reverting on
     * overflow (when the input is greater than largest uint40).
     *
     * Counterpart to Solidity's `uint40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     *
     * _Available since v4.7._
     */
    function toUint40(uint256 value) internal pure returns (uint40) {
        require(value <= type(uint40).max, "SafeCast: value doesn't fit in 40 bits");
        return uint40(value);
    }

    /**
     * @dev Returns the downcasted uint32 from uint256, reverting on
     * overflow (when the input is greater than largest uint32).
     *
     * Counterpart to Solidity's `uint32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     *
     * _Available since v2.5._
     */
    function toUint32(uint256 value) internal pure returns (uint32) {
        require(value <= type(uint32).max, "SafeCast: value doesn't fit in 32 bits");
        return uint32(value);
    }

    /**
     * @dev Returns the downcasted uint24 from uint256, reverting on
     * overflow (when the input is greater than largest uint24).
     *
     * Counterpart to Solidity's `uint24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     *
     * _Available since v4.7._
     */
    function toUint24(uint256 value) internal pure returns (uint24) {
        require(value <= type(uint24).max, "SafeCast: value doesn't fit in 24 bits");
        return uint24(value);
    }

    /**
     * @dev Returns the downcasted uint16 from uint256, reverting on
     * overflow (when the input is greater than largest uint16).
     *
     * Counterpart to Solidity's `uint16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     *
     * _Available since v2.5._
     */
    function toUint16(uint256 value) internal pure returns (uint16) {
        require(value <= type(uint16).max, "SafeCast: value doesn't fit in 16 bits");
        return uint16(value);
    }

    /**
     * @dev Returns the downcasted uint8 from uint256, reverting on
     * overflow (when the input is greater than largest uint8).
     *
     * Counterpart to Solidity's `uint8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     *
     * _Available since v2.5._
     */
    function toUint8(uint256 value) internal pure returns (uint8) {
        require(value <= type(uint8).max, "SafeCast: value doesn't fit in 8 bits");
        return uint8(value);
    }

    /**
     * @dev Converts a signed int256 into an unsigned uint256.
     *
     * Requirements:
     *
     * - input must be greater than or equal to 0.
     *
     * _Available since v3.0._
     */
    function toUint256(int256 value) internal pure returns (uint256) {
        require(value >= 0, "SafeCast: value must be positive");
        return uint256(value);
    }

    /**
     * @dev Returns the downcasted int248 from int256, reverting on
     * overflow (when the input is less than smallest int248 or
     * greater than largest int248).
     *
     * Counterpart to Solidity's `int248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     *
     * _Available since v4.7._
     */
    function toInt248(int256 value) internal pure returns (int248) {
        require(value >= type(int248).min && value <= type(int248).max, "SafeCast: value doesn't fit in 248 bits");
        return int248(value);
    }

    /**
     * @dev Returns the downcasted int240 from int256, reverting on
     * overflow (when the input is less than smallest int240 or
     * greater than largest int240).
     *
     * Counterpart to Solidity's `int240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     *
     * _Available since v4.7._
     */
    function toInt240(int256 value) internal pure returns (int240) {
        require(value >= type(int240).min && value <= type(int240).max, "SafeCast: value doesn't fit in 240 bits");
        return int240(value);
    }

    /**
     * @dev Returns the downcasted int232 from int256, reverting on
     * overflow (when the input is less than smallest int232 or
     * greater than largest int232).
     *
     * Counterpart to Solidity's `int232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     *
     * _Available since v4.7._
     */
    function toInt232(int256 value) internal pure returns (int232) {
        require(value >= type(int232).min && value <= type(int232).max, "SafeCast: value doesn't fit in 232 bits");
        return int232(value);
    }

    /**
     * @dev Returns the downcasted int224 from int256, reverting on
     * overflow (when the input is less than smallest int224 or
     * greater than largest int224).
     *
     * Counterpart to Solidity's `int224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     *
     * _Available since v4.7._
     */
    function toInt224(int256 value) internal pure returns (int224) {
        require(value >= type(int224).min && value <= type(int224).max, "SafeCast: value doesn't fit in 224 bits");
        return int224(value);
    }

    /**
     * @dev Returns the downcasted int216 from int256, reverting on
     * overflow (when the input is less than smallest int216 or
     * greater than largest int216).
     *
     * Counterpart to Solidity's `int216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     *
     * _Available since v4.7._
     */
    function toInt216(int256 value) internal pure returns (int216) {
        require(value >= type(int216).min && value <= type(int216).max, "SafeCast: value doesn't fit in 216 bits");
        return int216(value);
    }

    /**
     * @dev Returns the downcasted int208 from int256, reverting on
     * overflow (when the input is less than smallest int208 or
     * greater than largest int208).
     *
     * Counterpart to Solidity's `int208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     *
     * _Available since v4.7._
     */
    function toInt208(int256 value) internal pure returns (int208) {
        require(value >= type(int208).min && value <= type(int208).max, "SafeCast: value doesn't fit in 208 bits");
        return int208(value);
    }

    /**
     * @dev Returns the downcasted int200 from int256, reverting on
     * overflow (when the input is less than smallest int200 or
     * greater than largest int200).
     *
     * Counterpart to Solidity's `int200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     *
     * _Available since v4.7._
     */
    function toInt200(int256 value) internal pure returns (int200) {
        require(value >= type(int200).min && value <= type(int200).max, "SafeCast: value doesn't fit in 200 bits");
        return int200(value);
    }

    /**
     * @dev Returns the downcasted int192 from int256, reverting on
     * overflow (when the input is less than smallest int192 or
     * greater than largest int192).
     *
     * Counterpart to Solidity's `int192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     *
     * _Available since v4.7._
     */
    function toInt192(int256 value) internal pure returns (int192) {
        require(value >= type(int192).min && value <= type(int192).max, "SafeCast: value doesn't fit in 192 bits");
        return int192(value);
    }

    /**
     * @dev Returns the downcasted int184 from int256, reverting on
     * overflow (when the input is less than smallest int184 or
     * greater than largest int184).
     *
     * Counterpart to Solidity's `int184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     *
     * _Available since v4.7._
     */
    function toInt184(int256 value) internal pure returns (int184) {
        require(value >= type(int184).min && value <= type(int184).max, "SafeCast: value doesn't fit in 184 bits");
        return int184(value);
    }

    /**
     * @dev Returns the downcasted int176 from int256, reverting on
     * overflow (when the input is less than smallest int176 or
     * greater than largest int176).
     *
     * Counterpart to Solidity's `int176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     *
     * _Available since v4.7._
     */
    function toInt176(int256 value) internal pure returns (int176) {
        require(value >= type(int176).min && value <= type(int176).max, "SafeCast: value doesn't fit in 176 bits");
        return int176(value);
    }

    /**
     * @dev Returns the downcasted int168 from int256, reverting on
     * overflow (when the input is less than smallest int168 or
     * greater than largest int168).
     *
     * Counterpart to Solidity's `int168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     *
     * _Available since v4.7._
     */
    function toInt168(int256 value) internal pure returns (int168) {
        require(value >= type(int168).min && value <= type(int168).max, "SafeCast: value doesn't fit in 168 bits");
        return int168(value);
    }

    /**
     * @dev Returns the downcasted int160 from int256, reverting on
     * overflow (when the input is less than smallest int160 or
     * greater than largest int160).
     *
     * Counterpart to Solidity's `int160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     *
     * _Available since v4.7._
     */
    function toInt160(int256 value) internal pure returns (int160) {
        require(value >= type(int160).min && value <= type(int160).max, "SafeCast: value doesn't fit in 160 bits");
        return int160(value);
    }

    /**
     * @dev Returns the downcasted int152 from int256, reverting on
     * overflow (when the input is less than smallest int152 or
     * greater than largest int152).
     *
     * Counterpart to Solidity's `int152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     *
     * _Available since v4.7._
     */
    function toInt152(int256 value) internal pure returns (int152) {
        require(value >= type(int152).min && value <= type(int152).max, "SafeCast: value doesn't fit in 152 bits");
        return int152(value);
    }

    /**
     * @dev Returns the downcasted int144 from int256, reverting on
     * overflow (when the input is less than smallest int144 or
     * greater than largest int144).
     *
     * Counterpart to Solidity's `int144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     *
     * _Available since v4.7._
     */
    function toInt144(int256 value) internal pure returns (int144) {
        require(value >= type(int144).min && value <= type(int144).max, "SafeCast: value doesn't fit in 144 bits");
        return int144(value);
    }

    /**
     * @dev Returns the downcasted int136 from int256, reverting on
     * overflow (when the input is less than smallest int136 or
     * greater than largest int136).
     *
     * Counterpart to Solidity's `int136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     *
     * _Available since v4.7._
     */
    function toInt136(int256 value) internal pure returns (int136) {
        require(value >= type(int136).min && value <= type(int136).max, "SafeCast: value doesn't fit in 136 bits");
        return int136(value);
    }

    /**
     * @dev Returns the downcasted int128 from int256, reverting on
     * overflow (when the input is less than smallest int128 or
     * greater than largest int128).
     *
     * Counterpart to Solidity's `int128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     *
     * _Available since v3.1._
     */
    function toInt128(int256 value) internal pure returns (int128) {
        require(value >= type(int128).min && value <= type(int128).max, "SafeCast: value doesn't fit in 128 bits");
        return int128(value);
    }

    /**
     * @dev Returns the downcasted int120 from int256, reverting on
     * overflow (when the input is less than smallest int120 or
     * greater than largest int120).
     *
     * Counterpart to Solidity's `int120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     *
     * _Available since v4.7._
     */
    function toInt120(int256 value) internal pure returns (int120) {
        require(value >= type(int120).min && value <= type(int120).max, "SafeCast: value doesn't fit in 120 bits");
        return int120(value);
    }

    /**
     * @dev Returns the downcasted int112 from int256, reverting on
     * overflow (when the input is less than smallest int112 or
     * greater than largest int112).
     *
     * Counterpart to Solidity's `int112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     *
     * _Available since v4.7._
     */
    function toInt112(int256 value) internal pure returns (int112) {
        require(value >= type(int112).min && value <= type(int112).max, "SafeCast: value doesn't fit in 112 bits");
        return int112(value);
    }

    /**
     * @dev Returns the downcasted int104 from int256, reverting on
     * overflow (when the input is less than smallest int104 or
     * greater than largest int104).
     *
     * Counterpart to Solidity's `int104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     *
     * _Available since v4.7._
     */
    function toInt104(int256 value) internal pure returns (int104) {
        require(value >= type(int104).min && value <= type(int104).max, "SafeCast: value doesn't fit in 104 bits");
        return int104(value);
    }

    /**
     * @dev Returns the downcasted int96 from int256, reverting on
     * overflow (when the input is less than smallest int96 or
     * greater than largest int96).
     *
     * Counterpart to Solidity's `int96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     *
     * _Available since v4.7._
     */
    function toInt96(int256 value) internal pure returns (int96) {
        require(value >= type(int96).min && value <= type(int96).max, "SafeCast: value doesn't fit in 96 bits");
        return int96(value);
    }

    /**
     * @dev Returns the downcasted int88 from int256, reverting on
     * overflow (when the input is less than smallest int88 or
     * greater than largest int88).
     *
     * Counterpart to Solidity's `int88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     *
     * _Available since v4.7._
     */
    function toInt88(int256 value) internal pure returns (int88) {
        require(value >= type(int88).min && value <= type(int88).max, "SafeCast: value doesn't fit in 88 bits");
        return int88(value);
    }

    /**
     * @dev Returns the downcasted int80 from int256, reverting on
     * overflow (when the input is less than smallest int80 or
     * greater than largest int80).
     *
     * Counterpart to Solidity's `int80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     *
     * _Available since v4.7._
     */
    function toInt80(int256 value) internal pure returns (int80) {
        require(value >= type(int80).min && value <= type(int80).max, "SafeCast: value doesn't fit in 80 bits");
        return int80(value);
    }

    /**
     * @dev Returns the downcasted int72 from int256, reverting on
     * overflow (when the input is less than smallest int72 or
     * greater than largest int72).
     *
     * Counterpart to Solidity's `int72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     *
     * _Available since v4.7._
     */
    function toInt72(int256 value) internal pure returns (int72) {
        require(value >= type(int72).min && value <= type(int72).max, "SafeCast: value doesn't fit in 72 bits");
        return int72(value);
    }

    /**
     * @dev Returns the downcasted int64 from int256, reverting on
     * overflow (when the input is less than smallest int64 or
     * greater than largest int64).
     *
     * Counterpart to Solidity's `int64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     *
     * _Available since v3.1._
     */
    function toInt64(int256 value) internal pure returns (int64) {
        require(value >= type(int64).min && value <= type(int64).max, "SafeCast: value doesn't fit in 64 bits");
        return int64(value);
    }

    /**
     * @dev Returns the downcasted int56 from int256, reverting on
     * overflow (when the input is less than smallest int56 or
     * greater than largest int56).
     *
     * Counterpart to Solidity's `int56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     *
     * _Available since v4.7._
     */
    function toInt56(int256 value) internal pure returns (int56) {
        require(value >= type(int56).min && value <= type(int56).max, "SafeCast: value doesn't fit in 56 bits");
        return int56(value);
    }

    /**
     * @dev Returns the downcasted int48 from int256, reverting on
     * overflow (when the input is less than smallest int48 or
     * greater than largest int48).
     *
     * Counterpart to Solidity's `int48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     *
     * _Available since v4.7._
     */
    function toInt48(int256 value) internal pure returns (int48) {
        require(value >= type(int48).min && value <= type(int48).max, "SafeCast: value doesn't fit in 48 bits");
        return int48(value);
    }

    /**
     * @dev Returns the downcasted int40 from int256, reverting on
     * overflow (when the input is less than smallest int40 or
     * greater than largest int40).
     *
     * Counterpart to Solidity's `int40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     *
     * _Available since v4.7._
     */
    function toInt40(int256 value) internal pure returns (int40) {
        require(value >= type(int40).min && value <= type(int40).max, "SafeCast: value doesn't fit in 40 bits");
        return int40(value);
    }

    /**
     * @dev Returns the downcasted int32 from int256, reverting on
     * overflow (when the input is less than smallest int32 or
     * greater than largest int32).
     *
     * Counterpart to Solidity's `int32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     *
     * _Available since v3.1._
     */
    function toInt32(int256 value) internal pure returns (int32) {
        require(value >= type(int32).min && value <= type(int32).max, "SafeCast: value doesn't fit in 32 bits");
        return int32(value);
    }

    /**
     * @dev Returns the downcasted int24 from int256, reverting on
     * overflow (when the input is less than smallest int24 or
     * greater than largest int24).
     *
     * Counterpart to Solidity's `int24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     *
     * _Available since v4.7._
     */
    function toInt24(int256 value) internal pure returns (int24) {
        require(value >= type(int24).min && value <= type(int24).max, "SafeCast: value doesn't fit in 24 bits");
        return int24(value);
    }

    /**
     * @dev Returns the downcasted int16 from int256, reverting on
     * overflow (when the input is less than smallest int16 or
     * greater than largest int16).
     *
     * Counterpart to Solidity's `int16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     *
     * _Available since v3.1._
     */
    function toInt16(int256 value) internal pure returns (int16) {
        require(value >= type(int16).min && value <= type(int16).max, "SafeCast: value doesn't fit in 16 bits");
        return int16(value);
    }

    /**
     * @dev Returns the downcasted int8 from int256, reverting on
     * overflow (when the input is less than smallest int8 or
     * greater than largest int8).
     *
     * Counterpart to Solidity's `int8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     *
     * _Available since v3.1._
     */
    function toInt8(int256 value) internal pure returns (int8) {
        require(value >= type(int8).min && value <= type(int8).max, "SafeCast: value doesn't fit in 8 bits");
        return int8(value);
    }

    /**
     * @dev Converts an unsigned uint256 into a signed int256.
     *
     * Requirements:
     *
     * - input must be less than or equal to maxInt256.
     *
     * _Available since v3.0._
     */
    function toInt256(uint256 value) internal pure returns (int256) {
        // Note: Unsafe cast below is okay because `type(int256).max` is guaranteed to be positive
        require(value <= uint256(type(int256).max), "SafeCast: value doesn't fit in an int256");
        return int256(value);
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.6.0) (token/ERC20/IERC20.sol)

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC20 standard as defined in the EIP.
 */
interface IERC20 {
    /**
     * @dev Emitted when `value` tokens are moved from one account (`from`) to
     * another (`to`).
     *
     * Note that `value` may be zero.
     */
    event Transfer(address indexed from, address indexed to, uint256 value);

    /**
     * @dev Emitted when the allowance of a `spender` for an `owner` is set by
     * a call to {approve}. `value` is the new allowance.
     */
    event Approval(address indexed owner, address indexed spender, uint256 value);

    /**
     * @dev Returns the amount of tokens in existence.
     */
    function totalSupply() external view returns (uint256);

    /**
     * @dev Returns the amount of tokens owned by `account`.
     */
    function balanceOf(address account) external view returns (uint256);

    /**
     * @dev Moves `amount` tokens from the caller's account to `to`.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transfer(address to, uint256 amount) external returns (bool);

    /**
     * @dev Returns the remaining number of tokens that `spender` will be
     * allowed to spend on behalf of `owner` through {transferFrom}. This is
     * zero by default.
     *
     * This value changes when {approve} or {transferFrom} are called.
     */
    function allowance(address owner, address spender) external view returns (uint256);

    /**
     * @dev Sets `amount` as the allowance of `spender` over the caller's tokens.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * IMPORTANT: Beware that changing an allowance with this method brings the risk
     * that someone may use both the old and the new allowance by unfortunate
     * transaction ordering. One possible solution to mitigate this race
     * condition is to first reduce the spender's allowance to 0 and set the
     * desired value afterwards:
     * https://github.com/ethereum/EIPs/issues/20#issuecomment-263524729
     *
     * Emits an {Approval} event.
     */
    function approve(address spender, uint256 amount) external returns (bool);

    /**
     * @dev Moves `amount` tokens from `from` to `to` using the
     * allowance mechanism. `amount` is then deducted from the caller's
     * allowance.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address from,
        address to,
        uint256 amount
    ) external returns (bool);
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (token/ERC20/utils/SafeERC20.sol)

pragma solidity ^0.8.0;

import "../IERC20.sol";
import "../extensions/draft-IERC20Permit.sol";
import "../../../utils/Address.sol";

/**
 * @title SafeERC20
 * @dev Wrappers around ERC20 operations that throw on failure (when the token
 * contract returns false). Tokens that return no value (and instead revert or
 * throw on failure) are also supported, non-reverting calls are assumed to be
 * successful.
 * To use this library you can add a `using SafeERC20 for IERC20;` statement to your contract,
 * which allows you to call the safe operations as `token.safeTransfer(...)`, etc.
 */
library SafeERC20 {
    using Address for address;

    function safeTransfer(
        IERC20 token,
        address to,
        uint256 value
    ) internal {
        _callOptionalReturn(token, abi.encodeWithSelector(token.transfer.selector, to, value));
    }

    function safeTransferFrom(
        IERC20 token,
        address from,
        address to,
        uint256 value
    ) internal {
        _callOptionalReturn(token, abi.encodeWithSelector(token.transferFrom.selector, from, to, value));
    }

    /**
     * @dev Deprecated. This function has issues similar to the ones found in
     * {IERC20-approve}, and its usage is discouraged.
     *
     * Whenever possible, use {safeIncreaseAllowance} and
     * {safeDecreaseAllowance} instead.
     */
    function safeApprove(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        // safeApprove should only be called when setting an initial allowance,
        // or when resetting it to zero. To increase and decrease it, use
        // 'safeIncreaseAllowance' and 'safeDecreaseAllowance'
        require(
            (value == 0) || (token.allowance(address(this), spender) == 0),
            "SafeERC20: approve from non-zero to non-zero allowance"
        );
        _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, value));
    }

    function safeIncreaseAllowance(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        uint256 newAllowance = token.allowance(address(this), spender) + value;
        _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, newAllowance));
    }

    function safeDecreaseAllowance(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        unchecked {
            uint256 oldAllowance = token.allowance(address(this), spender);
            require(oldAllowance >= value, "SafeERC20: decreased allowance below zero");
            uint256 newAllowance = oldAllowance - value;
            _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, newAllowance));
        }
    }

    function safePermit(
        IERC20Permit token,
        address owner,
        address spender,
        uint256 value,
        uint256 deadline,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) internal {
        uint256 nonceBefore = token.nonces(owner);
        token.permit(owner, spender, value, deadline, v, r, s);
        uint256 nonceAfter = token.nonces(owner);
        require(nonceAfter == nonceBefore + 1, "SafeERC20: permit did not succeed");
    }

    /**
     * @dev Imitates a Solidity high-level call (i.e. a regular function call to a contract), relaxing the requirement
     * on the return value: the return value is optional (but if data is returned, it must not be false).
     * @param token The token targeted by the call.
     * @param data The call data (encoded using abi.encode or one of its variants).
     */
    function _callOptionalReturn(IERC20 token, bytes memory data) private {
        // We need to perform a low level call here, to bypass Solidity's return data size checking mechanism, since
        // we're implementing it ourselves. We use {Address.functionCall} to perform this call, which verifies that
        // the target address contains contract code and also asserts for success in the low-level call.

        bytes memory returndata = address(token).functionCall(data, "SafeERC20: low-level call failed");
        if (returndata.length > 0) {
            // Return data is optional
            require(abi.decode(returndata, (bool)), "SafeERC20: ERC20 operation did not succeed");
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

/// @title BitMath
/// @dev Library for computing the bit properties of unsigned integer
library BitMath {
    /// @notice Returns the index of the most significant bit of the number,
    ///     where the least significant bit is at index 0 and the most significant bit is at index 255
    /// @dev The function satisfies the property:
    ///     x >= 2**mostSignificantBit(x) and x < 2**(mostSignificantBit(x)+1)
    /// @param x the value for which to compute the most significant bit, must be greater than 0
    /// @return r the index of the most significant bit
    function mostSignificantBit(uint256 x) internal pure returns (uint8 r) {
        require(x > 0);

        unchecked {
            if (x >= 0x100000000000000000000000000000000) {
                x >>= 128;
                r += 128;
            }
            if (x >= 0x10000000000000000) {
                x >>= 64;
                r += 64;
            }
            if (x >= 0x100000000) {
                x >>= 32;
                r += 32;
            }
            if (x >= 0x10000) {
                x >>= 16;
                r += 16;
            }
            if (x >= 0x100) {
                x >>= 8;
                r += 8;
            }
            if (x >= 0x10) {
                x >>= 4;
                r += 4;
            }
            if (x >= 0x4) {
                x >>= 2;
                r += 2;
            }
            if (x >= 0x2) {
                r += 1;
            }
        }
    }

    /// @notice Returns the index of the least significant bit of the number,
    ///     where the least significant bit is at index 0 and the most significant bit is at index 255
    /// @dev The function satisfies the property:
    ///     (x & 2**leastSignificantBit(x)) != 0 and (x & (2**(leastSignificantBit(x)) - 1)) == 0)
    /// @param x the value for which to compute the least significant bit, must be greater than 0
    /// @return r the index of the least significant bit
    function leastSignificantBit(uint256 x) internal pure returns (uint8 r) {
        require(x > 0);

        r = 255;
        unchecked {
            if (x & type(uint128).max > 0) {
                r -= 128;
            } else {
                x >>= 128;
            }
            if (x & type(uint64).max > 0) {
                r -= 64;
            } else {
                x >>= 64;
            }
            if (x & type(uint32).max > 0) {
                r -= 32;
            } else {
                x >>= 32;
            }
            if (x & type(uint16).max > 0) {
                r -= 16;
            } else {
                x >>= 16;
            }
            if (x & type(uint8).max > 0) {
                r -= 8;
            } else {
                x >>= 8;
            }
            if (x & 0xf > 0) {
                r -= 4;
            } else {
                x >>= 4;
            }
            if (x & 0x3 > 0) {
                r -= 2;
            } else {
                x >>= 2;
            }
            if (x & 0x1 > 0) {
                r -= 1;
            }
        }
    }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

library FixedPointX128 {
    uint160 internal constant RESOLUTION = 1 << 128;
    uint160 internal constant Q = 0x100000000000000000000000000000000;
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

library FixedPointX96 {
    uint160 internal constant RESOLUTION = 1 << 96;
    uint160 internal constant Q = 0x1000000000000000000000000;
    uint160 internal constant Q_2 = 0x2000000000000000000000000;
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity ^0.8.0;

library FixedPointX192 {
    uint256 internal constant RESOLUTION = 1 << 192;
    uint256 internal constant Q = 0x1000000000000000000000000000000000000000000000000;
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/Address.sol)

pragma solidity ^0.8.1;

/**
 * @dev Collection of functions related to the address type
 */
library Address {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     * ====
     *
     * [IMPORTANT]
     * ====
     * You shouldn't rely on `isContract` to protect against flash loan attacks!
     *
     * Preventing calls from contracts is highly discouraged. It breaks composability, breaks support for smart wallets
     * like Gnosis Safe, and does not provide security since it can be circumvented by calling from a contract
     * constructor.
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // This method relies on extcodesize/address.code.length, which returns 0
        // for contracts in construction, since the code is only stored at the end
        // of the constructor execution.

        return account.code.length > 0;
    }

    /**
     * @dev Replacement for Solidity's `transfer`: sends `amount` wei to
     * `recipient`, forwarding all available gas and reverting on errors.
     *
     * https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
     * of certain opcodes, possibly making contracts go over the 2300 gas limit
     * imposed by `transfer`, making them unable to receive funds via
     * `transfer`. {sendValue} removes this limitation.
     *
     * https://diligence.consensys.net/posts/2019/09/stop-using-soliditys-transfer-now/[Learn more].
     *
     * IMPORTANT: because control is transferred to `recipient`, care must be
     * taken to not create reentrancy vulnerabilities. Consider using
     * {ReentrancyGuard} or the
     * https://solidity.readthedocs.io/en/v0.5.11/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        require(address(this).balance >= amount, "Address: insufficient balance");

        (bool success, ) = recipient.call{value: amount}("");
        require(success, "Address: unable to send value, recipient may have reverted");
    }

    /**
     * @dev Performs a Solidity function call using a low level `call`. A
     * plain `call` is an unsafe replacement for a function call: use this
     * function instead.
     *
     * If `target` reverts with a revert reason, it is bubbled up by this
     * function (like regular Solidity function calls).
     *
     * Returns the raw returned data. To convert to the expected return value,
     * use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
     *
     * Requirements:
     *
     * - `target` must be a contract.
     * - calling `target` with `data` must not revert.
     *
     * _Available since v3.1._
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCall(target, data, "Address: low-level call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`], but with
     * `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, value, "Address: low-level call with value failed");
    }

    /**
     * @dev Same as {xref-Address-functionCallWithValue-address-bytes-uint256-}[`functionCallWithValue`], but
     * with `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(address(this).balance >= value, "Address: insufficient balance for call");
        require(isContract(target), "Address: call to non-contract");

        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResult(success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
        return functionStaticCall(target, data, "Address: low-level static call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        require(isContract(target), "Address: static call to non-contract");

        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResult(success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionDelegateCall(target, data, "Address: low-level delegate call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(isContract(target), "Address: delegate call to non-contract");

        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResult(success, returndata, errorMessage);
    }

    /**
     * @dev Tool to verifies that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            // Look for revert reason and bubble it up if present
            if (returndata.length > 0) {
                // The easiest way to bubble the revert reason is using memory via assembly
                /// @solidity memory-safe-assembly
                assembly {
                    let returndata_size := mload(returndata)
                    revert(add(32, returndata), returndata_size)
                }
            } else {
                revert(errorMessage);
            }
        }
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (token/ERC20/extensions/draft-IERC20Permit.sol)

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC20 Permit extension allowing approvals to be made via signatures, as defined in
 * https://eips.ethereum.org/EIPS/eip-2612[EIP-2612].
 *
 * Adds the {permit} method, which can be used to change an account's ERC20 allowance (see {IERC20-allowance}) by
 * presenting a message signed by the account. By not relying on {IERC20-approve}, the token holder account doesn't
 * need to send a transaction, and thus is not required to hold Ether at all.
 */
interface IERC20Permit {
    /**
     * @dev Sets `value` as the allowance of `spender` over ``owner``'s tokens,
     * given ``owner``'s signed approval.
     *
     * IMPORTANT: The same issues {IERC20-approve} has related to transaction
     * ordering also apply here.
     *
     * Emits an {Approval} event.
     *
     * Requirements:
     *
     * - `spender` cannot be the zero address.
     * - `deadline` must be a timestamp in the future.
     * - `v`, `r` and `s` must be a valid `secp256k1` signature from `owner`
     * over the EIP712-formatted function arguments.
     * - the signature must use ``owner``'s current nonce (see {nonces}).
     *
     * For more information on the signature format, see the
     * https://eips.ethereum.org/EIPS/eip-2612#specification[relevant EIP
     * section].
     */
    function permit(
        address owner,
        address spender,
        uint256 value,
        uint256 deadline,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) external;

    /**
     * @dev Returns the current nonce for `owner`. This value must be
     * included whenever a signature is generated for {permit}.
     *
     * Every successful call to {permit} increases ``owner``'s nonce by one. This
     * prevents a signature from being used multiple times.
     */
    function nonces(address owner) external view returns (uint256);

    /**
     * @dev Returns the domain separator used in the encoding of the signature for {permit}, as defined by {EIP712}.
     */
    // solhint-disable-next-line func-name-mixedcase
    function DOMAIN_SEPARATOR() external view returns (bytes32);
}

{
  "optimizer": {
    "enabled": true,
    "runs": 8500
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "libraries": {}
}

[{"inputs":[],"stateMutability":"nonpayable","type":"constructor"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"uint64","name":"bundleId","type":"uint64"},{"indexed":false,"internalType":"int256","name":"makerAmountTotal","type":"int256"},{"indexed":false,"internalType":"int256","name":"makerAmountRemaining","type":"int256"}],"name":"ChangeBundleForSettleOrder","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"uint64","name":"bundleId","type":"uint64"},{"indexed":false,"internalType":"int256","name":"makerAmountRemaining","type":"int256"},{"indexed":false,"internalType":"uint256","name":"amountIn","type":"uint256"},{"indexed":false,"internalType":"uint128","name":"takerFeeAmountIn","type":"uint128"}],"name":"ChangeBundleForSwap","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"address","name":"sender","type":"address"},{"indexed":true,"internalType":"address","name":"recipient","type":"address"},{"indexed":false,"internalType":"uint128","name":"amount0","type":"uint128"},{"indexed":false,"internalType":"uint128","name":"amount1","type":"uint128"}],"name":"Collect","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"address","name":"sender","type":"address"},{"indexed":true,"internalType":"address","name":"recipient","type":"address"},{"indexed":false,"internalType":"uint256","name":"amount0","type":"uint256"},{"indexed":false,"internalType":"uint256","name":"amount1","type":"uint256"},{"indexed":false,"internalType":"uint128","name":"paid0","type":"uint128"},{"indexed":false,"internalType":"uint128","name":"paid1","type":"uint128"}],"name":"Flash","type":"event"},{"anonymous":false,"inputs":[{"indexed":false,"internalType":"uint160","name":"priceX96","type":"uint160"},{"indexed":false,"internalType":"int24","name":"boundary","type":"int24"}],"name":"Initialize","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"uint256","name":"orderId","type":"uint256"},{"indexed":true,"internalType":"address","name":"recipient","type":"address"},{"indexed":true,"internalType":"uint64","name":"bundleId","type":"uint64"},{"indexed":false,"internalType":"bool","name":"zero","type":"bool"},{"indexed":false,"internalType":"int24","name":"boundaryLower","type":"int24"},{"indexed":false,"internalType":"uint128","name":"amount","type":"uint128"}],"name":"PlaceMakerOrder","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"uint256","name":"orderId","type":"uint256"},{"indexed":false,"internalType":"uint128","name":"makerAmountOut","type":"uint128"},{"indexed":false,"internalType":"uint128","name":"takerAmountOut","type":"uint128"},{"indexed":false,"internalType":"uint128","name":"takerFeeAmountOut","type":"uint128"}],"name":"SettleMakerOrder","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"address","name":"sender","type":"address"},{"indexed":true,"internalType":"address","name":"recipient","type":"address"},{"indexed":false,"internalType":"int256","name":"amount0","type":"int256"},{"indexed":false,"internalType":"int256","name":"amount1","type":"int256"},{"indexed":false,"internalType":"uint160","name":"priceX96","type":"uint160"},{"indexed":false,"internalType":"int24","name":"boundary","type":"int24"}],"name":"Swap","type":"event"},{"inputs":[{"internalType":"int24","name":"","type":"int24"}],"name":"boundaries0","outputs":[{"internalType":"uint64","name":"bundle0Id","type":"uint64"},{"internalType":"uint64","name":"bundle1Id","type":"uint64"},{"internalType":"uint128","name":"makerAmountRemaining","type":"uint128"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"int24","name":"","type":"int24"}],"name":"boundaries1","outputs":[{"internalType":"uint64","name":"bundle0Id","type":"uint64"},{"internalType":"uint64","name":"bundle1Id","type":"uint64"},{"internalType":"uint128","name":"makerAmountRemaining","type":"uint128"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"int16","name":"","type":"int16"}],"name":"boundaryBitmaps0","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"int16","name":"","type":"int16"}],"name":"boundaryBitmaps1","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint64","name":"","type":"uint64"}],"name":"bundles","outputs":[{"internalType":"int24","name":"boundaryLower","type":"int24"},{"internalType":"bool","name":"zero","type":"bool"},{"internalType":"uint128","name":"makerAmountTotal","type":"uint128"},{"internalType":"uint128","name":"makerAmountRemaining","type":"uint128"},{"internalType":"uint128","name":"takerAmountRemaining","type":"uint128"},{"internalType":"uint128","name":"takerFeeAmountRemaining","type":"uint128"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"recipient","type":"address"},{"internalType":"uint128","name":"amount0Requested","type":"uint128"},{"internalType":"uint128","name":"amount1Requested","type":"uint128"}],"name":"collect","outputs":[{"internalType":"uint128","name":"amount0","type":"uint128"},{"internalType":"uint128","name":"amount1","type":"uint128"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"address","name":"recipient","type":"address"},{"internalType":"uint256","name":"amount0","type":"uint256"},{"internalType":"uint256","name":"amount1","type":"uint256"},{"internalType":"bytes","name":"data","type":"bytes"}],"name":"flash","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"components":[{"internalType":"uint160","name":"priceX96","type":"uint160"},{"internalType":"address","name":"recipient","type":"address"},{"components":[{"internalType":"int24","name":"boundaryLower","type":"int24"},{"internalType":"uint128","name":"amount","type":"uint128"}],"internalType":"struct IGridParameters.BoundaryLowerWithAmountParameters[]","name":"orders0","type":"tuple[]"},{"components":[{"internalType":"int24","name":"boundaryLower","type":"int24"},{"internalType":"uint128","name":"amount","type":"uint128"}],"internalType":"struct IGridParameters.BoundaryLowerWithAmountParameters[]","name":"orders1","type":"tuple[]"}],"internalType":"struct IGridParameters.InitializeParameters","name":"parameters","type":"tuple"},{"internalType":"bytes","name":"data","type":"bytes"}],"name":"initialize","outputs":[{"internalType":"uint256[]","name":"orderIds0","type":"uint256[]"},{"internalType":"uint256[]","name":"orderIds1","type":"uint256[]"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256","name":"","type":"uint256"}],"name":"orders","outputs":[{"internalType":"uint64","name":"bundleId","type":"uint64"},{"internalType":"address","name":"owner","type":"address"},{"internalType":"uint128","name":"amount","type":"uint128"}],"stateMutability":"view","type":"function"},{"inputs":[{"components":[{"internalType":"address","name":"recipient","type":"address"},{"internalType":"bool","name":"zero","type":"bool"},{"internalType":"int24","name":"boundaryLower","type":"int24"},{"internalType":"uint128","name":"amount","type":"uint128"}],"internalType":"struct IGridParameters.PlaceOrderParameters","name":"parameters","type":"tuple"},{"internalType":"bytes","name":"data","type":"bytes"}],"name":"placeMakerOrder","outputs":[{"internalType":"uint256","name":"orderId","type":"uint256"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"components":[{"internalType":"address","name":"recipient","type":"address"},{"internalType":"bool","name":"zero","type":"bool"},{"components":[{"internalType":"int24","name":"boundaryLower","type":"int24"},{"internalType":"uint128","name":"amount","type":"uint128"}],"internalType":"struct IGridParameters.BoundaryLowerWithAmountParameters[]","name":"orders","type":"tuple[]"}],"internalType":"struct IGridParameters.PlaceOrderInBatchParameters","name":"parameters","type":"tuple"},{"internalType":"bytes","name":"data","type":"bytes"}],"name":"placeMakerOrderInBatch","outputs":[{"internalType":"uint256[]","name":"orderIds","type":"uint256[]"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"resolution","outputs":[{"internalType":"int24","name":"","type":"int24"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256","name":"orderId","type":"uint256"}],"name":"settleMakerOrder","outputs":[{"internalType":"uint128","name":"amount0","type":"uint128"},{"internalType":"uint128","name":"amount1","type":"uint128"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"address","name":"recipient","type":"address"},{"internalType":"uint256","name":"orderId","type":"uint256"},{"internalType":"bool","name":"unwrapWETH9","type":"bool"}],"name":"settleMakerOrderAndCollect","outputs":[{"internalType":"uint128","name":"amount0","type":"uint128"},{"internalType":"uint128","name":"amount1","type":"uint128"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"address","name":"recipient","type":"address"},{"internalType":"uint256[]","name":"orderIds","type":"uint256[]"},{"internalType":"bool","name":"unwrapWETH9","type":"bool"}],"name":"settleMakerOrderAndCollectInBatch","outputs":[{"internalType":"uint128","name":"amount0Total","type":"uint128"},{"internalType":"uint128","name":"amount1Total","type":"uint128"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"slot0","outputs":[{"internalType":"uint160","name":"priceX96","type":"uint160"},{"internalType":"int24","name":"boundary","type":"int24"},{"internalType":"uint32","name":"blockTimestamp","type":"uint32"},{"internalType":"bool","name":"unlocked","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"recipient","type":"address"},{"internalType":"bool","name":"zeroForOne","type":"bool"},{"internalType":"int256","name":"amountSpecified","type":"int256"},{"internalType":"uint160","name":"priceLimitX96","type":"uint160"},{"internalType":"bytes","name":"data","type":"bytes"}],"name":"swap","outputs":[{"internalType":"int256","name":"amount0","type":"int256"},{"internalType":"int256","name":"amount1","type":"int256"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"takerFee","outputs":[{"internalType":"int24","name":"","type":"int24"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"token0","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"token1","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"","type":"address"}],"name":"tokensOweds","outputs":[{"internalType":"uint128","name":"token0","type":"uint128"},{"internalType":"uint128","name":"token1","type":"uint128"}],"stateMutability":"view","type":"function"},{"stateMutability":"payable","type":"receive"}]

6101406040523480156200001257600080fd5b50336001600160a01b031663890357306040518163ffffffff1660e01b815260040160c06040518083038186803b1580156200004d57600080fd5b505afa15801562000062573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190620000889190620000ec565b6001600160a01b0390811660e05290811661010052600291820b6101205291900b60c05290811660a052166080526200016d565b80516001600160a01b0381168114620000d457600080fd5b919050565b8051600281900b8114620000d457600080fd5b60008060008060008060c087890312156200010657600080fd5b6200011187620000bc565b95506200012160208801620000bc565b94506200013160408801620000d9565b93506200014160608801620000d9565b92506200015160808801620000bc565b91506200016160a08801620000bc565b90509295509295509295565b60805160a05160c05160e0516101005161012051615f3e6200026c600039600081816103400152611bb2015260008181610b4c015261160f01526000613f410152600081816104da0152818161097001528181610a35015281816115e601528181611eee01528181612e2601528181612e5e01526141ec0152600081816106d301528181610ded015281816115be0152818161227b015281816122bc015281816126a201528181612837015281816129010152612b2301526000818161018c01528181610db2015281816115960152818161225a015281816122dd01528181612564015281816127b6015281816128c60152612b4c0152615f3e6000f3fe60806040526004361061016e5760003560e01c80637e071773116100cb578063b703179d1161007f578063dd5f8a7b11610059578063dd5f8a7b146106f5578063f12e768c14610715578063f8421a311461073557600080fd5b8063b703179d1461063a578063d18b83d114610667578063d21220a7146106c157600080fd5b80638455c01d116100b05780638455c01d14610564578063a54cfb2314610584578063a85c38ef146105a457600080fd5b80637e071773146104fc57806380281adb1461053757600080fd5b8063490e6cbc1161012257806360d49d531161010757806360d49d53146103f8578063624ac9a71461041857806371e21495146104c857600080fd5b8063490e6cbc1461037557806356ebe63c1461039757600080fd5b8063285d937911610153578063285d9379146102005780633850c7bd1461028a57806343f0179b1461032e57600080fd5b80630dfe16811461017a578063128acb08146101cb57600080fd5b3661017557005b600080fd5b34801561018657600080fd5b506101ae7f000000000000000000000000000000000000000000000000000000000000000081565b6040516001600160a01b0390911681526020015b60405180910390f35b3480156101d757600080fd5b506101eb6101e63660046151e6565b610763565b604080519283526020830191909152016101c2565b34801561020c57600080fd5b5061025a61021b36600461527d565b60026020526000908152604090205467ffffffffffffffff8082169168010000000000000000810490911690600160801b90046001600160801b031683565b6040805167ffffffffffffffff94851681529390921660208401526001600160801b0316908201526060016101c2565b34801561029657600080fd5b506000546102f4906001600160a01b0381169074010000000000000000000000000000000000000000810460020b9077010000000000000000000000000000000000000000000000810463ffffffff1690600160d81b900460ff1684565b604080516001600160a01b03909516855260029390930b602085015263ffffffff90911691830191909152151560608201526080016101c2565b34801561033a57600080fd5b506103627f000000000000000000000000000000000000000000000000000000000000000081565b60405160029190910b81526020016101c2565b34801561038157600080fd5b50610395610390366004615298565b610d34565b005b3480156103a357600080fd5b506103d86103b2366004615302565b6009602052600090815260409020546001600160801b0380821691600160801b90041682565b604080516001600160801b039384168152929091166020830152016101c2565b34801561040457600080fd5b506103d8610413366004615336565b610f4f565b34801561042457600080fd5b5061048561043336600461537b565b6008602052600090815260409020805460018201546002928301549282900b9260ff6301000000840416926001600160801b0364010000000090910481169280821692600160801b9091048216911686565b6040805160029790970b875294151560208701526001600160801b03938416948601949094529082166060850152811660808401521660a082015260c0016101c2565b3480156104d457600080fd5b506103627f000000000000000000000000000000000000000000000000000000000000000081565b34801561050857600080fd5b506105296105173660046153a5565b60036020526000908152604090205481565b6040519081526020016101c2565b34801561054357600080fd5b506105296105523660046153a5565b60046020526000908152604090205481565b34801561057057600080fd5b506103d861057f3660046153c8565b611045565b34801561059057600080fd5b506103d861059f36600461551b565b6110e7565b3480156105b057600080fd5b506106036105bf3660046155cd565b6006602052600090815260409020805460019091015467ffffffffffffffff8216916801000000000000000090046001600160a01b0316906001600160801b031683565b6040805167ffffffffffffffff90941684526001600160a01b0390921660208401526001600160801b0316908201526060016101c2565b34801561064657600080fd5b5061065a61065536600461567e565b61115b565b6040516101c29190615776565b34801561067357600080fd5b5061025a61068236600461527d565b60016020526000908152604090205467ffffffffffffffff8082169168010000000000000000810490911690600160801b90046001600160801b031683565b3480156106cd57600080fd5b506101ae7f000000000000000000000000000000000000000000000000000000000000000081565b34801561070157600080fd5b50610529610710366004615789565b61120e565b34801561072157600080fd5b506103d86107303660046155cd565b6112d5565b34801561074157600080fd5b50610755610750366004615820565b611407565b6040516101c29291906158e7565b600080856107b85760405162461bcd60e51b815260206004820152600560248201527f475f41535a00000000000000000000000000000000000000000000000000000060448201526064015b60405180910390fd5b604080516080810182526000546001600160a01b038116825274010000000000000000000000000000000000000000810460020b602083015277010000000000000000000000000000000000000000000000810463ffffffff1692820192909252600160d81b90910460ff1615156060820181905261087b5760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b8761089e5780600001516001600160a01b0316866001600160a01b0316116108b8565b80600001516001600160a01b0316866001600160a01b0316105b6109045760405162461bcd60e51b815260206004820152600560248201527f475f504c4f00000000000000000000000000000000000000000000000000000060448201526064016107af565b6000805460ff60d81b1916815560408051610180810182528a1515815260208082018b9052918101839052606081018390526080810183905283516001600160a01b0390811660a0830152891660c0820152908301805160020b60e083015251610100820190610994907f00000000000000000000000000000000000000000000000000000000000000006118ea565b60020b81526000602082018190526040820181905260609091018190529091506109be8a15611924565b905060006109cc8b1561193a565b90505b6020830151158015906109e55750826101600151155b15610a9f5760e083015160a08401516101008501805160020b6000908152602085905260408120549151875191948594610a5a94899492939192600160801b9091046001600160801b03161515917f000000000000000000000000000000000000000000000000000000000000000091611950565b6001600160a01b039081166101408a015216610120880152909250905080610a83575050610a9f565b610a8f84848488611a80565b1515610160860152506109cf9050565b83600001516001600160a01b03168360a001516001600160a01b031614610c8457610acd8360a00151611f42565b600290810b60e0850181905260208601516000920b14801590610b0357504290508063ffffffff16856040015163ffffffff1614155b15610bfb5760208501516040517fcc2ef58c00000000000000000000000000000000000000000000000000000000815260029190910b600482015263ffffffff821660248201527f00000000000000000000000000000000000000000000000000000000000000006001600160a01b03169063cc2ef58c90604401600060405180830381600087803b158015610b9857600080fd5b505af1158015610bac573d6000803e3d6000fd5b5050600080547fffffffffff00000000ffffffffffffffffffffffffffffffffffffffffffffff167701000000000000000000000000000000000000000000000063ffffffff86160217905550505b5060a083015160e0840151600080546001600160a01b039093167fffffffffffffffffffffffff000000000000000000000000000000000000000062ffffff9093167401000000000000000000000000000000000000000002929092167fffffffffffffffffff0000000000000000000000000000000000000000000000909316929092171790555b610c90838d8a8a61222b565b90965094506001600160a01b038c16336001600160a01b03167f41e82c9c8c68651be91e14fa6bb6d577822b5f6b66fda7d7f365faed56e2855e88888760a001518860e00151604051610d08949392919093845260208401929092526001600160a01b0316604083015260020b606082015260800190565b60405180910390a350506000805460ff60d81b1916600160d81b17905550919890975095505050505050565b600054600160d81b900460ff16610d8f5760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b6000805460ff60d81b19168155808515610dd857610dab612533565b9150610dd87f000000000000000000000000000000000000000000000000000000000000000088886125ec565b8415610e1357610de6612671565b9050610e137f000000000000000000000000000000000000000000000000000000000000000088876125ec565b6040517f7b17fb300000000000000000000000000000000000000000000000000000000081523390637b17fb3090610e519087908790600401615955565b600060405180830381600087803b158015610e6b57600080fd5b505af1158015610e7f573d6000803e3d6000fd5b505050506000806000881115610eb1576000610e99612533565b9050610ead610ea88683615998565b6126d9565b9250505b8615610ed4576000610ec1612671565b9050610ed0610ea88583615998565b9150505b60408051898152602081018990526001600160801b03848116828401528316606082015290516001600160a01b038b169133917fab4f19a9f2e46fd590cecef736d778467430de8fd1f41cd7a7e3d23df9a86f4c9181900360800190a350506000805460ff60d81b1916600160d81b17905550505050505050565b600080548190600160d81b900460ff16610fad5760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b6000805460ff60d81b19168155338152600960205260409020610fd29086868661275c565b604080516001600160801b0380851682528316602082015281519395509193506001600160a01b0388169233927f38c069c2e9bc192f8cf4f1b85be791ccc0d04bb12c4ca71a3fbfe96ea0932dd592908290030190a36000805460ff60d81b1916600160d81b1790559094909350915050565b600080548190600160d81b900460ff166110a35760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b6000805460ff60d81b191690556110b984612869565b90925090506110ca858383866128b1565b6000805460ff60d81b1916600160d81b1790559094909350915050565b600080548190600160d81b900460ff166111455760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b6000805460ff60d81b191690556110b98461297f565b600054606090600160d81b900460ff166111b95760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b6000805460ff60d81b191681558451602086015160408701516111dd929190612a2b565b602087015191935091506111f390828686612b17565b506000805460ff60d81b1916600160d81b1790559392505050565b60008054600160d81b900460ff1661126a5760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b6000805460ff60d81b1916905561127f612d7a565b905061129e818560000151866020015187604001518860600151612d95565b6112bb846020015185606001516001600160801b03168585612b17565b6000805460ff60d81b1916600160d81b1790559392505050565b600080548190600160d81b900460ff166113335760405162461bcd60e51b81526004016107af9060208082526004908201527f475f474c00000000000000000000000000000000000000000000000000000000604082015260600190565b6000805460ff60d81b1916905561134983612869565b33600090815260096020526040902091935091506001600160801b038316156113a75780546113829084906001600160801b03166159af565b81546fffffffffffffffffffffffffffffffff19166001600160801b03919091161781555b6001600160801b038216156113ec5780546113d3908390600160801b90046001600160801b03166159af565b81546001600160801b03918216600160801b0291161781555b506000805460ff60d81b1916600160d81b1790559092909150565b60005460609081906001600160a01b0316156114655760405162461bcd60e51b815260206004820152600560248201527f475f47414900000000000000000000000000000000000000000000000000000060448201526064016107af565b84516114709061326e565b6114bc5760405162461bcd60e51b815260206004820152600560248201527f475f504f5200000000000000000000000000000000000000000000000000000060448201526064016107af565b6000856040015151116115115760405162461bcd60e51b815260206004820152600560248201527f475f4f4e4500000000000000000000000000000000000000000000000000000060448201526064016107af565b6000856060015151116115665760405162461bcd60e51b815260206004820152600560248201527f475f4f4e4500000000000000000000000000000000000000000000000000000060448201526064016107af565b6040517f9dce66510000000000000000000000000000000000000000000000000000000081526001600160a01b037f0000000000000000000000000000000000000000000000000000000000000000811660048301527f0000000000000000000000000000000000000000000000000000000000000000811660248301527f000000000000000000000000000000000000000000000000000000000000000060020b60448301527f00000000000000000000000000000000000000000000000000000000000000001690639dce665190606401600060405180830381600087803b15801561165357600080fd5b505af1158015611667573d6000803e3d6000fd5b50505050600061167a8660000151611f42565b6040805160808101825288516001600160a01b03908116808352600285900b60208085018290524263ffffffff168587018190526000606090960186905285547fffffffffffffffffff0000000000000000000000000000000000000000000000169093177401000000000000000000000000000000000000000062ffffff891602177fffffffff0000000000ffffffffffffffffffffffffffffffffffffffffffffff167701000000000000000000000000000000000000000000000090930260ff60d81b1916929092179093558a518451921682528101919091529192507f98636036cb66a9c19a37435efc1e90142190214e8abeb821bdba3f2990dd4c95910160405180910390a1600061179b876020015160018960400151612a2b565b809250819550505060006117b9886020015160008a60600151612a2b565b90945090506000806117c9612533565b6117d1612671565b915091506117dc3390565b6001600160a01b0316638f61c9f785858c8c6040518563ffffffff1660e01b815260040161180d94939291906159da565b600060405180830381600087803b15801561182757600080fd5b505af115801561183b573d6000803e3d6000fd5b5050505060008061184a612533565b611852612671565b9092509050856118628584615998565b101580156118795750846118768483615998565b10155b6118c55760405162461bcd60e51b815260206004820152600560248201527f475f54504600000000000000000000000000000000000000000000000000000060448201526064016107af565b50506000805460ff60d81b1916600160d81b1790555094989397509295505050505050565b60008160020b828360020b8560020b81611906576119066159fa565b070160020b81611918576119186159fa565b07830390505b92915050565b60008161193257600461191e565b600392915050565b60008161194857600261191e565b600192915050565b6000808080806119608888615a29565b905088156119fc5785156119b7576000611979886132ae565b90508a6001600160a01b0316816001600160a01b031610156119b157876001826119a2856132ae565b95509550955095505050611a72565b506119fc565b60006119c2826132ae565b90508a6001600160a01b0316816001600160a01b031611156119fa578760016119ea8a6132ae565b8395509550955095505050611a72565b505b85158015611a0f57508a60020b8160020b145b611a19578a611a1b565b865b9a505b611a278b61358a565b15611a7057611a388c8c8a896135cb565b90955093508315611a6857846001611a4f876132ae565b611a5a8b89016132ae565b945094509450945050611a72565b849a50611a1e565b505b975097509750979350505050565b604080516080810182526101208301516001600160a01b0390811682526101408401511660208201526000918101829052606081018290528251611ada578060200151611ad582600001518560a00151613795565b611af1565b8060000151611af182602001518560a001516137bf565b6001600160a01b03908116606084015216604082015282518015611b2f57508260c001516001600160a01b031681606001516001600160a01b031611155b80611b5e57508251158015611b5e57508260c001516001600160a01b031681606001516001600160a01b031610155b15611b6d576001915050611f3a565b600284900b60009081526020868152604080832060608501519185015160c0880151938801518254929594611bd69493909190600160801b90046001600160801b03167f00000000000000000000000000000000000000000000000000000000000000006137e0565b905080604001516001600160801b031660001415611bfa5760019350505050611f3a565b80602001518560400151611c0e9190615a70565b604086015260608082015190860151611c30916001600160801b031690615a70565b606086015260408101516080860151611c52916001600160801b031690615a70565b60808601526020850151600013611c9c5780606001516001600160801b0316611c7e8260200151613858565b8660200151611c8d9190615a88565b611c979190615a88565b611cb9565b80604001516001600160801b03168560200151611cb99190615afc565b602080870191909152825467ffffffffffffffff16600090815260088252604080822092840151908401516060850151611cf692859290916138f0565b8454604082015191925067ffffffffffffffff16907f700dec44bb198379f48560c2e4ea3ce1a6485d0beaf623dbcead52c7850ff3df90611d3f906001600160801b0316615b70565b835160808501516040805193845260208401929092526001600160801b03169082015260600160405180910390a260018201546001600160801b0316611eb657835468010000000000000000810467ffffffffffffffff166fffffffffffffffffffffffffffffffff1990911617845560608101516001600160801b031615611eb657835467ffffffffffffffff16600090815260086020908152604090912090820151606083015160a0840151611dfa92849290916138f0565b8554604082015191935067ffffffffffffffff16907f700dec44bb198379f48560c2e4ea3ce1a6485d0beaf623dbcead52c7850ff3df90611e43906001600160801b0316615b70565b845160808601516040805193845260208401929092526001600160801b03169082015260600160405180910390a260018101546001600160801b0316611eb457845468010000000000000000810467ffffffffffffffff166fffffffffffffffffffffffffffffffff199091161785555b505b5050604081015182546001600160801b03600160801b8083048216939093038082169384029190921617845590611f1257611f1289887f0000000000000000000000000000000000000000000000000000000000000000613ab7565b50516001600160a01b031660a0850152505050600282900b60e0820181905261010082015260005b949350505050565b600077ffffffffffffffffffffffffffffffffffffffff00000000602083901b166001600160801b03811160071b81811c67ffffffffffffffff811160061b90811c63ffffffff811160051b90811c61ffff811160041b90811c60ff8111600390811b91821c600f811160021b90811c918211600190811b92831c97908811961790941790921717909117171760808110611fe557607f810383901c9150611fef565b80607f0383901b91505b908002607f81811c60ff83811c9190911c800280831c81831c1c800280841c81841c1c800280851c81851c1c800280861c81861c1c800280871c81871c1c800280881c81881c1c800280891c81891c1c8002808a1c818a1c1c8002808b1c818b1c1c8002808c1c818c1c1c8002808d1c818d1c1c8002808e1c9c81901c9c909c1c80029c8d901c9e9d7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff808f0160401b60c09190911c678000000000000000161760c19b909b1c674000000000000000169a909a1760c29990991c672000000000000000169890981760c39790971c671000000000000000169690961760c49590951c670800000000000000169490941760c59390931c670400000000000000169290921760c69190911c670200000000000000161760c79190911c670100000000000000161760c89190911c6680000000000000161760c99190911c6640000000000000161760ca9190911c6620000000000000161760cb9190911c6610000000000000161760cc9190911c6608000000000000161760cd9190911c66040000000000001617691b13d180eb882abba64281027ffffffffffffffffffffffffffffffffffeb84dbf2a407dd93f221832f996e78b8101608090811d906fd9e63e52eeeb7828cf1af18004b842588301901d600281810b9083900b1461221c57886001600160a01b0316612201826132ae565b6001600160a01b03161115612216578161221e565b8061221e565b815b9998505050505050505050565b6000806000866060015187604001516122449190615a70565b608088015188519192509060009081906122ba577f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000006122a385613858565b6122ac90615b70565b6122b587613858565b612317565b7f00000000000000000000000000000000000000000000000000000000000000007f000000000000000000000000000000000000000000000000000000000000000061230586613858565b61230e86613858565b61231790615b70565b9098509650909250905061232c828a856125ec565b6040517f70a082310000000000000000000000000000000000000000000000000000000081523060048201526000906001600160a01b038316906370a082319060240160206040518083038186803b15801561238757600080fd5b505afa15801561239b573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906123bf9190615ba9565b6040517f8870c4f80000000000000000000000000000000000000000000000000000000081529091503390638870c4f890612404908a908a908e908e906004016159da565b600060405180830381600087803b15801561241e57600080fd5b505af1158015612432573d6000803e3d6000fd5b50506040517f70a08231000000000000000000000000000000000000000000000000000000008152306004820152600092506001600160a01b03851691506370a082319060240160206040518083038186803b15801561249157600080fd5b505afa1580156124a5573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906124c99190615ba9565b9050856124d68383615998565b10156125245760405162461bcd60e51b815260206004820152600560248201527f475f54524600000000000000000000000000000000000000000000000000000060448201526064016107af565b50505050505094509492505050565b6040517f70a082310000000000000000000000000000000000000000000000000000000081523060048201526000907f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316906370a08231906024015b60206040518083038186803b1580156125af57600080fd5b505afa1580156125c3573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906125e79190615ba9565b905090565b604080516001600160a01b038416602482015260448082018490528251808303909101815260649091019091526020810180517bffffffffffffffffffffffffffffffffffffffffffffffffffffffff167fa9059cbb0000000000000000000000000000000000000000000000000000000017905261266c908490613b0a565b505050565b6040517f70a082310000000000000000000000000000000000000000000000000000000081523060048201526000907f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316906370a0823190602401612597565b60006001600160801b038211156127585760405162461bcd60e51b815260206004820152602760248201527f53616665436173743a2076616c756520646f65736e27742066697420696e203160448201527f323820626974730000000000000000000000000000000000000000000000000060648201526084016107af565b5090565b6000806001600160801b038416156127df5785546127849085906001600160801b0316613bef565b86546fffffffffffffffffffffffffffffffff1981166001600160801b0391821683900382161788559092506127df907f000000000000000000000000000000000000000000000000000000000000000090879085166125ec565b6001600160801b0383161561286057855461280b908490600160801b90046001600160801b0316613bef565b86546001600160801b03600160801b8083048216849003821602918116919091178855909150612860907f000000000000000000000000000000000000000000000000000000000000000090879084166125ec565b94509492505050565b60008060008060008061287b87613c10565b9350935093509350836128985761289281836159af565b836128a3565b826128a382846159af565b909890975095505050505050565b6001600160801b038316156128ec576128ec847f00000000000000000000000000000000000000000000000000000000000000008584613f37565b6001600160801b0382161561292757612927847f00000000000000000000000000000000000000000000000000000000000000008484613f37565b604080516001600160801b0385811682528416602082015281516001600160a01b0387169233927f38c069c2e9bc192f8cf4f1b85be791ccc0d04bb12c4ca71a3fbfe96ea0932dd5929081900390910190a350505050565b60008060005b8351811015612a25576000806000806129b68886815181106129a9576129a9615bc2565b6020026020010151613c10565b9350935093509350836129e757806129ce83896159af565b6129d891906159af565b6129e284886159af565b612a06565b6129f183886159af565b816129fc84896159af565b612a0691906159af565b8097508198505050505050508080612a1d90615bf1565b915050612985565b50915091565b60606000825167ffffffffffffffff811115612a4957612a4961540a565b604051908082528060200260200182016040528015612a72578160200160208202803683370190505b5091506000612a818451614027565b905060005b8451811015612b0d576000858281518110612aa357612aa3615bc2565b60200260200101519050612ac283898984600001518560200151612d95565b82858381518110612ad557612ad5615bc2565b6020908102919091018101919091528101516001938401939290920191612b05906001600160801b031685615a70565b935050612a86565b5050935093915050565b600080600086612b4a577f0000000000000000000000000000000000000000000000000000000000000000600087612b6f565b7f00000000000000000000000000000000000000000000000000000000000000008660005b6040517f70a0823100000000000000000000000000000000000000000000000000000000815230600482015292955090935091506000906001600160a01b038516906370a082319060240160206040518083038186803b158015612bd257600080fd5b505afa158015612be6573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190612c0a9190615ba9565b6040517f8f61c9f70000000000000000000000000000000000000000000000000000000081529091503390638f61c9f790612c4f90869086908b908b906004016159da565b600060405180830381600087803b158015612c6957600080fd5b505af1158015612c7d573d6000803e3d6000fd5b50506040517f70a08231000000000000000000000000000000000000000000000000000000008152306004820152600092506001600160a01b03871691506370a082319060240160206040518083038186803b158015612cdc57600080fd5b505afa158015612cf0573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190612d149190615ba9565b905087612d218383615998565b1015612d6f5760405162461bcd60e51b815260206004820152600560248201527f475f54504600000000000000000000000000000000000000000000000000000060448201526064016107af565b505050505050505050565b6000600560008154612d8b90615bf1565b9182905550919050565b6000816001600160801b031611612dee5760405162461bcd60e51b815260206004820152600560248201527f475f4f415a00000000000000000000000000000000000000000000000000000060448201526064016107af565b7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f3d8600283900b12801590612e5157506206c4f3612e4b7f000000000000000000000000000000000000000000000000000000000000000084615a29565b60020b13155b8015612e825750612e82827f000000000000000000000000000000000000000000000000000000000000000061403f565b612ece5760405162461bcd60e51b815260206004820152600560248201527f475f49424c00000000000000000000000000000000000000000000000000000060448201526064016107af565b6000612eda8385614056565b805490915060009068010000000000000000900467ffffffffffffffff168015612f285767ffffffffffffffff811660009081526008602052604090209150612f23828561408c565b6130da565b825467ffffffffffffffff1680612fd957612f43868861410d565b85547fffffffffffffffffffffffffffffffffffffffffffffffff00000000000000001667ffffffffffffffff831617865580547fffffffffffffffffffffffff00000000000000000000000000000000ffffffff166401000000006001600160801b0389169081029190911782556001820180546fffffffffffffffffffffffffffffffff19169091179055935091506130d8565b67ffffffffffffffff811660009081526008602052604090208054600182015491945091925082916001600160801b0364010000000090910481169116818110156130c957613028888a61410d565b87547fffffffffffffffffffffffffffffffff0000000000000000ffffffffffffffff166801000000000000000067ffffffffffffffff84160217885580547fffffffffffffffffffffffff00000000000000000000000000000000ffffffff166401000000006001600160801b038b169081029190911782556001820180546fffffffffffffffffffffffffffffffff19169091179055955093506130d5565b6130d58583838a614178565b50505b505b60405180606001604052808267ffffffffffffffff168152602001886001600160a01b03168152602001856001600160801b0316815250600660008a815260200190815260200160002060008201518160000160006101000a81548167ffffffffffffffff021916908367ffffffffffffffff16021790555060208201518160000160086101000a8154816001600160a01b0302191690836001600160a01b0316021790555060408201518160010160006101000a8154816001600160801b0302191690836001600160801b031602179055509050508067ffffffffffffffff16876001600160a01b0316897fd0caf2c4677b4d382504eb6b0f15d030d6887b69dbcb3fc302a62fea5a9fc7a789898960405161321893929190921515835260029190910b60208301526001600160801b0316604082015260600190565b60405180910390a48254600160801b90046001600160801b0316806132415761324186886141e6565b61324b85826159af565b84546001600160801b03918216600160801b029116179093555050505050505050565b6000620f18826001600160a01b0383161080159061191e575073fff6fbe64b68d618d47c209fe40b0d8ee6e23c916001600160a01b038316111592915050565b60008060008360020b126132c7578262ffffff166132cf565b8260020b6000035b90506000600182166132e557600160801b6132f7565b6ffff97272373d413259a46990580e213a5b70ffffffffffffffffffffffffffffffffff169050600282161561332b576ffff2e50f5f656932ef12357cf3c7fdcc0260801c5b600482161561334a576fffe5caca7e10e4e61c3624eaa0941cd00260801c5b6008821615613369576fffcb9843d60f6159c9db58835c9266440260801c5b6010821615613388576fff973b41fa98c081472e6896dfb254c00260801c5b60208216156133a7576fff2ea16466c96a3843ec78b326b528610260801c5b60408216156133c6576ffe5dee046a99a2a811c461f1969c30530260801c5b60808216156133e5576ffcbe86c7900a88aedcffc83b479aa3a40260801c5b610100821615613405576ff987a7253ac413176f2b074cf7815e540260801c5b610200821615613425576ff3392b0822b70005940c7a398e4b70f30260801c5b610400821615613445576fe7159475a2c29b7443b29c7fa6e889d90260801c5b610800821615613465576fd097f3bdfd2022b8845ad8f792aa58250260801c5b611000821615613485576fa9f746462d870fdf8a65dc1f90e061e50260801c5b6120008216156134a5576f70d869a156d2a1b890bb3df62baf32f70260801c5b6140008216156134c5576f31be135f97d08fd981231505542fcfa60260801c5b6180008216156134e5576f09aa508b5b7a84e1c677de54f3e99bc90260801c5b62010000821615613505576e5d6af8dedb81196699c329225ee6040260801c5b62020000821615613524576d2216e584f5fa1ea926041bedfe980260801c5b62040000821615613541576b048a170391f7dc42444e8fa20260801c5b620800008216156135595766149b34ee7ac2630260801c5b60008460020b131561357a578060001981613576576135766159fa565b0490505b63ffffffff0160201c9392505050565b60007ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f3d8600283900b1280159061191e5750506206c4f360029190910b131590565b600080806135d98587615c0c565b905083156136aa576000806135fd6135f2600185615c46565b600281900b60081d91565b9092509050600061360f8260ff615c8e565b600184900b600090815260208c9052604090205460001960ff929092169190911c908116801515965090915085613669578860ff8416613650600188615c46565b61365a9190615c46565b6136649190615cb1565b61369f565b886136738261421f565b61367d9085615c8e565b60ff1661368b600188615c46565b6136959190615c46565b61369f9190615cb1565b96505050505061378b565b60008660020b1280156136c857506136c28587615d3e565b60020b15155b156136d9576136d681615d60565b90505b6000806136ea6135f2846001615a29565b600182900b600090815260208c9052604090205460001960ff83161b9081168015159750929450909250908561374d57886137268460ff615c8e565b60ff16613734876001615a29565b61373e9190615a29565b6137489190615cb1565b613784565b8883613758836142c0565b6137629190615c8e565b60ff16613770876001615a29565b61377a9190615a29565b6137849190615cb1565b9650505050505b5094509492505050565b6000816001600160a01b0316836001600160a01b0316116137b657816137b8565b825b9392505050565b6000816001600160a01b0316836001600160a01b0316106137b657816137b8565b6040805160808101825260008082526020820181905291810182905260608101829052908413156138205761381987878787878761447c565b905061384e565b600084900361384a8888886001600160801b03881685116138415784613843565b875b888861451f565b9150505b9695505050505050565b60007f7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8211156127585760405162461bcd60e51b815260206004820152602860248201527f53616665436173743a2076616c756520646f65736e27742066697420696e206160448201527f6e20696e7432353600000000000000000000000000000000000000000000000060648201526084016107af565b6040805160c081018252600080825260208201819052918101829052606081018290526080810182905260a081019190915260018501546001600160801b039081169084168110156139425780613944565b835b6001600160801b03908116604084018190529085161415613976578482526001600160801b03831660808301526139f7565b836001600160801b03168583604001516001600160801b03166139999190615d84565b6139a39190615da3565b8083528503602083015260408201516001600160801b038186038116606085015280861691811690851602816139db576139db6159fa565b046001600160801b039081166080840181905284031660a08301525b60408201516001870180546fffffffffffffffffffffffffffffffff19169183036001600160801b03169190911790558151613a32906126d9565b6001870154613a519190600160801b90046001600160801b03166159af565b6001870180546001600160801b03928316600160801b0290831617905560808301516002880154613a8292166159af565b60029690960180546fffffffffffffffffffffffffffffffff19166001600160801b0390971696909617909555949350505050565b613ac18183615d3e565b60020b15613ace57600080fd5b600080613ade6135f28486615c0c565b600191820b60009081526020979097526040909620805460ff9097169190911b90951890945550505050565b6000613b5f826040518060400160405280602081526020017f5361666545524332303a206c6f772d6c6576656c2063616c6c206661696c6564815250856001600160a01b03166145859092919063ffffffff16565b80519091501561266c5780806020019051810190613b7d9190615db7565b61266c5760405162461bcd60e51b815260206004820152602a60248201527f5361666545524332303a204552433230206f7065726174696f6e20646964206e60448201527f6f7420737563636565640000000000000000000000000000000000000000000060648201526084016107af565b6000816001600160801b0316836001600160801b0316106137b657816137b8565b60008181526006602090815260408083208151606081018352815467ffffffffffffffff811682526801000000000000000090046001600160a01b03169381018490526001909101546001600160801b0316918101919091528291829182913314613cbd5760405162461bcd60e51b815260206004820152600560248201527f475f434f4f00000000000000000000000000000000000000000000000000000060448201526064016107af565b600086815260066020908152604080832080547fffffffff0000000000000000000000000000000000000000000000000000000016815560010180546fffffffffffffffffffffffffffffffff19169055835167ffffffffffffffff1683526008909152808220805491840151630100000090920460ff1697509190613d44908390614594565b86516040880151949a50929850909650925067ffffffffffffffff16907f7f4039a9e4ce7a4058dd4ca2b91b6b29590b989d4cea256fb3080141cdf3b7e490613d95906001600160801b0316615b70565b613da76001600160801b038a16615b70565b6040805192835260208301919091520160405180910390a28154600090613dd19060020b89614056565b8054855191925067ffffffffffffffff9081169116811480613e0e57508451825468010000000000000000900467ffffffffffffffff9081169116145b15613edd578154600090613e33908a90600160801b90046001600160801b0316615dd4565b83546001600160801b03908116600160801b838316021785559091508416613edb57855167ffffffffffffffff8381169116148015613e885750825468010000000000000000900467ffffffffffffffff1615155b15613ebe57825468010000000000000000810467ffffffffffffffff166fffffffffffffffffffffffffffffffff199091161783555b6001600160801b038116613edb578454613edb9060020b8b6141e6565b505b604080516001600160801b038a81168252898116602083015288168183015290518b917fa9d41f4c7e5cdf552e9bfe6d10327a427231e7905304c308dbf7455b6905556f919081900360600190a250505050509193509193565b808015613f7557507f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316836001600160a01b0316145b1561400d576040517f2e1a7d4d0000000000000000000000000000000000000000000000000000000081526001600160801b03831660048201526001600160a01b03841690632e1a7d4d90602401600060405180830381600087803b158015613fdd57600080fd5b505af1158015613ff1573d6000803e3d6000fd5b5050505061400884836001600160801b0316614705565b614021565b6140218385846001600160801b03166125ec565b50505050565b6005546140348282615a70565b600555600101919050565b600061404b8284615d3e565b60020b159392505050565b60008161407657600283810b6000908152602091909152604090206137b8565b505060020b600090815260016020526040902090565b81546140aa90829064010000000090046001600160801b03166159af565b82547fffffffffffffffffffffffff00000000000000000000000000000000ffffffff166401000000006001600160801b0392831602178355600190920180546fffffffffffffffffffffffffffffffff19811690841692909201909216179055565b60008061411861481e565b67ffffffffffffffff8116600090815260086020526040902080549415156301000000027fffffffffffffffffffffffffffffffffffffffffffffffffffffffff0000000090951662ffffff909616959095179390931784555090929050565b61418281846159af565b84547fffffffffffffffffffffffff00000000000000000000000000000000ffffffff166401000000006001600160801b0392831602178555600190940180546fffffffffffffffffffffffffffffffff1916919092019093169290921790915550565b61421b827f000000000000000000000000000000000000000000000000000000000000000061421484611924565b9190613ab7565b5050565b600080821161422d57600080fd5b600160801b821061424057608091821c91015b68010000000000000000821061425857604091821c91015b640100000000821061426c57602091821c91015b62010000821061427e57601091821c91015b610100821061428f57600891821c91015b6010821061429f57600491821c91015b600482106142af57600291821c91015b600282106142bb576001015b919050565b60008082116142ce57600080fd5b5060ff6001600160801b03821615614307577fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff800161430f565b608082901c91505b67ffffffffffffffff821615614346577fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc00161434e565b604082901c91505b63ffffffff821615614381577fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe001614389565b602082901c91505b61ffff8216156143ba577ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0016143c2565b601082901c91505b60ff8216156143f2577ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8016143fa565b600882901c91505b600f82161561442a577ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc01614432565b600482901c91505b6003821615614462577ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0161446a565b600282901c91505b60018216156142bb5760001901919050565b6040805160808101825260008082526020820181905291810182905260608101919091526144ab878787614865565b6144bc5761381987878686866148f4565b6144c887878786614b79565b6001600160801b0316604082018190526144e790889088908686614bef565b90508381606001516001600160801b031682602001516145079190615a70565b116145125780613819565b61381987878686866148f4565b60408051608081018252600080825260208201819052918101829052606081019190915261454e878787614865565b61455f576138198787868686614bef565b600061456d88888887614b79565b905061384a888861457e8489613bef565b8787614bef565b6060611f3a8484600085614c9f565b8154600183015460028401547fffffffffffffffffffffffff00000000000000000000000000000000ffffffff8316640100000000938490046001600160801b039081168681038083169096029290921787556000948594859491939280821692600160801b90920481169181169084908a16840281614616576146166159fa565b0497508783038a60010160006101000a8154816001600160801b0302191690836001600160801b03160217905550836001600160801b0316826001600160801b03168a6001600160801b03160281614670576146706159fa565b0496508682038a60010160106101000a8154816001600160801b0302191690836001600160801b03160217905550836001600160801b0316816001600160801b03168a6001600160801b031602816146ca576146ca6159fa565b0495508581038a60020160006101000a8154816001600160801b0302191690836001600160801b031602179055505050505092959194509250565b804710156147555760405162461bcd60e51b815260206004820152601d60248201527f416464726573733a20696e73756666696369656e742062616c616e636500000060448201526064016107af565b6000826001600160a01b03168260405160006040518083038185875af1925050503d80600081146147a2576040519150601f19603f3d011682016040523d82523d6000602084013e6147a7565b606091505b505090508061266c5760405162461bcd60e51b815260206004820152603a60248201527f416464726573733a20756e61626c6520746f2073656e642076616c75652c207260448201527f6563697069656e74206d6179206861766520726576657274656400000000000060648201526084016107af565b6007805460009190829061483b9067ffffffffffffffff16615dfc565b91906101000a81548167ffffffffffffffff021916908367ffffffffffffffff1602179055905090565b6000826001600160a01b0316846001600160a01b031610156148b957836001600160a01b0316826001600160a01b0316101580156148b45750826001600160a01b0316826001600160a01b0316105b611f3a565b826001600160a01b0316826001600160a01b0316118015611f3a5750836001600160a01b0316826001600160a01b0316111590509392505050565b6040805160808101825260008082526020820181905291810182905260608101919091526001600160a01b03808616908716101560006149498661494062ffffff8716620f4240615998565b620f4240614de7565b905060008261495a5788880361495e565b8789035b9050600083156149d85760006001600160a01b038b1661497f856002615d84565b6149899190615d84565b905060006149ac846001600160a01b0316868b6001600160801b03166001614e97565b90506149c5816c02000000000000000000000000615a70565b6149cf9083615da3565b92505050614ac4565b6000614a066001600160a01b038c167801000000000000000000000000000000000000000000000000615da3565b614a11856002615d84565b614a1b9190615d84565b90506000614a4b6001600160a01b038c167801000000000000000000000000000000000000000000000000615da3565b614a7778010000000000000000000000000000000000000000000000008e6001600160a01b0316614ef4565b614a819190615998565b90506000614a9b82878c6001600160801b03166001614e97565b9050614ab4816c02000000000000000000000000615a70565b614abe9084615da3565b93505050505b866001600160801b0316811115614b17576001600160a01b03891685526001600160801b0387166040860152614aff848b8b8a60008b614f2b565b6001600160801b031660608701526020860152614b6c565b614b20816126d9565b6001600160801b031660408601819052614b409085908c9085908b615001565b6001600160a01b0316855260208501839052614b5d8389036126d9565b6001600160801b031660608601525b5050505095945050505050565b6000806000866001600160a01b0316856001600160a01b03161015614ba357848703868803614baa565b8685038787035b90925090506000614bbb8383615060565b9050614be3610ea8826001600160801b0388166c010000000000000000000000006001614e97565b98975050505050505050565b6040805160808101825260008082526020820181905291810182905260608101919091526001600160a01b03808616908716101560008082614c35578888036001614c3b565b87890360005b9092509050614c56838a846001600160801b038b168a615001565b6001600160a01b0316808552614c729084908b908a858a614f2b565b6001600160801b039081166060870152602086019190915296909616604084015250909695505050505050565b606082471015614d175760405162461bcd60e51b815260206004820152602660248201527f416464726573733a20696e73756666696369656e742062616c616e636520666f60448201527f722063616c6c000000000000000000000000000000000000000000000000000060648201526084016107af565b6001600160a01b0385163b614d6e5760405162461bcd60e51b815260206004820152601d60248201527f416464726573733a2063616c6c20746f206e6f6e2d636f6e747261637400000060448201526064016107af565b600080866001600160a01b03168587604051614d8a9190615e50565b60006040518083038185875af1925050503d8060008114614dc7576040519150601f19603f3d011682016040523d82523d6000602084013e614dcc565b606091505b5091509150614ddc8282866150b4565b979650505050505050565b600080806000198587098587029250828110838203039150508060001415614e2257838281614e1857614e186159fa565b04925050506137b8565b808411614e2e57600080fd5b60008486880960026001871981018816978890046003810283188082028403028082028403028082028403028082028403028082028403029081029092039091026000889003889004909101858311909403939093029303949094049190911702949350505050565b600080614ea5868686614de7565b90506001836002811115614ebb57614ebb615e6c565b148015614ed8575060008480614ed357614ed36159fa565b868809115b15614eeb57614ee8600182615a70565b90505b95945050505050565b60008215614f225781614f08600185615998565b614f129190615da3565b614f1d906001615a70565b6137b8565b50600092915050565b600080806001600160a01b03888116908816016001866002811115614f5257614f52615e6c565b14614f5d5780614f62565b806001015b60011c9150899050614f9f57614f9a6001600160a01b0382166001600160801b0388166c010000000000000000000000006001614e97565b614fcb565b614fcb6001600160801b0387166c010000000000000000000000006001600160a01b0384166001614e97565b9250614ff3610ea862ffffff861685614fe788620f4240615e9b565b62ffffff166001614e97565b915050965096945050505050565b60008061502c856001600160a01b0316856001600160a01b0316856001600160801b03166001614e97565b90508661504c5761504781876001600160a01b0316016150ed565b614ddc565b614ddc81876001600160a01b0316036150ed565b60006001600160a01b0383166150785750600061191e565b6001600160a01b038381166c01000000000000000000000000029083166000198201816150a7576150a76159fa565b0460010191505092915050565b606083156150c35750816137b8565b8251156150d35782518084602001fd5b8160405162461bcd60e51b81526004016107af9190615eb7565b60006001600160a01b038211156127585760405162461bcd60e51b815260206004820152602760248201527f53616665436173743a2076616c756520646f65736e27742066697420696e203160448201527f363020626974730000000000000000000000000000000000000000000000000060648201526084016107af565b6001600160a01b038116811461518157600080fd5b50565b801515811461518157600080fd5b80356142bb81615184565b60008083601f8401126151af57600080fd5b50813567ffffffffffffffff8111156151c757600080fd5b6020830191508360208285010111156151df57600080fd5b9250929050565b60008060008060008060a087890312156151ff57600080fd5b863561520a8161516c565b9550602087013561521a81615184565b94506040870135935060608701356152318161516c565b9250608087013567ffffffffffffffff81111561524d57600080fd5b61525989828a0161519d565b979a9699509497509295939492505050565b8035600281900b81146142bb57600080fd5b60006020828403121561528f57600080fd5b6137b88261526b565b6000806000806000608086880312156152b057600080fd5b85356152bb8161516c565b94506020860135935060408601359250606086013567ffffffffffffffff8111156152e557600080fd5b6152f18882890161519d565b969995985093965092949392505050565b60006020828403121561531457600080fd5b81356137b88161516c565b80356001600160801b03811681146142bb57600080fd5b60008060006060848603121561534b57600080fd5b83356153568161516c565b92506153646020850161531f565b91506153726040850161531f565b90509250925092565b60006020828403121561538d57600080fd5b813567ffffffffffffffff811681146137b857600080fd5b6000602082840312156153b757600080fd5b81358060010b81146137b857600080fd5b6000806000606084860312156153dd57600080fd5b83356153e88161516c565b92506020840135915060408401356153ff81615184565b809150509250925092565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052604160045260246000fd5b6040805190810167ffffffffffffffff8111828210171561545c5761545c61540a565b60405290565b6040516060810167ffffffffffffffff8111828210171561545c5761545c61540a565b6040516080810167ffffffffffffffff8111828210171561545c5761545c61540a565b604051601f82017fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe016810167ffffffffffffffff811182821017156154ef576154ef61540a565b604052919050565b600067ffffffffffffffff8211156155115761551161540a565b5060051b60200190565b60008060006060848603121561553057600080fd5b833561553b8161516c565b925060208481013567ffffffffffffffff81111561555857600080fd5b8501601f8101871361556957600080fd5b803561557c615577826154f7565b6154a8565b81815260059190911b8201830190838101908983111561559b57600080fd5b928401925b828410156155b9578335825292840192908401906155a0565b809650505050505061537260408501615192565b6000602082840312156155df57600080fd5b5035919050565b600082601f8301126155f757600080fd5b81356020615607615577836154f7565b82815260069290921b8401810191818101908684111561562657600080fd5b8286015b8481101561567357604081890312156156435760008081fd5b61564b615439565b6156548261526b565b815261566185830161531f565b8186015283529183019160400161562a565b509695505050505050565b60008060006040848603121561569357600080fd5b833567ffffffffffffffff808211156156ab57600080fd5b90850190606082880312156156bf57600080fd5b6156c7615462565b82356156d28161516c565b815260208301356156e281615184565b60208201526040830135828111156156f957600080fd5b615705898286016155e6565b6040830152509450602086013591508082111561572157600080fd5b5061572e8682870161519d565b9497909650939450505050565b600081518084526020808501945080840160005b8381101561576b5781518752958201959082019060010161574f565b509495945050505050565b6020815260006137b8602083018461573b565b600080600083850360a081121561579f57600080fd5b60808112156157ad57600080fd5b506157b6615485565b84356157c18161516c565b815260208501356157d181615184565b60208201526157e26040860161526b565b60408201526157f36060860161531f565b60608201529250608084013567ffffffffffffffff81111561581457600080fd5b61572e8682870161519d565b60008060006040848603121561583557600080fd5b833567ffffffffffffffff8082111561584d57600080fd5b908501906080828803121561586157600080fd5b615869615485565b82356158748161516c565b815260208301356158848161516c565b602082015260408301358281111561589b57600080fd5b6158a7898286016155e6565b6040830152506060830135828111156158bf57600080fd5b6158cb898286016155e6565b6060830152509450602086013591508082111561572157600080fd5b6040815260006158fa604083018561573b565b8281036020840152614eeb818561573b565b8183528181602085013750600060208284010152600060207fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0601f840116840101905092915050565b602081526000611f3a60208301848661590c565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052601160045260246000fd5b6000828210156159aa576159aa615969565b500390565b60006001600160801b038083168185168083038211156159d1576159d1615969565b01949350505050565b84815283602082015260606040820152600061384e60608301848661590c565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052601260045260246000fd5b60008160020b8360020b6000821282627fffff03821381151615615a4f57615a4f615969565b82627fffff19038212811615615a6757615a67615969565b50019392505050565b60008219821115615a8357615a83615969565b500190565b6000808312837f800000000000000000000000000000000000000000000000000000000000000001831281151615615ac257615ac2615969565b837f7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff018313811615615af657615af6615969565b50500390565b6000808212827f7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff03841381151615615b3657615b36615969565b827f8000000000000000000000000000000000000000000000000000000000000000038412811615615b6a57615b6a615969565b50500190565b60007f8000000000000000000000000000000000000000000000000000000000000000821415615ba257615ba2615969565b5060000390565b600060208284031215615bbb57600080fd5b5051919050565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b6000600019821415615c0557615c05615969565b5060010190565b60008160020b8360020b80615c2357615c236159fa565b6000198114627fffff1983141615615c3d57615c3d615969565b90059392505050565b60008160020b8360020b6000811281627fffff1901831281151615615c6d57615c6d615969565b81627fffff018313811615615c8457615c84615969565b5090039392505050565b600060ff821660ff841680821015615ca857615ca8615969565b90039392505050565b60008160020b8360020b627fffff600082136000841383830485118282161615615cdd57615cdd615969565b627fffff196000851286820586128184161615615cfc57615cfc615969565b60008712925085820587128484161615615d1857615d18615969565b85850587128184161615615d2e57615d2e615969565b5050509290910295945050505050565b60008260020b80615d5157615d516159fa565b808360020b0791505092915050565b60008160020b627fffff19811415615d7a57615d7a615969565b6000190192915050565b6000816000190483118215151615615d9e57615d9e615969565b500290565b600082615db257615db26159fa565b500490565b600060208284031215615dc957600080fd5b81516137b881615184565b60006001600160801b0383811690831681811015615df457615df4615969565b039392505050565b600067ffffffffffffffff80831681811415615e1a57615e1a615969565b6001019392505050565b60005b83811015615e3f578181015183820152602001615e27565b838111156140215750506000910152565b60008251615e62818460208701615e24565b9190910192915050565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052602160045260246000fd5b600062ffffff83811690831681811015615df457615df4615969565b6020815260008251806020840152615ed6816040850160208701615e24565b601f017fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe016919091016040019291505056fea2646970667358221220149d394a07615e309a8e667a845d7982bc69068d58b46398e27bc077234037a064736f6c63430008090033