// SPDX-License-Identifier: BUSL-1.1
pragma solidity =0.8.20;
pragma abicoder v1;

import '@cryptoalgebra/integral-core/contracts/base/common/Timestamp.sol';
import '@cryptoalgebra/integral-core/contracts/libraries/FullMath.sol';
import '@cryptoalgebra/integral-core/contracts/libraries/Constants.sol';
import '@cryptoalgebra/integral-core/contracts/libraries/TickMath.sol';
import '@cryptoalgebra/integral-core/contracts/libraries/LiquidityMath.sol';
import '@cryptoalgebra/integral-core/contracts/libraries/TickManagement.sol';
import '@cryptoalgebra/integral-core/contracts/interfaces/pool/IAlgebraPoolErrors.sol';

import '../base/VirtualTickStructure.sol';

/// @title Algebra Integral 1.2.2 eternal virtual pool
/// @notice used to track active liquidity in farming and distribute rewards
contract EternalVirtualPool is Timestamp, VirtualTickStructure {
  using TickManagement for mapping(int24 => TickManagement.Tick);

  /// @inheritdoc IAlgebraEternalVirtualPool
  address public immutable override farmingAddress;
  /// @inheritdoc IAlgebraEternalVirtualPool
  address public immutable override plugin;

  /// @inheritdoc IAlgebraEternalVirtualPool
  uint128 public override currentLiquidity;
  /// @inheritdoc IAlgebraEternalVirtualPool
  int24 public override globalTick;
  /// @inheritdoc IAlgebraEternalVirtualPool
  uint32 public override prevTimestamp;
  /// @inheritdoc IAlgebraEternalVirtualPool
  bool public override deactivated;

  uint128 internal rewardRate0;
  uint128 internal rewardRate1;

  uint128 internal rewardReserve0;
  uint128 internal rewardReserve1;

  uint256 internal totalRewardGrowth0 = 1;
  uint256 internal totalRewardGrowth1 = 1;

  modifier onlyFromFarming() {
    _checkIsFromFarming();
    _;
  }

  constructor(address _farmingAddress, address _plugin) {
    farmingAddress = _farmingAddress;
    plugin = _plugin;

    prevTimestamp = _blockTimestamp();
    globalPrevInitializedTick = TickMath.MIN_TICK;
    globalNextInitializedTick = TickMath.MAX_TICK;
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function rewardReserves() external view override returns (uint128 reserve0, uint128 reserve1) {
    return (rewardReserve0, rewardReserve1);
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function rewardRates() external view override returns (uint128 rate0, uint128 rate1) {
    return (rewardRate0, rewardRate1);
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function totalRewardGrowth() external view override returns (uint256 rewardGrowth0, uint256 rewardGrowth1) {
    return (totalRewardGrowth0, totalRewardGrowth1);
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function getInnerRewardsGrowth(
    int24 bottomTick,
    int24 topTick
  ) external view override returns (uint256 rewardGrowthInside0, uint256 rewardGrowthInside1) {
    unchecked {
      // check if ticks are initialized
      if (ticks[bottomTick].prevTick == ticks[bottomTick].nextTick || ticks[topTick].prevTick == ticks[topTick].nextTick)
        revert IAlgebraPoolErrors.tickIsNotInitialized();

      uint32 timeDelta = _blockTimestamp() - prevTimestamp;
      int24 _globalTick = globalTick;

      (uint256 _totalRewardGrowth0, uint256 _totalRewardGrowth1) = (totalRewardGrowth0, totalRewardGrowth1);

      if (timeDelta > 0) {
        // update rewards
        uint128 _currentLiquidity = currentLiquidity;
        if (_currentLiquidity > 0) {
          (uint256 reward0, uint256 reward1) = (rewardRate0 * timeDelta, rewardRate1 * timeDelta);
          (uint256 _rewardReserve0, uint256 _rewardReserve1) = (rewardReserve0, rewardReserve1);

          if (reward0 > _rewardReserve0) reward0 = _rewardReserve0;
          if (reward1 > _rewardReserve1) reward1 = _rewardReserve1;

          if (reward0 > 0) _totalRewardGrowth0 += FullMath.mulDiv(reward0, Constants.Q128, _currentLiquidity);
          if (reward1 > 0) _totalRewardGrowth1 += FullMath.mulDiv(reward1, Constants.Q128, _currentLiquidity);
        }
      }

      return ticks.getInnerFeeGrowth(bottomTick, topTick, _globalTick, _totalRewardGrowth0, _totalRewardGrowth1);
    }
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function deactivate() external override onlyFromFarming {
    deactivated = true;
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function addRewards(uint128 token0Amount, uint128 token1Amount) external override onlyFromFarming {
    _applyRewardsDelta(true, token0Amount, token1Amount);
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function decreaseRewards(uint128 token0Amount, uint128 token1Amount) external override onlyFromFarming {
    _applyRewardsDelta(false, token0Amount, token1Amount);
  }

  /// @inheritdoc IAlgebraVirtualPool
  /// @dev If the virtual pool is deactivated, does nothing
  function crossTo(int24 targetTick, bool zeroToOne) external override returns (bool) {
    if (msg.sender != plugin) revert onlyPlugin();

    // All storage reads in this code block use the same slot
    uint128 _currentLiquidity = currentLiquidity;
    int24 _globalTick = globalTick;
    uint32 _prevTimestamp = prevTimestamp;
    bool _deactivated = deactivated;

    int24 previousTick = globalPrevInitializedTick;
    int24 nextTick = globalNextInitializedTick;

    if (_deactivated) return false; // early return if virtual pool is deactivated
    bool virtualZtO = targetTick <= _globalTick; // direction of movement from the point of view of the virtual pool

    // early return if without any crosses
    if (virtualZtO) {
      if (targetTick >= previousTick) return true;
    } else {
      if (targetTick < nextTick) return true;
    }

    if (virtualZtO != zeroToOne) {
      deactivated = true; // deactivate if invalid input params (possibly desynchronization)
      return false;
    }

    _distributeRewards(_prevTimestamp, _currentLiquidity);

    (uint256 rewardGrowth0, uint256 rewardGrowth1) = (totalRewardGrowth0, totalRewardGrowth1);
    // The set of active ticks in the virtual pool must be a subset of the active ticks in the real pool
    // so this loop will cross no more ticks than the real pool
    if (zeroToOne) {
      while (_globalTick != TickMath.MIN_TICK) {
        if (targetTick >= previousTick) break;
        unchecked {
          int128 liquidityDelta;
          _globalTick = previousTick - 1; // safe since tick index range is narrower than the data type
          nextTick = previousTick;
          (liquidityDelta, previousTick, ) = ticks.cross(previousTick, rewardGrowth0, rewardGrowth1);
          _currentLiquidity = LiquidityMath.addDelta(_currentLiquidity, -liquidityDelta);
        }
      }
    } else {
      while (_globalTick != TickMath.MAX_TICK - 1) {
        if (targetTick < nextTick) break;
        int128 liquidityDelta;
        _globalTick = nextTick;
        previousTick = nextTick;
        (liquidityDelta, , nextTick) = ticks.cross(nextTick, rewardGrowth0, rewardGrowth1);
        _currentLiquidity = LiquidityMath.addDelta(_currentLiquidity, liquidityDelta);
      }
    }

    currentLiquidity = _currentLiquidity;
    globalTick = targetTick;

    globalPrevInitializedTick = previousTick;
    globalNextInitializedTick = nextTick;
    return true;
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function distributeRewards() external override onlyFromFarming {
    _distributeRewards();
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function applyLiquidityDeltaToPosition(
    int24 bottomTick,
    int24 topTick,
    int128 liquidityDelta,
    int24 currentTick
  ) external override onlyFromFarming {
    uint128 _currentLiquidity = currentLiquidity;
    uint32 _prevTimestamp = prevTimestamp;
    bool _deactivated = deactivated;
    {
      int24 _nextActiveTick = globalNextInitializedTick;
      int24 _prevActiveTick = globalPrevInitializedTick;

      if (!_deactivated) {
        // checking if the current tick is within the allowed range: it should not be on the other side of the nearest active tick
        // if the check is violated, the virtual pool deactivates
        if (!_isTickInsideRange(currentTick, _prevActiveTick, _nextActiveTick)) {
          deactivated = _deactivated = true;
        }
      }
    }

    if (_deactivated) {
      // early return if virtual pool is deactivated
      return;
    }

    globalTick = currentTick;

    if (_blockTimestamp() > _prevTimestamp) {
      _distributeRewards(_prevTimestamp, _currentLiquidity);
    }

    if (liquidityDelta != 0) {
      // if we need to update the ticks, do it

      bool flippedBottom = _updateTick(bottomTick, currentTick, liquidityDelta, false);
      bool flippedTop = _updateTick(topTick, currentTick, liquidityDelta, true);

      if (_isTickInsideRange(currentTick, bottomTick, topTick)) {
        currentLiquidity = LiquidityMath.addDelta(_currentLiquidity, liquidityDelta);
      }

      if (flippedBottom || flippedTop) {
        _addOrRemoveTicks(bottomTick, topTick, flippedBottom, flippedTop, currentTick, liquidityDelta < 0);
      }
    }
  }

  /// @inheritdoc IAlgebraEternalVirtualPool
  function setRates(uint128 rate0, uint128 rate1) external override onlyFromFarming {
    _distributeRewards();
    (rewardRate0, rewardRate1) = (rate0, rate1);
  }

  function _checkIsFromFarming() internal view {
    if (msg.sender != farmingAddress) revert onlyFarming();
  }

  function _isTickInsideRange(int24 tick, int24 bottomTick, int24 topTick) internal pure returns (bool) {
    return tick >= bottomTick && tick < topTick;
  }

  function _applyRewardsDelta(bool add, uint128 token0Delta, uint128 token1Delta) private {
    _distributeRewards();
    if (token0Delta | token1Delta != 0) {
      (uint128 _rewardReserve0, uint128 _rewardReserve1) = (rewardReserve0, rewardReserve1);
      if (add) {
        _rewardReserve0 = _rewardReserve0 + token0Delta;
        _rewardReserve1 = _rewardReserve1 + token1Delta;
      } else {
        _rewardReserve0 = _rewardReserve0 - token0Delta;
        _rewardReserve1 = _rewardReserve1 - token1Delta;
      }
      (rewardReserve0, rewardReserve1) = (_rewardReserve0, _rewardReserve1);
    }
  }

  function _distributeRewards() internal {
    _distributeRewards(prevTimestamp, currentLiquidity);
  }

  function _distributeRewards(uint32 _prevTimestamp, uint256 _currentLiquidity) internal {
    // currentLiquidity is uint128
    unchecked {
      uint256 timeDelta = _blockTimestamp() - _prevTimestamp; // safe until timedelta > 136 years
      if (timeDelta == 0) return; // only once per block

      if (_currentLiquidity > 0) {
        (uint256 reward0, uint256 reward1) = (rewardRate0 * timeDelta, rewardRate1 * timeDelta);
        (uint128 _rewardReserve0, uint128 _rewardReserve1) = (rewardReserve0, rewardReserve1);

        if (reward0 > _rewardReserve0) reward0 = _rewardReserve0;
        if (reward1 > _rewardReserve1) reward1 = _rewardReserve1;

        if (reward0 | reward1 != 0) {
          _rewardReserve0 = uint128(_rewardReserve0 - reward0);
          _rewardReserve1 = uint128(_rewardReserve1 - reward1);

          if (reward0 > 0) totalRewardGrowth0 += FullMath.mulDiv(reward0, Constants.Q128, _currentLiquidity);
          if (reward1 > 0) totalRewardGrowth1 += FullMath.mulDiv(reward1, Constants.Q128, _currentLiquidity);

          (rewardReserve0, rewardReserve1) = (_rewardReserve0, _rewardReserve1);
        }
      }
    }

    prevTimestamp = _blockTimestamp();
    return;
  }

  function _updateTick(int24 tick, int24 currentTick, int128 liquidityDelta, bool isTopTick) internal returns (bool updated) {
    return ticks.update(tick, currentTick, liquidityDelta, totalRewardGrowth0, totalRewardGrowth1, isTopTick);
  }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.5.0;

/// @title The interface for the virtual pool
/// @dev Used to calculate active liquidity in farmings
interface IAlgebraVirtualPool {
  /// @dev This function is called by the main pool if an initialized ticks are crossed by swap.
  /// If any one of crossed ticks is also initialized in a virtual pool it should be crossed too
  /// @param targetTick The target tick up to which we need to cross all active ticks
  /// @param zeroToOne Swap direction
  function crossTo(int24 targetTick, bool zeroToOne) external returns (bool success);
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.8.0 <0.9.0;

/// @title Abstract contract with modified blockTimestamp functionality
/// @notice Allows the pool and other contracts to get a timestamp truncated to 32 bits
/// @dev Can be overridden in tests to make testing easier
abstract contract Timestamp {
  /// @dev This function is created for testing by overriding it.
  /// @return A timestamp converted to uint32
  function _blockTimestamp() internal view virtual returns (uint32) {
    return uint32(block.timestamp); // truncation is desired
  }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.8.4;

/// @title Errors emitted by a pool
/// @notice Contains custom errors emitted by the pool
/// @dev Custom errors are separated from the common pool interface for compatibility with older versions of Solidity
interface IAlgebraPoolErrors {
  // ####  pool errors  ####

  /// @notice Emitted by the reentrancy guard
  error locked();

  /// @notice Emitted if arithmetic error occurred
  error arithmeticError();

  /// @notice Emitted if an attempt is made to initialize the pool twice
  error alreadyInitialized();

  /// @notice Emitted if an attempt is made to mint or swap in uninitialized pool
  error notInitialized();

  /// @notice Emitted if 0 is passed as amountRequired to swap function
  error zeroAmountRequired();

  /// @notice Emitted if invalid amount is passed as amountRequired to swap function
  error invalidAmountRequired();

  /// @notice Emitted if plugin fee param greater than fee/override fee
  error incorrectPluginFee();

  /// @notice Emitted if the pool received fewer tokens than it should have
  error insufficientInputAmount();

  /// @notice Emitted if there was an attempt to mint zero liquidity
  error zeroLiquidityDesired();
  /// @notice Emitted if actual amount of liquidity is zero (due to insufficient amount of tokens received)
  error zeroLiquidityActual();

  /// @notice Emitted if the pool received fewer tokens0 after flash than it should have
  error flashInsufficientPaid0();
  /// @notice Emitted if the pool received fewer tokens1 after flash than it should have
  error flashInsufficientPaid1();

  /// @notice Emitted if limitSqrtPrice param is incorrect
  error invalidLimitSqrtPrice();

  /// @notice Tick must be divisible by tickspacing
  error tickIsNotSpaced();

  /// @notice Emitted if a method is called that is accessible only to the factory owner or dedicated role
  error notAllowed();

  /// @notice Emitted if new tick spacing exceeds max allowed value
  error invalidNewTickSpacing();
  /// @notice Emitted if new community fee exceeds max allowed value
  error invalidNewCommunityFee();

  /// @notice Emitted if an attempt is made to manually change the fee value, but dynamic fee is enabled
  error dynamicFeeActive();
  /// @notice Emitted if an attempt is made by plugin to change the fee value, but dynamic fee is disabled
  error dynamicFeeDisabled();
  /// @notice Emitted if an attempt is made to change the plugin configuration, but the plugin is not connected
  error pluginIsNotConnected();
  /// @notice Emitted if a plugin returns invalid selector after hook call
  /// @param expectedSelector The expected selector
  error invalidHookResponse(bytes4 expectedSelector);

  // ####  LiquidityMath errors  ####

  /// @notice Emitted if liquidity underflows
  error liquiditySub();
  /// @notice Emitted if liquidity overflows
  error liquidityAdd();

  // ####  TickManagement errors  ####

  /// @notice Emitted if the topTick param not greater then the bottomTick param
  error topTickLowerOrEqBottomTick();
  /// @notice Emitted if the bottomTick param is lower than min allowed value
  error bottomTickLowerThanMIN();
  /// @notice Emitted if the topTick param is greater than max allowed value
  error topTickAboveMAX();
  /// @notice Emitted if the liquidity value associated with the tick exceeds MAX_LIQUIDITY_PER_TICK
  error liquidityOverflow();
  /// @notice Emitted if an attempt is made to interact with an uninitialized tick
  error tickIsNotInitialized();
  /// @notice Emitted if there is an attempt to insert a new tick into the list of ticks with incorrect indexes of the previous and next ticks
  error tickInvalidLinks();

  // ####  SafeTransfer errors  ####

  /// @notice Emitted if token transfer failed internally
  error transferFailed();

  // ####  TickMath errors  ####

  /// @notice Emitted if tick is greater than the maximum or less than the minimum allowed value
  error tickOutOfRange();
  /// @notice Emitted if price is greater than the maximum or less than the minimum allowed value
  error priceOutOfRange();
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.5.0 <0.9.0;

/// @title Contains common constants for Algebra contracts
/// @dev Constants moved to the library, not the base contract, to further emphasize their constant nature
library Constants {
  uint8 internal constant RESOLUTION = 96;
  uint256 internal constant Q96 = 1 << 96;
  uint256 internal constant Q128 = 1 << 128;

  uint24 internal constant FEE_DENOMINATOR = 1e6;
  uint16 internal constant FLASH_FEE = 0.01e4; // fee for flash loan in hundredths of a bip (0.01%)
  uint16 internal constant INIT_DEFAULT_FEE = 0.05e4; // init default fee value in hundredths of a bip (0.05%)
  uint16 internal constant MAX_DEFAULT_FEE = 5e4; // max default fee value in hundredths of a bip (5%)

  int24 internal constant INIT_DEFAULT_TICK_SPACING = 60;
  int24 internal constant MAX_TICK_SPACING = 500;
  int24 internal constant MIN_TICK_SPACING = 1;

  // the frequency with which the accumulated community fees are sent to the vault
  uint32 internal constant FEE_TRANSFER_FREQUENCY = 8 hours;

  // max(uint128) / (MAX_TICK - MIN_TICK)
  uint128 internal constant MAX_LIQUIDITY_PER_TICK = 191757638537527648490752896198553;

  uint16 internal constant MAX_COMMUNITY_FEE = 1e3; // 100%
  uint256 internal constant COMMUNITY_FEE_DENOMINATOR = 1e3;
  // role that can change settings in pools
  bytes32 internal constant POOLS_ADMINISTRATOR_ROLE = keccak256('POOLS_ADMINISTRATOR');
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @title Contains 512-bit math functions
/// @notice Facilitates multiplication and division that can have overflow of an intermediate value without any loss of precision
/// @dev Handles "phantom overflow" i.e., allows multiplication and division where an intermediate value overflows 256 bits
library FullMath {
  /// @notice Calculates floor(a×b÷denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
  /// @param a The multiplicand
  /// @param b The multiplier
  /// @param denominator The divisor
  /// @return result The 256-bit result
  /// @dev Credit to Remco Bloemen under MIT license https://xn--2-umb.com/21/muldiv
  function mulDiv(uint256 a, uint256 b, uint256 denominator) internal pure returns (uint256 result) {
    unchecked {
      // 512-bit multiply [prod1 prod0] = a * b
      // Compute the product mod 2**256 and mod 2**256 - 1
      // then 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 = a * b; // Least significant 256 bits of the product
      uint256 prod1; // Most significant 256 bits of the product
      assembly {
        let mm := mulmod(a, b, not(0))
        prod1 := sub(sub(mm, prod0), lt(mm, prod0))
      }

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

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

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

      // Make division exact by subtracting the remainder from [prod1 prod0]
      // Compute remainder using mulmod
      // Subtract 256 bit remainder from 512 bit number
      assembly {
        let remainder := mulmod(a, b, denominator)
        prod1 := sub(prod1, gt(remainder, prod0))
        prod0 := sub(prod0, remainder)
      }

      // Factor powers of two out of denominator
      // Compute largest power of two divisor of denominator.
      // Always >= 1.
      uint256 twos = (0 - denominator) & denominator;
      // Divide denominator by power of two
      assembly {
        denominator := div(denominator, twos)
      }

      // Divide [prod1 prod0] by the factors of two
      assembly {
        prod0 := div(prod0, twos)
      }
      // Shift in bits from prod1 into prod0. For this we need
      // to flip `twos` such that it is 2**256 / twos.
      // If twos is zero, then it becomes one
      assembly {
        twos := add(div(sub(0, twos), twos), 1)
      }
      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
      // correct for four bits. That is, denominator * inv = 1 mod 2**4
      uint256 inv = (3 * denominator) ^ 2;
      // Now use 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.
      inv *= 2 - denominator * inv; // inverse mod 2**8
      inv *= 2 - denominator * inv; // inverse mod 2**16
      inv *= 2 - denominator * inv; // inverse mod 2**32
      inv *= 2 - denominator * inv; // inverse mod 2**64
      inv *= 2 - denominator * inv; // inverse mod 2**128
      inv *= 2 - denominator * inv; // 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 * inv;
      return result;
    }
  }

  /// @notice Calculates ceil(a×b÷denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
  /// @param a The multiplicand
  /// @param b The multiplier
  /// @param denominator The divisor
  /// @return result The 256-bit result
  function mulDivRoundingUp(uint256 a, uint256 b, uint256 denominator) internal pure returns (uint256 result) {
    unchecked {
      if (a == 0 || ((result = a * b) / a == b)) {
        require(denominator > 0);
        assembly {
          result := add(div(result, denominator), gt(mod(result, denominator), 0))
        }
      } else {
        result = mulDiv(a, b, denominator);
        if (mulmod(a, b, denominator) > 0) {
          require(result < type(uint256).max);
          result++;
        }
      }
    }
  }

  /// @notice Returns ceil(x / y)
  /// @dev division by 0 has unspecified behavior, and must be checked externally
  /// @param x The dividend
  /// @param y The divisor
  /// @return z The quotient, ceil(x / y)
  function unsafeDivRoundingUp(uint256 x, uint256 y) internal pure returns (uint256 z) {
    assembly {
      z := add(div(x, y), gt(mod(x, y), 0))
    }
  }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.8.4 <0.9.0;

import '../interfaces/pool/IAlgebraPoolErrors.sol';
import './TickMath.sol';
import './TokenDeltaMath.sol';

/// @title Math library for liquidity
/// @dev Credit to Uniswap Labs under GPL-2.0-or-later license:
/// https://github.com/Uniswap/v3-core/blob/main/contracts/libraries
library LiquidityMath {
  /// @notice Add a signed liquidity delta to liquidity and revert if it overflows or underflows
  /// @param x The liquidity before change
  /// @param y The delta by which liquidity should be changed
  /// @return z The liquidity delta
  function addDelta(uint128 x, int128 y) internal pure returns (uint128 z) {
    unchecked {
      if (y < 0) {
        if ((z = x - uint128(-y)) >= x) revert IAlgebraPoolErrors.liquiditySub();
      } else {
        if ((z = x + uint128(y)) < x) revert IAlgebraPoolErrors.liquidityAdd();
      }
    }
  }

  function getAmountsForLiquidity(
    int24 bottomTick,
    int24 topTick,
    int128 liquidityDelta,
    int24 currentTick,
    uint160 currentPrice
  ) internal pure returns (uint256 amount0, uint256 amount1, int128 globalLiquidityDelta) {
    uint160 priceAtBottomTick = TickMath.getSqrtRatioAtTick(bottomTick);
    uint160 priceAtTopTick = TickMath.getSqrtRatioAtTick(topTick);

    int256 amount0Int;
    int256 amount1Int;
    if (currentTick < bottomTick) {
      // If current tick is less than the provided bottom one then only the token0 has to be provided
      amount0Int = TokenDeltaMath.getToken0Delta(priceAtBottomTick, priceAtTopTick, liquidityDelta);
    } else if (currentTick < topTick) {
      amount0Int = TokenDeltaMath.getToken0Delta(currentPrice, priceAtTopTick, liquidityDelta);
      amount1Int = TokenDeltaMath.getToken1Delta(priceAtBottomTick, currentPrice, liquidityDelta);
      globalLiquidityDelta = liquidityDelta;
    } else {
      // If current tick is greater than the provided top one then only the token1 has to be provided
      amount1Int = TokenDeltaMath.getToken1Delta(priceAtBottomTick, priceAtTopTick, liquidityDelta);
    }

    unchecked {
      (amount0, amount1) = liquidityDelta < 0 ? (uint256(-amount0Int), uint256(-amount1Int)) : (uint256(amount0Int), uint256(amount1Int));
    }
  }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.5.0 <0.9.0;

/// @title Safe casting methods
/// @notice Contains methods for safely casting between types
/// @dev Credit to Uniswap Labs under GPL-2.0-or-later license:
/// https://github.com/Uniswap/v3-core/blob/main/contracts/libraries
library SafeCast {
  /// @notice Cast a uint256 to a uint160, revert on overflow
  /// @param y The uint256 to be downcasted
  /// @return z The downcasted integer, now type uint160
  function toUint160(uint256 y) internal pure returns (uint160 z) {
    require((z = uint160(y)) == y);
  }

  /// @notice Cast a uint256 to a uint128, revert on overflow
  /// @param y The uint256 to be downcasted
  /// @return z The downcasted integer, now type uint128
  function toUint128(uint256 y) internal pure returns (uint128 z) {
    require((z = uint128(y)) == y);
  }

  /// @notice Cast a int256 to a int128, revert on overflow or underflow
  /// @param y The int256 to be downcasted
  /// @return z The downcasted integer, now type int128
  function toInt128(int256 y) internal pure returns (int128 z) {
    require((z = int128(y)) == y);
  }

  /// @notice Cast a uint128 to a int128, revert on overflow
  /// @param y The uint128 to be downcasted
  /// @return z The downcasted integer, now type int128
  function toInt128(uint128 y) internal pure returns (int128 z) {
    require((z = int128(y)) >= 0);
  }

  /// @notice Cast a uint256 to a int256, revert on overflow
  /// @param y The uint256 to be casted
  /// @return z The casted integer, now type int256
  function toInt256(uint256 y) internal pure returns (int256 z) {
    require((z = int256(y)) >= 0);
  }
}

// SPDX-License-Identifier: BUSL-1.1
pragma solidity =0.8.20;

import '../interfaces/pool/IAlgebraPoolErrors.sol';

import './TickMath.sol';
import './LiquidityMath.sol';
import './Constants.sol';

/// @title Library for managing and interacting with ticks
/// @notice Contains functions for managing tick processes and relevant calculations
/// @dev Ticks are organized as a doubly linked list
library TickManagement {
  // info stored for each initialized individual tick
  struct Tick {
    uint256 liquidityTotal; // the total position liquidity that references this tick
    int128 liquidityDelta; // amount of net liquidity added (subtracted) when tick is crossed left-right (right-left),
    int24 prevTick;
    int24 nextTick;
    // fee growth per unit of liquidity on the _other_ side of this tick (relative to the current tick)
    // only has relative meaning, not absolute — the value depends on when the tick is initialized
    uint256 outerFeeGrowth0Token;
    uint256 outerFeeGrowth1Token;
  }

  function checkTickRangeValidity(int24 bottomTick, int24 topTick) internal pure {
    if (topTick > TickMath.MAX_TICK) revert IAlgebraPoolErrors.topTickAboveMAX();
    if (topTick <= bottomTick) revert IAlgebraPoolErrors.topTickLowerOrEqBottomTick();
    if (bottomTick < TickMath.MIN_TICK) revert IAlgebraPoolErrors.bottomTickLowerThanMIN();
  }

  /// @notice Retrieves fee growth data
  /// @param self The mapping containing all tick information for initialized ticks
  /// @param bottomTick The lower tick boundary of the position
  /// @param topTick The upper tick boundary of the position
  /// @param currentTick The current tick
  /// @param totalFeeGrowth0Token The all-time global fee growth, per unit of liquidity, in token0
  /// @param totalFeeGrowth1Token The all-time global fee growth, per unit of liquidity, in token1
  /// @return innerFeeGrowth0Token The all-time fee growth in token0, per unit of liquidity, inside the position's tick boundaries
  /// @return innerFeeGrowth1Token The all-time fee growth in token1, per unit of liquidity, inside the position's tick boundaries
  function getInnerFeeGrowth(
    mapping(int24 => Tick) storage self,
    int24 bottomTick,
    int24 topTick,
    int24 currentTick,
    uint256 totalFeeGrowth0Token,
    uint256 totalFeeGrowth1Token
  ) internal view returns (uint256 innerFeeGrowth0Token, uint256 innerFeeGrowth1Token) {
    Tick storage lower = self[bottomTick];
    Tick storage upper = self[topTick];

    unchecked {
      if (currentTick < topTick) {
        if (currentTick >= bottomTick) {
          innerFeeGrowth0Token = totalFeeGrowth0Token - lower.outerFeeGrowth0Token;
          innerFeeGrowth1Token = totalFeeGrowth1Token - lower.outerFeeGrowth1Token;
        } else {
          innerFeeGrowth0Token = lower.outerFeeGrowth0Token;
          innerFeeGrowth1Token = lower.outerFeeGrowth1Token;
        }
        innerFeeGrowth0Token -= upper.outerFeeGrowth0Token;
        innerFeeGrowth1Token -= upper.outerFeeGrowth1Token;
      } else {
        innerFeeGrowth0Token = upper.outerFeeGrowth0Token - lower.outerFeeGrowth0Token;
        innerFeeGrowth1Token = upper.outerFeeGrowth1Token - lower.outerFeeGrowth1Token;
      }
    }
  }

  /// @notice Updates a tick and returns true if the tick was flipped from initialized to uninitialized, or vice versa
  /// @param self The mapping containing all tick information for initialized ticks
  /// @param tick The tick that will be updated
  /// @param currentTick The current tick
  /// @param liquidityDelta A new amount of liquidity to be added (subtracted) when tick is crossed from left to right (right to left)
  /// @param totalFeeGrowth0Token The all-time global fee growth, per unit of liquidity, in token0
  /// @param totalFeeGrowth1Token The all-time global fee growth, per unit of liquidity, in token1
  /// @param upper True for updating a position's upper tick, or false for updating a position's lower tick
  /// @return flipped Whether the tick was flipped from initialized to uninitialized, or vice versa
  function update(
    mapping(int24 => Tick) storage self,
    int24 tick,
    int24 currentTick,
    int128 liquidityDelta,
    uint256 totalFeeGrowth0Token,
    uint256 totalFeeGrowth1Token,
    bool upper
  ) internal returns (bool flipped) {
    Tick storage data = self[tick];

    uint256 liquidityTotalBefore = data.liquidityTotal;
    uint256 liquidityTotalAfter = LiquidityMath.addDelta(uint128(liquidityTotalBefore), liquidityDelta);
    if (liquidityTotalAfter > Constants.MAX_LIQUIDITY_PER_TICK) revert IAlgebraPoolErrors.liquidityOverflow();

    int128 liquidityDeltaBefore = data.liquidityDelta;
    // when the lower (upper) tick is crossed left to right (right to left), liquidity must be added (removed)
    data.liquidityDelta = upper ? int128(int256(liquidityDeltaBefore) - liquidityDelta) : int128(int256(liquidityDeltaBefore) + liquidityDelta);
    data.liquidityTotal = liquidityTotalAfter;

    flipped = (liquidityTotalAfter == 0);
    if (liquidityTotalBefore == 0) {
      flipped = !flipped;
      // by convention, we assume that all growth before a tick was initialized happened _below_ the tick
      if (tick <= currentTick) (data.outerFeeGrowth0Token, data.outerFeeGrowth1Token) = (totalFeeGrowth0Token, totalFeeGrowth1Token);
    }
  }

  /// @notice Transitions to next tick as needed by price movement
  /// @param self The mapping containing all tick information for initialized ticks
  /// @param tick The destination tick of the transition
  /// @param feeGrowth0 The all-time global fee growth, per unit of liquidity, in token0
  /// @param feeGrowth1 The all-time global fee growth, per unit of liquidity, in token1
  /// @return liquidityDelta The amount of liquidity added (subtracted) when tick is crossed from left to right (right to left)
  /// @return prevTick The previous active tick before _tick_
  /// @return nextTick The next active tick after _tick_
  function cross(
    mapping(int24 => Tick) storage self,
    int24 tick,
    uint256 feeGrowth0,
    uint256 feeGrowth1
  ) internal returns (int128 liquidityDelta, int24 prevTick, int24 nextTick) {
    Tick storage data = self[tick];
    unchecked {
      (data.outerFeeGrowth1Token, data.outerFeeGrowth0Token) = (feeGrowth1 - data.outerFeeGrowth1Token, feeGrowth0 - data.outerFeeGrowth0Token);
    }
    return (data.liquidityDelta, data.prevTick, data.nextTick);
  }

  /// @notice Used for initial setup of ticks list
  /// @param self The mapping containing all tick information for initialized ticks
  function initTickState(mapping(int24 => Tick) storage self) internal {
    (self[TickMath.MIN_TICK].prevTick, self[TickMath.MIN_TICK].nextTick) = (TickMath.MIN_TICK, TickMath.MAX_TICK);
    (self[TickMath.MAX_TICK].prevTick, self[TickMath.MAX_TICK].nextTick) = (TickMath.MIN_TICK, TickMath.MAX_TICK);
  }

  /// @notice Removes tick from the linked list
  /// @param self The mapping containing all tick information for initialized ticks
  /// @param tick The tick that will be removed
  /// @return prevTick The previous active tick before _tick_
  /// @return nextTick The next active tick after _tick_
  function removeTick(mapping(int24 => Tick) storage self, int24 tick) internal returns (int24 prevTick, int24 nextTick) {
    (prevTick, nextTick) = (self[tick].prevTick, self[tick].nextTick);
    delete self[tick];

    if (tick == TickMath.MIN_TICK || tick == TickMath.MAX_TICK) {
      // MIN_TICK and MAX_TICK cannot be removed from tick list
      (self[tick].prevTick, self[tick].nextTick) = (prevTick, nextTick);
    } else {
      if (prevTick == nextTick) revert IAlgebraPoolErrors.tickIsNotInitialized();
      self[prevTick].nextTick = nextTick;
      self[nextTick].prevTick = prevTick;
    }
    return (prevTick, nextTick);
  }

  /// @notice Adds tick to the linked list
  /// @param self The mapping containing all tick information for initialized ticks
  /// @param tick The tick that will be inserted
  /// @param prevTick The previous active tick before _tick_
  /// @param nextTick The next active tick after _tick_
  function insertTick(mapping(int24 => Tick) storage self, int24 tick, int24 prevTick, int24 nextTick) internal {
    if (tick == TickMath.MIN_TICK || tick == TickMath.MAX_TICK) return;
    if (!(prevTick < tick && nextTick > tick)) revert IAlgebraPoolErrors.tickInvalidLinks();
    (self[tick].prevTick, self[tick].nextTick) = (prevTick, nextTick);

    self[prevTick].nextTick = tick;
    self[nextTick].prevTick = tick;
  }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.8.4 <0.9.0;

import '../interfaces/pool/IAlgebraPoolErrors.sol';

/// @title Math library for computing sqrt prices from ticks and vice versa
/// @notice Computes sqrt price for ticks of size 1.0001, i.e. sqrt(1.0001^tick) as fixed point Q64.96 numbers. Supports
/// prices between 2**-128 and 2**128
/// @dev Credit to Uniswap Labs under GPL-2.0-or-later license:
/// https://github.com/Uniswap/v3-core/blob/main/contracts/libraries
library TickMath {
  /// @dev The minimum tick that may be passed to #getSqrtRatioAtTick computed from log base 1.0001 of 2**-128
  int24 internal constant MIN_TICK = -887272;
  /// @dev The maximum tick that may be passed to #getSqrtRatioAtTick computed from log base 1.0001 of 2**128
  int24 internal constant MAX_TICK = -MIN_TICK;

  /// @dev The minimum value that can be returned from #getSqrtRatioAtTick. Equivalent to getSqrtRatioAtTick(MIN_TICK)
  uint160 internal constant MIN_SQRT_RATIO = 4295128739;
  /// @dev The maximum value that can be returned from #getSqrtRatioAtTick. Equivalent to getSqrtRatioAtTick(MAX_TICK)
  uint160 internal constant MAX_SQRT_RATIO = 1461446703485210103287273052203988822378723970342;

  /// @notice Calculates sqrt(1.0001^tick) * 2^96
  /// @dev Throws if |tick| > max tick
  /// @param tick The input tick for the above formula
  /// @return price A Fixed point Q64.96 number representing the sqrt of the ratio of the two assets (token1/token0)
  /// at the given tick
  function getSqrtRatioAtTick(int24 tick) internal pure returns (uint160 price) {
    unchecked {
      // get abs value
      int24 absTickMask = tick >> (24 - 1);
      uint256 absTick = uint24((tick + absTickMask) ^ absTickMask);
      if (absTick > uint24(MAX_TICK)) revert IAlgebraPoolErrors.tickOutOfRange();

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

      if (tick > 0) {
        assembly {
          ratio := div(not(0), ratio)
        }
      }

      // this divides by 1<<32 rounding up to go from a Q128.128 to a Q128.96.
      // we then downcast because we know the result always fits within 160 bits due to our tick input constraint
      // we round up in the division so getTickAtSqrtRatio of the output price is always consistent
      price = uint160((ratio + 0xFFFFFFFF) >> 32);
    }
  }

  /// @notice Calculates the greatest tick value such that getRatioAtTick(tick) <= ratio
  /// @dev Throws in case price < MIN_SQRT_RATIO, as MIN_SQRT_RATIO is the lowest value getRatioAtTick may
  /// ever return.
  /// @param price The sqrt ratio for which to compute the tick as a Q64.96
  /// @return tick The greatest tick for which the ratio is less than or equal to the input ratio
  function getTickAtSqrtRatio(uint160 price) internal pure returns (int24 tick) {
    unchecked {
      // second inequality must be >= because the price can never reach the price at the max tick
      if (price < MIN_SQRT_RATIO || price >= MAX_SQRT_RATIO) revert IAlgebraPoolErrors.priceOutOfRange();
      uint256 ratio = uint256(price) << 32;

      uint256 r = ratio;
      uint256 msb;

      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 log_sqrt10001 = log_2 * 255738958999603826347141; // 128.128 number

      int24 tickLow = int24((log_sqrt10001 - 3402992956809132418596140100660247210) >> 128);
      int24 tickHi = int24((log_sqrt10001 + 291339464771989622907027621153398088495) >> 128);

      tick = tickLow == tickHi ? tickLow : getSqrtRatioAtTick(tickHi) <= price ? tickHi : tickLow;
    }
  }
}

// SPDX-License-Identifier: BUSL-1.1
pragma solidity =0.8.20;

import './TickMath.sol';

/// @title Packed tick initialized state library
/// @notice Stores a packed mapping of tick index to its initialized state and search tree
/// @dev The leafs mapping uses int16 for keys since ticks are represented as int24 and there are 256 (2^8) values per word.
library TickTree {
  int16 internal constant SECOND_LAYER_OFFSET = 3466; // ceil(-MIN_TICK / 256)

  /// @notice Toggles the initialized state for a given tick from false to true, or vice versa
  /// @param leafs The mapping of words with ticks
  /// @param secondLayer The mapping of words with leafs
  /// @param treeRoot The word with info about active subtrees
  /// @param tick The tick to toggle
  function toggleTick(
    mapping(int16 => uint256) storage leafs,
    mapping(int16 => uint256) storage secondLayer,
    uint32 treeRoot,
    int24 tick
  ) internal returns (uint32 newTreeRoot) {
    newTreeRoot = treeRoot;
    (bool toggledNode, int16 nodeIndex) = _toggleBitInNode(leafs, tick); // toggle in leaf
    if (toggledNode) {
      unchecked {
        (toggledNode, nodeIndex) = _toggleBitInNode(secondLayer, nodeIndex + SECOND_LAYER_OFFSET);
      }
      if (toggledNode) {
        assembly {
          newTreeRoot := xor(newTreeRoot, shl(nodeIndex, 1))
        }
      }
    }
  }

  /// @notice Toggles a bit in a tree layer by its index
  /// @param treeLevel The level of tree
  /// @param bitIndex The end-to-end index of a bit in a layer of tree
  /// @return toggledNode Toggled whole node or not
  /// @return nodeIndex Number of corresponding node
  function _toggleBitInNode(mapping(int16 => uint256) storage treeLevel, int24 bitIndex) private returns (bool toggledNode, int16 nodeIndex) {
    assembly {
      nodeIndex := sar(8, bitIndex)
    }
    uint256 node = treeLevel[nodeIndex];
    assembly {
      toggledNode := iszero(node)
      node := xor(node, shl(and(bitIndex, 0xFF), 1))
      toggledNode := xor(toggledNode, iszero(node))
    }
    treeLevel[nodeIndex] = node;
  }

  /// @notice Returns the next initialized tick in tree to the right (gte) of the given tick or `MAX_TICK`
  /// @param leafs The words with ticks
  /// @param secondLayer The words with info about active leafs
  /// @param treeRoot The word with info about active subtrees
  /// @param tick The starting tick
  /// @return nextTick The next initialized tick or `MAX_TICK`
  function getNextTick(
    mapping(int16 => uint256) storage leafs,
    mapping(int16 => uint256) storage secondLayer,
    uint32 treeRoot,
    int24 tick
  ) internal view returns (int24 nextTick) {
    unchecked {
      tick++; // start searching from the next tick
      int16 nodeIndex;
      assembly {
        // index in treeRoot
        nodeIndex := shr(8, add(sar(8, tick), SECOND_LAYER_OFFSET))
      }
      bool initialized;
      // if subtree has active ticks
      if (treeRoot & (1 << uint16(nodeIndex)) != 0) {
        // try to find initialized tick in the corresponding leaf of the tree
        (nodeIndex, nextTick, initialized) = _nextActiveBitInSameNode(leafs, tick);
        if (initialized) return nextTick;

        // try to find next initialized leaf in the tree
        (nodeIndex, nextTick, initialized) = _nextActiveBitInSameNode(secondLayer, nodeIndex + SECOND_LAYER_OFFSET + 1);
      }
      if (!initialized) {
        // try to find which subtree has an active leaf
        // nodeIndex is now the index of the second level node
        (nextTick, initialized) = _nextActiveBitInWord(treeRoot, ++nodeIndex);
        if (!initialized) return TickMath.MAX_TICK;
        nextTick = _firstActiveBitInNode(secondLayer, nextTick); // we found a second level node that has a leaf with an active tick
      }
      nextTick = _firstActiveBitInNode(leafs, nextTick - SECOND_LAYER_OFFSET);
    }
  }

  /// @notice Returns the index of the next active bit in the same tree node
  /// @param treeLevel The level of search tree
  /// @param bitIndex The starting bit index
  /// @return nodeIndex The index of corresponding node
  /// @return nextBitIndex The index of next active bit or last bit in node
  /// @return initialized Is nextBitIndex initialized or not
  function _nextActiveBitInSameNode(
    mapping(int16 => uint256) storage treeLevel,
    int24 bitIndex
  ) internal view returns (int16 nodeIndex, int24 nextBitIndex, bool initialized) {
    assembly {
      nodeIndex := sar(8, bitIndex)
    }
    (nextBitIndex, initialized) = _nextActiveBitInWord(treeLevel[nodeIndex], bitIndex);
  }

  /// @notice Returns first active bit in given node
  /// @param treeLevel The level of search tree
  /// @param nodeIndex The index of corresponding node in the level of tree
  /// @return bitIndex Number of next active bit or last bit in node
  function _firstActiveBitInNode(mapping(int16 => uint256) storage treeLevel, int24 nodeIndex) internal view returns (int24 bitIndex) {
    assembly {
      bitIndex := shl(8, nodeIndex)
    }
    (bitIndex, ) = _nextActiveBitInWord(treeLevel[int16(nodeIndex)], bitIndex);
  }

  /// @notice Returns the next initialized bit contained in the word that is to the right or at (gte) of the given bit
  /// @param word The word in which to compute the next initialized bit
  /// @param bitIndex The end-to-end index of a bit in a layer of tree
  /// @return nextBitIndex The next initialized or uninitialized bit up to 256 bits away from the current bit
  /// @return initialized Whether the next bit is initialized, as the function only searches within up to 256 bits
  function _nextActiveBitInWord(uint256 word, int24 bitIndex) internal pure returns (int24 nextBitIndex, bool initialized) {
    uint256 bitIndexInWord;
    assembly {
      bitIndexInWord := and(bitIndex, 0xFF)
    }
    unchecked {
      uint256 _row = word >> bitIndexInWord; // all the 1s at or to the left of the bitIndexInWord
      if (_row == 0) {
        nextBitIndex = bitIndex | 255;
      } else {
        nextBitIndex = bitIndex + int24(uint24(getSingleSignificantBit((0 - _row) & _row))); // least significant bit
        initialized = true;
      }
    }
  }

  /// @notice get position of single 1-bit
  /// @dev it is assumed that word contains exactly one 1-bit, otherwise the result will be incorrect
  /// @param word The word containing only one 1-bit
  function getSingleSignificantBit(uint256 word) internal pure returns (uint8 singleBitPos) {
    assembly {
      singleBitPos := iszero(and(word, 0x5555555555555555555555555555555555555555555555555555555555555555))
      singleBitPos := or(singleBitPos, shl(7, iszero(and(word, 0x00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF))))
      singleBitPos := or(singleBitPos, shl(6, iszero(and(word, 0x0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF))))
      singleBitPos := or(singleBitPos, shl(5, iszero(and(word, 0x00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF))))
      singleBitPos := or(singleBitPos, shl(4, iszero(and(word, 0x0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF))))
      singleBitPos := or(singleBitPos, shl(3, iszero(and(word, 0x00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF))))
      singleBitPos := or(singleBitPos, shl(2, iszero(and(word, 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F))))
      singleBitPos := or(singleBitPos, shl(1, iszero(and(word, 0x3333333333333333333333333333333333333333333333333333333333333333))))
    }
  }
}

// SPDX-License-Identifier: BUSL-1.1
pragma solidity =0.8.20;

import './SafeCast.sol';
import './FullMath.sol';
import './Constants.sol';

/// @title Functions based on Q64.96 sqrt price and liquidity
/// @notice Contains the math that uses square root of price as a Q64.96 and liquidity to compute deltas
library TokenDeltaMath {
  using SafeCast for uint256;

  /// @notice Gets the token0 delta between two prices
  /// @dev Calculates liquidity / sqrt(lower) - liquidity / sqrt(upper)
  /// @param priceLower A Q64.96 sqrt price
  /// @param priceUpper Another Q64.96 sqrt price
  /// @param liquidity The amount of usable liquidity
  /// @param roundUp Whether to round the amount up or down
  /// @return token0Delta Amount of token0 required to cover a position of size liquidity between the two passed prices
  function getToken0Delta(uint160 priceLower, uint160 priceUpper, uint128 liquidity, bool roundUp) internal pure returns (uint256 token0Delta) {
    unchecked {
      uint256 priceDelta = priceUpper - priceLower;
      require(priceDelta < priceUpper); // forbids underflow and 0 priceLower
      uint256 liquidityShifted = uint256(liquidity) << Constants.RESOLUTION;

      token0Delta = roundUp
        ? FullMath.unsafeDivRoundingUp(FullMath.mulDivRoundingUp(priceDelta, liquidityShifted, priceUpper), priceLower) // denominator always > 0
        : FullMath.mulDiv(priceDelta, liquidityShifted, priceUpper) / priceLower;
    }
  }

  /// @notice Gets the token1 delta between two prices
  /// @dev Calculates liquidity * (sqrt(upper) - sqrt(lower))
  /// @param priceLower A Q64.96 sqrt price
  /// @param priceUpper Another Q64.96 sqrt price
  /// @param liquidity The amount of usable liquidity
  /// @param roundUp Whether to round the amount up, or down
  /// @return token1Delta Amount of token1 required to cover a position of size liquidity between the two passed prices
  function getToken1Delta(uint160 priceLower, uint160 priceUpper, uint128 liquidity, bool roundUp) internal pure returns (uint256 token1Delta) {
    unchecked {
      require(priceUpper >= priceLower);
      uint256 priceDelta = priceUpper - priceLower;
      token1Delta = roundUp ? FullMath.mulDivRoundingUp(priceDelta, liquidity, Constants.Q96) : FullMath.mulDiv(priceDelta, liquidity, Constants.Q96);
    }
  }

  /// @notice Helper that gets signed token0 delta
  /// @param priceLower A Q64.96 sqrt price
  /// @param priceUpper Another Q64.96 sqrt price
  /// @param liquidity The change in liquidity for which to compute the token0 delta
  /// @return token0Delta Amount of token0 corresponding to the passed liquidityDelta between the two prices
  function getToken0Delta(uint160 priceLower, uint160 priceUpper, int128 liquidity) internal pure returns (int256 token0Delta) {
    unchecked {
      token0Delta = liquidity >= 0
        ? getToken0Delta(priceLower, priceUpper, uint128(liquidity), true).toInt256()
        : -getToken0Delta(priceLower, priceUpper, uint128(-liquidity), false).toInt256();
    }
  }

  /// @notice Helper that gets signed token1 delta
  /// @param priceLower A Q64.96 sqrt price
  /// @param priceUpper Another Q64.96 sqrt price
  /// @param liquidity The change in liquidity for which to compute the token1 delta
  /// @return token1Delta Amount of token1 corresponding to the passed liquidityDelta between the two prices
  function getToken1Delta(uint160 priceLower, uint160 priceUpper, int128 liquidity) internal pure returns (int256 token1Delta) {
    unchecked {
      token1Delta = liquidity >= 0
        ? getToken1Delta(priceLower, priceUpper, uint128(liquidity), true).toInt256()
        : -getToken1Delta(priceLower, priceUpper, uint128(-liquidity), false).toInt256();
    }
  }
}

// SPDX-License-Identifier: BUSL-1.1
pragma solidity =0.8.20;

import '@cryptoalgebra/integral-core/contracts/libraries/TickTree.sol';
import '@cryptoalgebra/integral-core/contracts/libraries/TickManagement.sol';

import '../interfaces/IAlgebraEternalVirtualPool.sol';

/// @title Algebra virtual tick structure abstract contract
/// @notice Encapsulates the logic of interaction with the data structure with ticks
/// @dev Ticks are stored as a doubly linked list. A two-layer bitmap tree is used to search through the list
abstract contract VirtualTickStructure is IAlgebraEternalVirtualPool {
  using TickManagement for mapping(int24 => TickManagement.Tick);
  using TickTree for mapping(int16 => uint256);

  /// @inheritdoc IAlgebraEternalVirtualPool
  mapping(int24 tickId => TickManagement.Tick tick) public override ticks;

  uint32 internal tickTreeRoot; // The root of bitmap search tree
  mapping(int16 wordIndex => uint256 word) internal tickSecondLayer; // The second layer bitmap search tree
  mapping(int16 wordIndex => uint256 word) internal tickTable; // the leaves of the tree

  int24 internal globalPrevInitializedTick;
  int24 internal globalNextInitializedTick;

  constructor() {
    ticks.initTickState();
  }

  /// @notice Used to add or remove a tick from a doubly linked list and search tree
  /// @param tick The tick being removed or added now
  /// @param currentTick The current global tick in the pool
  /// @param oldTickTreeRoot The current tick tree root
  /// @param prevInitializedTick Previous active tick before `currentTick`
  /// @param nextInitializedTick Next active tick after `currentTick`
  /// @param remove Remove or add the tick
  /// @return New previous active tick before `currentTick` if changed
  /// @return New next active tick after `currentTick` if changed
  /// @return New tick tree root if changed
  function _addOrRemoveTick(
    int24 tick,
    int24 currentTick,
    uint32 oldTickTreeRoot,
    int24 prevInitializedTick,
    int24 nextInitializedTick,
    bool remove
  ) internal returns (int24, int24, uint32) {
    if (remove) {
      (int24 prevTick, int24 nextTick) = ticks.removeTick(tick);
      if (prevInitializedTick == tick) prevInitializedTick = prevTick;
      else if (nextInitializedTick == tick) nextInitializedTick = nextTick;
    } else {
      int24 prevTick;
      int24 nextTick;
      if (prevInitializedTick < tick && nextInitializedTick > tick) {
        (prevTick, nextTick) = (prevInitializedTick, nextInitializedTick); // we know next and prev ticks
        if (tick > currentTick) nextInitializedTick = tick;
        else prevInitializedTick = tick;
      } else {
        nextTick = tickTable.getNextTick(tickSecondLayer, oldTickTreeRoot, tick);
        prevTick = ticks[nextTick].prevTick;
      }
      ticks.insertTick(tick, prevTick, nextTick);
    }

    uint32 newTickTreeRoot = tickTable.toggleTick(tickSecondLayer, oldTickTreeRoot, tick);
    return (prevInitializedTick, nextInitializedTick, newTickTreeRoot);
  }

  /// @notice Used to add or remove a pair of ticks from a doubly linked list and search tree
  /// @param bottomTick The bottom tick being removed or added now
  /// @param topTick The top tick being removed or added now
  /// @param toggleBottom Should bottom tick be changed or not
  /// @param toggleTop Should top tick be changed or not
  /// @param currentTick The current global tick in the pool
  /// @param remove Remove or add the ticks
  function _addOrRemoveTicks(int24 bottomTick, int24 topTick, bool toggleBottom, bool toggleTop, int24 currentTick, bool remove) internal {
    (int24 prevInitializedTick, int24 nextInitializedTick, uint32 oldTickTreeRoot) = (
      globalPrevInitializedTick,
      globalNextInitializedTick,
      tickTreeRoot
    );
    (int24 newPrevTick, int24 newNextTick, uint32 newTreeRoot) = (prevInitializedTick, nextInitializedTick, oldTickTreeRoot);
    if (toggleBottom) {
      (newPrevTick, newNextTick, newTreeRoot) = _addOrRemoveTick(bottomTick, currentTick, newTreeRoot, newPrevTick, newNextTick, remove);
    }
    if (toggleTop) {
      (newPrevTick, newNextTick, newTreeRoot) = _addOrRemoveTick(topTick, currentTick, newTreeRoot, newPrevTick, newNextTick, remove);
    }
    if (prevInitializedTick != newPrevTick || nextInitializedTick != newNextTick || newTreeRoot != oldTickTreeRoot) {
      (globalPrevInitializedTick, globalNextInitializedTick, tickTreeRoot) = (newPrevTick, newNextTick, newTreeRoot);
    }
  }
}

// SPDX-License-Identifier: GPL-2.0-or-later
pragma solidity >=0.8.4;

import '@cryptoalgebra/integral-base-plugin/contracts/interfaces/IAlgebraVirtualPool.sol';

/// @title Algebra eternal virtual pool interface
/// @notice Used to track active liquidity in farming and distribute rewards
interface IAlgebraEternalVirtualPool is IAlgebraVirtualPool {
  error onlyPlugin();
  error onlyFarming();

  /// @notice Returns address of the AlgebraEternalFarming
  function farmingAddress() external view returns (address);

  /// @notice Returns address of the plugin for which this virtual pool was created
  function plugin() external view returns (address);

  /// @notice Returns data associated with a tick
  function ticks(
    int24 tickId
  )
    external
    view
    returns (
      uint256 liquidityTotal,
      int128 liquidityDelta,
      int24 prevTick,
      int24 nextTick,
      uint256 outerFeeGrowth0Token,
      uint256 outerFeeGrowth1Token
    );

  /// @notice Returns the current liquidity in virtual pool
  function currentLiquidity() external view returns (uint128);

  /// @notice Returns the current tick in virtual pool
  function globalTick() external view returns (int24);

  /// @notice Returns the timestamp after previous virtual pool update
  function prevTimestamp() external view returns (uint32);

  /// @notice Returns true if virtual pool is deactivated
  function deactivated() external view returns (bool);

  /// @dev This function is called when anyone changes their farmed liquidity. The position in a virtual pool should be changed accordingly.
  /// If the virtual pool is deactivated, does nothing.
  /// @param bottomTick The bottom tick of a position
  /// @param topTick The top tick of a position
  /// @param liquidityDelta The amount of liquidity in a position
  /// @param currentTick The current tick in the main pool
  function applyLiquidityDeltaToPosition(int24 bottomTick, int24 topTick, int128 liquidityDelta, int24 currentTick) external;

  /// @dev This function is called by farming to increase rewards per liquidity accumulator.
  /// Can only be called by farming
  function distributeRewards() external;

  /// @notice Change reward rates
  /// @param rate0 The new rate of main token distribution per sec
  /// @param rate1 The new rate of bonus token distribution per sec
  function setRates(uint128 rate0, uint128 rate1) external;

  /// @notice This function is used to deactivate virtual pool
  /// @dev Can only be called by farming
  function deactivate() external;

  /// @notice Top up rewards reserves
  /// @param token0Amount The amount of token0
  /// @param token1Amount The amount of token1
  function addRewards(uint128 token0Amount, uint128 token1Amount) external;

  /// @notice Withdraw rewards from reserves directly
  /// @param token0Amount The amount of token0
  /// @param token1Amount The amount of token1
  function decreaseRewards(uint128 token0Amount, uint128 token1Amount) external;

  /// @notice Retrieves rewards growth data inside specified range
  /// @dev Should only be used for relative comparison of the same range over time
  /// @param bottomTick The lower tick boundary of the range
  /// @param topTick The upper tick boundary of the range
  /// @return rewardGrowthInside0 The all-time reward growth in token0, per unit of liquidity, inside the range's tick boundaries
  /// @return rewardGrowthInside1 The all-time reward growth in token1, per unit of liquidity, inside the range's tick boundaries
  function getInnerRewardsGrowth(int24 bottomTick, int24 topTick) external view returns (uint256 rewardGrowthInside0, uint256 rewardGrowthInside1);

  /// @notice Get reserves of rewards in one call
  /// @return reserve0 The reserve of token0
  /// @return reserve1 The reserve of token1
  function rewardReserves() external view returns (uint128 reserve0, uint128 reserve1);

  /// @notice Get rates of rewards in one call
  /// @return rate0 The rate of token0, rewards / sec
  /// @return rate1 The rate of token1, rewards / sec
  function rewardRates() external view returns (uint128 rate0, uint128 rate1);

  /// @notice Get reward growth accumulators
  /// @return rewardGrowth0 The reward growth for reward0, per unit of liquidity, has only relative meaning
  /// @return rewardGrowth1 The reward growth for reward1, per unit of liquidity, has only relative meaning
  function totalRewardGrowth() external view returns (uint256 rewardGrowth0, uint256 rewardGrowth1);
}

{
  "evmVersion": "paris",
  "optimizer": {
    "enabled": true,
    "runs": 10000
  },
  "metadata": {
    "bytecodeHash": "none"
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  }
}

• No Contract Security Audit Submitted- Submit Audit Here

[{"inputs":[{"internalType":"address","name":"_farmingAddress","type":"address"},{"internalType":"address","name":"_plugin","type":"address"}],"stateMutability":"nonpayable","type":"constructor"},{"inputs":[],"name":"liquidityAdd","type":"error"},{"inputs":[],"name":"liquidityOverflow","type":"error"},{"inputs":[],"name":"liquiditySub","type":"error"},{"inputs":[],"name":"onlyFarming","type":"error"},{"inputs":[],"name":"onlyPlugin","type":"error"},{"inputs":[],"name":"tickInvalidLinks","type":"error"},{"inputs":[],"name":"tickIsNotInitialized","type":"error"},{"inputs":[{"internalType":"uint128","name":"token0Amount","type":"uint128"},{"internalType":"uint128","name":"token1Amount","type":"uint128"}],"name":"addRewards","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"int24","name":"bottomTick","type":"int24"},{"internalType":"int24","name":"topTick","type":"int24"},{"internalType":"int128","name":"liquidityDelta","type":"int128"},{"internalType":"int24","name":"currentTick","type":"int24"}],"name":"applyLiquidityDeltaToPosition","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"int24","name":"targetTick","type":"int24"},{"internalType":"bool","name":"zeroToOne","type":"bool"}],"name":"crossTo","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"currentLiquidity","outputs":[{"internalType":"uint128","name":"","type":"uint128"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"deactivate","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"deactivated","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint128","name":"token0Amount","type":"uint128"},{"internalType":"uint128","name":"token1Amount","type":"uint128"}],"name":"decreaseRewards","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"distributeRewards","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"farmingAddress","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"int24","name":"bottomTick","type":"int24"},{"internalType":"int24","name":"topTick","type":"int24"}],"name":"getInnerRewardsGrowth","outputs":[{"internalType":"uint256","name":"rewardGrowthInside0","type":"uint256"},{"internalType":"uint256","name":"rewardGrowthInside1","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"globalTick","outputs":[{"internalType":"int24","name":"","type":"int24"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"plugin","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"prevTimestamp","outputs":[{"internalType":"uint32","name":"","type":"uint32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"rewardRates","outputs":[{"internalType":"uint128","name":"rate0","type":"uint128"},{"internalType":"uint128","name":"rate1","type":"uint128"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"rewardReserves","outputs":[{"internalType":"uint128","name":"reserve0","type":"uint128"},{"internalType":"uint128","name":"reserve1","type":"uint128"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint128","name":"rate0","type":"uint128"},{"internalType":"uint128","name":"rate1","type":"uint128"}],"name":"setRates","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"int24","name":"tickId","type":"int24"}],"name":"ticks","outputs":[{"internalType":"uint256","name":"liquidityTotal","type":"uint256"},{"internalType":"int128","name":"liquidityDelta","type":"int128"},{"internalType":"int24","name":"prevTick","type":"int24"},{"internalType":"int24","name":"nextTick","type":"int24"},{"internalType":"uint256","name":"outerFeeGrowth0Token","type":"uint256"},{"internalType":"uint256","name":"outerFeeGrowth1Token","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"totalRewardGrowth","outputs":[{"internalType":"uint256","name":"rewardGrowth0","type":"uint256"},{"internalType":"uint256","name":"rewardGrowth1","type":"uint256"}],"stateMutability":"view","type":"function"}]

0x60c0604052600160075560016008553480156200001b57600080fd5b506040516200228038038062002280833981810160405260408110156200004157600080fd5b508051602090910151620000566000620000d2565b6001600160a01b03828116608052811660a0526004805462ffffff63ffffffff60c81b011916600160c81b4263ffffffff160262ffffff19161762f27618179055620000a6620d89e719620001c8565b6004805462ffffff9290921663010000000265ffffff0000001990921691909117905550620001f99050565b620d89e719620000e281620001c8565b620d89e7196000818152602085905260409020600101805465ffffffffffff60801b1916600160981b62ffffff9485160262ffffff60801b191617600160801b9490931693909302919091179091556200013c81620001c8565b8260006200014e620d89e719620001c8565b60020b60020b81526020019081526020016000206001016010846000620d89e7196200017a90620001c8565b60020b81526020810191909152604001600020600101805462ffffff948516600160981b0262ffffff60981b1990911617905581549383166101009190910a90810292021990921617905550565b60008160020b627fffff198103620001f057634e487b7160e01b600052601160045260246000fd5b60000392915050565b60805160a0516120536200022d6000396000818161044101526107e801526000818161028c01526112ec01526120536000f3fe608060405234801561001057600080fd5b50600436106101365760003560e01c80638e76c332116100b2578063d6b83ede11610081578063f0de822811610066578063f0de822814610463578063f30dba9314610495578063fddf08e51461054c57600080fd5b8063d6b83ede14610401578063ef01df4f1461043c57600080fd5b80638e76c332146102d7578063a88a5c1614610315578063ca16ca7e14610384578063d576dfc0146103bb57600080fd5b8063556ed30e116101095780636f4a2cd0116100ee5780636f4a2cd0146102485780637f463bb8146102505780638a2ade581461028757600080fd5b8063556ed30e1461020f5780635e075b531461023d57600080fd5b80630bd6f2001461013b57806334d335901461017e57806346caf2ae146101ba57806351b42b0014610205575b600080fd5b6101656004803603604081101561015157600080fd5b508035600290810b9160200135900b610583565b6040805192835260208301919091528051918290030190f35b6101a66004803603604081101561019457600080fd5b50803560020b906020013515156107ce565b604080519115158252519081900360200190f35b6004546101e090660100000000000090046fffffffffffffffffffffffffffffffff1681565b604080516fffffffffffffffffffffffffffffffff9092168252519081900360200190f35b61020d610bdf565b005b6004546101a6907d010000000000000000000000000000000000000000000000000000000000900460ff1681565b600754600854610165565b61020d610c31565b61020d6004803603604081101561026657600080fd5b506fffffffffffffffffffffffffffffffff81358116916020013516610c43565b6102ae7f000000000000000000000000000000000000000000000000000000000000000081565b6040805173ffffffffffffffffffffffffffffffffffffffff9092168252519081900360200190f35b6004546102fe90760100000000000000000000000000000000000000000000900460020b81565b6040805160029290920b8252519081900360200190f35b6005546fffffffffffffffffffffffffffffffff808216917001000000000000000000000000000000009004165b60405180836fffffffffffffffffffffffffffffffff168152602001826fffffffffffffffffffffffffffffffff1681526020019250505060405180910390f35b61020d6004803603604081101561039a57600080fd5b506fffffffffffffffffffffffffffffffff81358116916020013516610ca4565b6004546103e890790100000000000000000000000000000000000000000000000000900463ffffffff1681565b6040805163ffffffff9092168252519081900360200190f35b61020d6004803603608081101561041757600080fd5b508035600290810b916020810135820b916040820135600f0b9160600135900b610cbc565b6102ae7f000000000000000000000000000000000000000000000000000000000000000081565b6006546fffffffffffffffffffffffffffffffff80821691700100000000000000000000000000000000900416610343565b610510600480360360208110156104ab57600080fd5b50600060208190529035600290810b8252604090912080546001820154828401546003909301549193600f82900b937001000000000000000000000000000000008304820b9373010000000000000000000000000000000000000090930490910b9186565b60408051968752600f9590950b6020870152600293840b868601529190920b6060850152608084019190915260a0830152519081900360c00190f35b61020d6004803603604081101561056257600080fd5b506fffffffffffffffffffffffffffffffff81358116916020013516610ed4565b600282810b600090815260208190526040812060010154909182917001000000000000000000000000000000008104820b73010000000000000000000000000000000000000090910490910b14806106205750600283810b6000908152602081905260409020600101547001000000000000000000000000000000008104820b73010000000000000000000000000000000000000090910490910b145b15610657576040517f0d6e094900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60045460075460085463ffffffff79010000000000000000000000000000000000000000000000000084048116420393760100000000000000000000000000000000000000000000900460020b9291908416156107af57600454660100000000000090046fffffffffffffffffffffffffffffffff1680156107ad5760055460065463ffffffff87166fffffffffffffffffffffffffffffffff8084168202811693700100000000000000000000000000000000908190048216909202811692818116929004168184111561072a578193505b80831115610736578092505b831561076f5761076a84700100000000000000000000000000000000876fffffffffffffffffffffffffffffffff16610ee8565b870196505b82156107a8576107a383700100000000000000000000000000000000876fffffffffffffffffffffffffffffffff16610ee8565b860195505b505050505b505b6107be60008989868686610fa0565b95509550505050505b9250929050565b60003373ffffffffffffffffffffffffffffffffffffffff7f0000000000000000000000000000000000000000000000000000000000000000161461083f576040517f545acb2400000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6004546fffffffffffffffffffffffffffffffff6601000000000000820416907601000000000000000000000000000000000000000000008104600290810b9163ffffffff7901000000000000000000000000000000000000000000000000008204169160ff7d0100000000000000000000000000000000000000000000000000000000008304169180820b916301000000909104900b82156108eb5760009650505050505050610bd9565b600285810b908a900b1380159061091e578260020b8a60020b12610919576001975050505050505050610bd9565b61093c565b8160020b8a60020b121561093c576001975050505050505050610bd9565b881515811515146109a0575050600480547fffff00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff167d0100000000000000000000000000000000000000000000000000000000001790555060009450610bd99350505050565b6109bc85886fffffffffffffffffffffffffffffffff1661103e565b6007546008548a15610a71575b600288900b620d89e71914610a6c578460020b8c60020b1215610b0257600285810b600090815260208190526040812060038101805482850180548803905585039055600101547fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff88019a50700100000000000000000000000000000000810490920b969550600f9190910b90610a64908b9083900361120d565b9950506109c9565b610b02565b6001610a80620d89e719611f26565b610a8a9190611f64565b60020b8860020b14610b02578360020b8c60020b12610b0257600284810b600090815260208190526040902060038101805482840180548703905584039055600101549498508895507301000000000000000000000000000000000000008504900b93600f0b610afa8a8261120d565b995050610a71565b50506004805462ffffff9384166301000000027fffffffffffffffffffffffffffffffffffffffffffffffffffff000000000000858e16760100000000000000000000000000000000000000000000027fffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffff6fffffffffffffffffffffffffffffffff909c166601000000000000029b909b167fffffffffffffff00000000000000000000000000000000000000ffffffffffff90931692909217999099171693909216929092179590951790945550600193505050505b92915050565b610be76112d4565b600480547fffff00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff167d010000000000000000000000000000000000000000000000000000000000179055565b610c396112d4565b610c41611343565b565b610c4b6112d4565b610c53611343565b6fffffffffffffffffffffffffffffffff9182169116700100000000000000000000000000000000027fffffffffffffffffffffffffffffffff000000000000000000000000000000001617600555565b610cac6112d4565b610cb86000838361138f565b5050565b610cc46112d4565b6004546fffffffffffffffffffffffffffffffff66010000000000008204169063ffffffff7901000000000000000000000000000000000000000000000000008204169060ff7d0100000000000000000000000000000000000000000000000000000000008204169063010000008104600290810b91900b82610d9d57610d4c86828461146f565b610d9d57600480547fffff00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff167d010000000000000000000000000000000000000000000000000000000000179055600192505b50508015610dad57505050610ece565b600480547fffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffff1676010000000000000000000000000000000000000000000062ffffff87160217905563ffffffff82164263ffffffff161115610e2557610e2582846fffffffffffffffffffffffffffffffff1661103e565b84600f0b600014610eca576000610e3f8886886000611494565b90506000610e508887896001611494565b9050610e5d868a8a61146f565b15610ea557610e6c858861120d565b600460066101000a8154816fffffffffffffffffffffffffffffffff02191690836fffffffffffffffffffffffffffffffff1602179055505b8180610eae5750805b15610ec757610ec7898984848a60008d600f0b126114b8565b50505b5050505b50505050565b610edc6112d4565b610cb86001838361138f565b6000838302817fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff85870982811083820303915050808411610f2857600080fd5b80600003610f3b57508290049050610f99565b8385870960008581038616958690049560026003880281188089028203028089028203028089028203028089028203028089028203028089029091030291819003819004600101858411909403939093029190930391909104170290505b9392505050565b600285810b60009081526020889052604080822087840b8084529183209293849391929088900b1215611016578860020b8760020b12610ff157816002015486039350816003015485039250611000565b81600201549350816003015492505b6002810154600382015494039390920391611031565b81600201548160020154039350816003015481600301540392505b5050965096945050505050565b63ffffffff4283900316600081900361105657505050565b81156111bc576005546006546fffffffffffffffffffffffffffffffff8083168402927001000000000000000000000000000000009081900482168502928083169291900416818411156110ba57816fffffffffffffffffffffffffffffffff1693505b806fffffffffffffffffffffffffffffffff168311156110ea57806fffffffffffffffffffffffffffffffff1692505b838317156111b7576fffffffffffffffffffffffffffffffff9182168490039116829003831561113a576111308470010000000000000000000000000000000088610ee8565b6007805490910190555b82156111665761115c8370010000000000000000000000000000000088610ee8565b6008805490910190555b6fffffffffffffffffffffffffffffffff808316908216700100000000000000000000000000000000027fffffffffffffffffffffffffffffffff0000000000000000000000000000000016176006555b505050505b5050600480547fffffff00000000ffffffffffffffffffffffffffffffffffffffffffffffffff167901000000000000000000000000000000000000000000000000004263ffffffff160217905550565b60008082600f0b121561127157508082016fffffffffffffffffffffffffffffffff8084169082161061126c576040517f1301f74800000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b610bd9565b826fffffffffffffffffffffffffffffffff168284019150816fffffffffffffffffffffffffffffffff161015610bd9576040517f997402f200000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b3373ffffffffffffffffffffffffffffffffffffffff7f00000000000000000000000000000000000000000000000000000000000000001614610c41576040517fae74b17800000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600454610c4190790100000000000000000000000000000000000000000000000000810463ffffffff1690660100000000000090046fffffffffffffffffffffffffffffffff1661103e565b611397611343565b6fffffffffffffffffffffffffffffffff828217161561146a576006546fffffffffffffffffffffffffffffffff808216917001000000000000000000000000000000009004168415611401576113ee8483611fa5565b91506113fa8382611fa5565b905061141a565b61140b8483611fd5565b91506114178382611fd5565b90505b6fffffffffffffffffffffffffffffffff9182169116700100000000000000000000000000000000027fffffffffffffffffffffffffffffffff0000000000000000000000000000000016176006555b505050565b60008260020b8460020b1215801561148c57508160020b8460020b125b949350505050565b6007546008546000916114af918391889188918891886115e7565b95945050505050565b600454600154600282810b9263010000009004900b9063ffffffff1682828289156114f3576114eb8c898386868c61171b565b919450925090505b881561150f576115078b898386868c61171b565b919450925090505b8260020b8660020b14158061152a57508160020b8560020b14155b8061154157508363ffffffff168163ffffffff1614155b156115d957600180547fffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000001663ffffffff8316179055600480547fffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000016630100000062ffffff858116919091027fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000016919091179085161790555b505050505050505050505050565b600286900b6000908152602088905260408120805482611607828961120d565b6fffffffffffffffffffffffffffffffff1690506d09745258e83de0d0f4e400fce799811115611663576040517f25b8364a00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6001830154600f0b856116875788600f0b81600f0b6116829190611ffe565b611699565b88600f0b81600f0b6116999190612026565b6001850180547fffffffffffffffffffffffffffffffff00000000000000000000000000000000166fffffffffffffffffffffffffffffffff9290921691909117905581845581159450600083900361170c57841594508960020b8b60020b1361170c5760038401879055600284018890555b50505050979650505050505050565b6000806000831561176457600080611733818c61181c565b915091508a60020b8860020b0361174c5781975061175d565b8a60020b8760020b0361175d578096505b50506117fa565b6000808a60020b8860020b12801561178157508a60020b8760020b135b156117aa57508690508560028a810b908c900b13156117a2578a96506117ea565b8a97506117ea565b6117b8600360028b8e611a5a565b600281810b6000908152602081905260409020600101547001000000000000000000000000000000009004900b925090505b6117f760008c8484611b37565b50505b600061180a600360028a8d611cab565b969a9599509597509395505050505050565b600281810b60008181526020859052604081206001810180548383557fffffffffffffffffffff0000000000000000000000000000000000000000000081169091558185018390556003909101919091557001000000000000000000000000000000008104830b92730100000000000000000000000000000000000000909104900b90620d89e71914806118c157506118b8620d89e719611f26565b60020b8360020b145b1561196657600283900b6000908152602085905260409020600101805462ffffff808516700100000000000000000000000000000000027fffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffff91851673010000000000000000000000000000000000000002919091167fffffffffffffffffffff000000000000ffffffffffffffffffffffffffffffff909216919091171790556107c7565b8060020b8260020b036119a5576040517f0d6e094900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600282810b6000908152602086905260408082206001908101805462ffffff808816730100000000000000000000000000000000000000027fffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffff909216919091179091559385900b83529120018054918416700100000000000000000000000000000000027fffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffff9092169190911790559250929050565b600190810190600090600883811d610d8a01901c90829061ffff83161b851663ffffffff1615611abd57611a8e8785611d43565b90945090925090508015611aa357505061148c565b611ab486610d8b840160010b611d43565b90945090925090505b80611b0057611adb8563ffffffff168360010193508360010b611d74565b909350905080611af35750620d89e8915061148c9050565b611afd8684611ecb565b92505b611b2c877ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff2768501611ecb565b979650505050505050565b600283900b620d89e7191480611b5e5750611b55620d89e719611f26565b60020b8360020b145b610ece578260020b8260020b128015611b7c57508260020b8160020b135b611bb2576040517fe45ac17d00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600283810b60009081526020959095526040808620600190810180547fffffffffffffffffffff000000000000ffffffffffffffffffffffffffffffff1673010000000000000000000000000000000000000062ffffff87811682027fffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffff908116939093177001000000000000000000000000000000008a831681029190911790945597860b8a52848a20840180547fffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffff1698909916908102979097179097559390920b865290942090930180549092169202919091179055565b81600080611ce88785600881901d600181810b60009081526020949094526040909320805460ff9093169390931b80831890935591811490151891565b915091508115611d3957610d8a01600181810b60081d80820b6000908152602089905260409020805460ff9094169290921b808418909255821591909214818118935014611d39576001811b831892505b5050949350505050565b600881901d600181900b6000908152602084905260408120548190611d689085611d74565b93969095509293505050565b60008060ff831684811c808303611d90578460ff179350611ec2565b7f555555555555555555555555555555555555555555555555555555555555555560008290038216908116156fffffffffffffffffffffffffffffffff82161560071b1777ffffffffffffffff0000000000000000ffffffffffffffff82161560061b177bffffffff00000000ffffffff00000000ffffffff00000000ffffffff82161560051b177dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff82161560041b177eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff82161560031b177f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f82161560021b177f33333333333333333333333333333333333333333333333333333333333333339091161560011b1760ff1685019350600192505b50509250929050565b600181900b600090815260208390526040902054600882901b90611eef9082611d74565b509392505050565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052601160045260246000fd5b60008160020b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8000008103611f5b57611f5b611ef7565b60000392915050565b600282810b9082900b037fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8000008112627fffff82131715610bd957610bd9611ef7565b6fffffffffffffffffffffffffffffffff818116838216019080821115611fce57611fce611ef7565b5092915050565b6fffffffffffffffffffffffffffffffff828116828216039080821115611fce57611fce611ef7565b808201828112600083128015821682158216171561201e5761201e611ef7565b505092915050565b8181036000831280158383131683831282161715611fce57611fce611ef756fea164736f6c6343000814000a0000000000000000000000001e862624eda92b8fe532c16253356d17dd70a337000000000000000000000000cbe3fefdc43cdb24869097ebd55f881ce2b82065

0x608060405234801561001057600080fd5b50600436106101365760003560e01c80638e76c332116100b2578063d6b83ede11610081578063f0de822811610066578063f0de822814610463578063f30dba9314610495578063fddf08e51461054c57600080fd5b8063d6b83ede14610401578063ef01df4f1461043c57600080fd5b80638e76c332146102d7578063a88a5c1614610315578063ca16ca7e14610384578063d576dfc0146103bb57600080fd5b8063556ed30e116101095780636f4a2cd0116100ee5780636f4a2cd0146102485780637f463bb8146102505780638a2ade581461028757600080fd5b8063556ed30e1461020f5780635e075b531461023d57600080fd5b80630bd6f2001461013b57806334d335901461017e57806346caf2ae146101ba57806351b42b0014610205575b600080fd5b6101656004803603604081101561015157600080fd5b508035600290810b9160200135900b610583565b6040805192835260208301919091528051918290030190f35b6101a66004803603604081101561019457600080fd5b50803560020b906020013515156107ce565b604080519115158252519081900360200190f35b6004546101e090660100000000000090046fffffffffffffffffffffffffffffffff1681565b604080516fffffffffffffffffffffffffffffffff9092168252519081900360200190f35b61020d610bdf565b005b6004546101a6907d010000000000000000000000000000000000000000000000000000000000900460ff1681565b600754600854610165565b61020d610c31565b61020d6004803603604081101561026657600080fd5b506fffffffffffffffffffffffffffffffff81358116916020013516610c43565b6102ae7f0000000000000000000000001e862624eda92b8fe532c16253356d17dd70a33781565b6040805173ffffffffffffffffffffffffffffffffffffffff9092168252519081900360200190f35b6004546102fe90760100000000000000000000000000000000000000000000900460020b81565b6040805160029290920b8252519081900360200190f35b6005546fffffffffffffffffffffffffffffffff808216917001000000000000000000000000000000009004165b60405180836fffffffffffffffffffffffffffffffff168152602001826fffffffffffffffffffffffffffffffff1681526020019250505060405180910390f35b61020d6004803603604081101561039a57600080fd5b506fffffffffffffffffffffffffffffffff81358116916020013516610ca4565b6004546103e890790100000000000000000000000000000000000000000000000000900463ffffffff1681565b6040805163ffffffff9092168252519081900360200190f35b61020d6004803603608081101561041757600080fd5b508035600290810b916020810135820b916040820135600f0b9160600135900b610cbc565b6102ae7f000000000000000000000000cbe3fefdc43cdb24869097ebd55f881ce2b8206581565b6006546fffffffffffffffffffffffffffffffff80821691700100000000000000000000000000000000900416610343565b610510600480360360208110156104ab57600080fd5b50600060208190529035600290810b8252604090912080546001820154828401546003909301549193600f82900b937001000000000000000000000000000000008304820b9373010000000000000000000000000000000000000090930490910b9186565b60408051968752600f9590950b6020870152600293840b868601529190920b6060850152608084019190915260a0830152519081900360c00190f35b61020d6004803603604081101561056257600080fd5b506fffffffffffffffffffffffffffffffff81358116916020013516610ed4565b600282810b600090815260208190526040812060010154909182917001000000000000000000000000000000008104820b73010000000000000000000000000000000000000090910490910b14806106205750600283810b6000908152602081905260409020600101547001000000000000000000000000000000008104820b73010000000000000000000000000000000000000090910490910b145b15610657576040517f0d6e094900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60045460075460085463ffffffff79010000000000000000000000000000000000000000000000000084048116420393760100000000000000000000000000000000000000000000900460020b9291908416156107af57600454660100000000000090046fffffffffffffffffffffffffffffffff1680156107ad5760055460065463ffffffff87166fffffffffffffffffffffffffffffffff8084168202811693700100000000000000000000000000000000908190048216909202811692818116929004168184111561072a578193505b80831115610736578092505b831561076f5761076a84700100000000000000000000000000000000876fffffffffffffffffffffffffffffffff16610ee8565b870196505b82156107a8576107a383700100000000000000000000000000000000876fffffffffffffffffffffffffffffffff16610ee8565b860195505b505050505b505b6107be60008989868686610fa0565b95509550505050505b9250929050565b60003373ffffffffffffffffffffffffffffffffffffffff7f000000000000000000000000cbe3fefdc43cdb24869097ebd55f881ce2b82065161461083f576040517f545acb2400000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6004546fffffffffffffffffffffffffffffffff6601000000000000820416907601000000000000000000000000000000000000000000008104600290810b9163ffffffff7901000000000000000000000000000000000000000000000000008204169160ff7d0100000000000000000000000000000000000000000000000000000000008304169180820b916301000000909104900b82156108eb5760009650505050505050610bd9565b600285810b908a900b1380159061091e578260020b8a60020b12610919576001975050505050505050610bd9565b61093c565b8160020b8a60020b121561093c576001975050505050505050610bd9565b881515811515146109a0575050600480547fffff00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff167d0100000000000000000000000000000000000000000000000000000000001790555060009450610bd99350505050565b6109bc85886fffffffffffffffffffffffffffffffff1661103e565b6007546008548a15610a71575b600288900b620d89e71914610a6c578460020b8c60020b1215610b0257600285810b600090815260208190526040812060038101805482850180548803905585039055600101547fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff88019a50700100000000000000000000000000000000810490920b969550600f9190910b90610a64908b9083900361120d565b9950506109c9565b610b02565b6001610a80620d89e719611f26565b610a8a9190611f64565b60020b8860020b14610b02578360020b8c60020b12610b0257600284810b600090815260208190526040902060038101805482840180548703905584039055600101549498508895507301000000000000000000000000000000000000008504900b93600f0b610afa8a8261120d565b995050610a71565b50506004805462ffffff9384166301000000027fffffffffffffffffffffffffffffffffffffffffffffffffffff000000000000858e16760100000000000000000000000000000000000000000000027fffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffff6fffffffffffffffffffffffffffffffff909c166601000000000000029b909b167fffffffffffffff00000000000000000000000000000000000000ffffffffffff90931692909217999099171693909216929092179590951790945550600193505050505b92915050565b610be76112d4565b600480547fffff00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff167d010000000000000000000000000000000000000000000000000000000000179055565b610c396112d4565b610c41611343565b565b610c4b6112d4565b610c53611343565b6fffffffffffffffffffffffffffffffff9182169116700100000000000000000000000000000000027fffffffffffffffffffffffffffffffff000000000000000000000000000000001617600555565b610cac6112d4565b610cb86000838361138f565b5050565b610cc46112d4565b6004546fffffffffffffffffffffffffffffffff66010000000000008204169063ffffffff7901000000000000000000000000000000000000000000000000008204169060ff7d0100000000000000000000000000000000000000000000000000000000008204169063010000008104600290810b91900b82610d9d57610d4c86828461146f565b610d9d57600480547fffff00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff167d010000000000000000000000000000000000000000000000000000000000179055600192505b50508015610dad57505050610ece565b600480547fffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffff1676010000000000000000000000000000000000000000000062ffffff87160217905563ffffffff82164263ffffffff161115610e2557610e2582846fffffffffffffffffffffffffffffffff1661103e565b84600f0b600014610eca576000610e3f8886886000611494565b90506000610e508887896001611494565b9050610e5d868a8a61146f565b15610ea557610e6c858861120d565b600460066101000a8154816fffffffffffffffffffffffffffffffff02191690836fffffffffffffffffffffffffffffffff1602179055505b8180610eae5750805b15610ec757610ec7898984848a60008d600f0b126114b8565b50505b5050505b50505050565b610edc6112d4565b610cb86001838361138f565b6000838302817fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff85870982811083820303915050808411610f2857600080fd5b80600003610f3b57508290049050610f99565b8385870960008581038616958690049560026003880281188089028203028089028203028089028203028089028203028089028203028089029091030291819003819004600101858411909403939093029190930391909104170290505b9392505050565b600285810b60009081526020889052604080822087840b8084529183209293849391929088900b1215611016578860020b8760020b12610ff157816002015486039350816003015485039250611000565b81600201549350816003015492505b6002810154600382015494039390920391611031565b81600201548160020154039350816003015481600301540392505b5050965096945050505050565b63ffffffff4283900316600081900361105657505050565b81156111bc576005546006546fffffffffffffffffffffffffffffffff8083168402927001000000000000000000000000000000009081900482168502928083169291900416818411156110ba57816fffffffffffffffffffffffffffffffff1693505b806fffffffffffffffffffffffffffffffff168311156110ea57806fffffffffffffffffffffffffffffffff1692505b838317156111b7576fffffffffffffffffffffffffffffffff9182168490039116829003831561113a576111308470010000000000000000000000000000000088610ee8565b6007805490910190555b82156111665761115c8370010000000000000000000000000000000088610ee8565b6008805490910190555b6fffffffffffffffffffffffffffffffff808316908216700100000000000000000000000000000000027fffffffffffffffffffffffffffffffff0000000000000000000000000000000016176006555b505050505b5050600480547fffffff00000000ffffffffffffffffffffffffffffffffffffffffffffffffff167901000000000000000000000000000000000000000000000000004263ffffffff160217905550565b60008082600f0b121561127157508082016fffffffffffffffffffffffffffffffff8084169082161061126c576040517f1301f74800000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b610bd9565b826fffffffffffffffffffffffffffffffff168284019150816fffffffffffffffffffffffffffffffff161015610bd9576040517f997402f200000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b3373ffffffffffffffffffffffffffffffffffffffff7f0000000000000000000000001e862624eda92b8fe532c16253356d17dd70a3371614610c41576040517fae74b17800000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600454610c4190790100000000000000000000000000000000000000000000000000810463ffffffff1690660100000000000090046fffffffffffffffffffffffffffffffff1661103e565b611397611343565b6fffffffffffffffffffffffffffffffff828217161561146a576006546fffffffffffffffffffffffffffffffff808216917001000000000000000000000000000000009004168415611401576113ee8483611fa5565b91506113fa8382611fa5565b905061141a565b61140b8483611fd5565b91506114178382611fd5565b90505b6fffffffffffffffffffffffffffffffff9182169116700100000000000000000000000000000000027fffffffffffffffffffffffffffffffff0000000000000000000000000000000016176006555b505050565b60008260020b8460020b1215801561148c57508160020b8460020b125b949350505050565b6007546008546000916114af918391889188918891886115e7565b95945050505050565b600454600154600282810b9263010000009004900b9063ffffffff1682828289156114f3576114eb8c898386868c61171b565b919450925090505b881561150f576115078b898386868c61171b565b919450925090505b8260020b8660020b14158061152a57508160020b8560020b14155b8061154157508363ffffffff168163ffffffff1614155b156115d957600180547fffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000001663ffffffff8316179055600480547fffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000016630100000062ffffff858116919091027fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000016919091179085161790555b505050505050505050505050565b600286900b6000908152602088905260408120805482611607828961120d565b6fffffffffffffffffffffffffffffffff1690506d09745258e83de0d0f4e400fce799811115611663576040517f25b8364a00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6001830154600f0b856116875788600f0b81600f0b6116829190611ffe565b611699565b88600f0b81600f0b6116999190612026565b6001850180547fffffffffffffffffffffffffffffffff00000000000000000000000000000000166fffffffffffffffffffffffffffffffff9290921691909117905581845581159450600083900361170c57841594508960020b8b60020b1361170c5760038401879055600284018890555b50505050979650505050505050565b6000806000831561176457600080611733818c61181c565b915091508a60020b8860020b0361174c5781975061175d565b8a60020b8760020b0361175d578096505b50506117fa565b6000808a60020b8860020b12801561178157508a60020b8760020b135b156117aa57508690508560028a810b908c900b13156117a2578a96506117ea565b8a97506117ea565b6117b8600360028b8e611a5a565b600281810b6000908152602081905260409020600101547001000000000000000000000000000000009004900b925090505b6117f760008c8484611b37565b50505b600061180a600360028a8d611cab565b969a9599509597509395505050505050565b600281810b60008181526020859052604081206001810180548383557fffffffffffffffffffff0000000000000000000000000000000000000000000081169091558185018390556003909101919091557001000000000000000000000000000000008104830b92730100000000000000000000000000000000000000909104900b90620d89e71914806118c157506118b8620d89e719611f26565b60020b8360020b145b1561196657600283900b6000908152602085905260409020600101805462ffffff808516700100000000000000000000000000000000027fffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffff91851673010000000000000000000000000000000000000002919091167fffffffffffffffffffff000000000000ffffffffffffffffffffffffffffffff909216919091171790556107c7565b8060020b8260020b036119a5576040517f0d6e094900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600282810b6000908152602086905260408082206001908101805462ffffff808816730100000000000000000000000000000000000000027fffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffff909216919091179091559385900b83529120018054918416700100000000000000000000000000000000027fffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffff9092169190911790559250929050565b600190810190600090600883811d610d8a01901c90829061ffff83161b851663ffffffff1615611abd57611a8e8785611d43565b90945090925090508015611aa357505061148c565b611ab486610d8b840160010b611d43565b90945090925090505b80611b0057611adb8563ffffffff168360010193508360010b611d74565b909350905080611af35750620d89e8915061148c9050565b611afd8684611ecb565b92505b611b2c877ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff2768501611ecb565b979650505050505050565b600283900b620d89e7191480611b5e5750611b55620d89e719611f26565b60020b8360020b145b610ece578260020b8260020b128015611b7c57508260020b8160020b135b611bb2576040517fe45ac17d00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600283810b60009081526020959095526040808620600190810180547fffffffffffffffffffff000000000000ffffffffffffffffffffffffffffffff1673010000000000000000000000000000000000000062ffffff87811682027fffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffff908116939093177001000000000000000000000000000000008a831681029190911790945597860b8a52848a20840180547fffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffff1698909916908102979097179097559390920b865290942090930180549092169202919091179055565b81600080611ce88785600881901d600181810b60009081526020949094526040909320805460ff9093169390931b80831890935591811490151891565b915091508115611d3957610d8a01600181810b60081d80820b6000908152602089905260409020805460ff9094169290921b808418909255821591909214818118935014611d39576001811b831892505b5050949350505050565b600881901d600181900b6000908152602084905260408120548190611d689085611d74565b93969095509293505050565b60008060ff831684811c808303611d90578460ff179350611ec2565b7f555555555555555555555555555555555555555555555555555555555555555560008290038216908116156fffffffffffffffffffffffffffffffff82161560071b1777ffffffffffffffff0000000000000000ffffffffffffffff82161560061b177bffffffff00000000ffffffff00000000ffffffff00000000ffffffff82161560051b177dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff82161560041b177eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff82161560031b177f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f82161560021b177f33333333333333333333333333333333333333333333333333333333333333339091161560011b1760ff1685019350600192505b50509250929050565b600181900b600090815260208390526040902054600882901b90611eef9082611d74565b509392505050565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052601160045260246000fd5b60008160020b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8000008103611f5b57611f5b611ef7565b60000392915050565b600282810b9082900b037fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8000008112627fffff82131715610bd957610bd9611ef7565b6fffffffffffffffffffffffffffffffff818116838216019080821115611fce57611fce611ef7565b5092915050565b6fffffffffffffffffffffffffffffffff828116828216039080821115611fce57611fce611ef7565b808201828112600083128015821682158216171561201e5761201e611ef7565b505092915050565b8181036000831280158383131683831282161715611fce57611fce611ef756fea164736f6c6343000814000a