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

import { MerkleZeros as MerkleQuinaryMaci } from "./zeros/MerkleQuinaryMaci.sol";
import { AccQueueQuinary } from "./AccQueueQuinary.sol";

/// @title AccQueueQuinaryMaci
/// @notice This contract extends AccQueueQuinary and MerkleQuinaryMaci
/// @dev This contract is used for creating a
/// Merkle tree with quinary (5 leaves per node) structure
contract AccQueueQuinaryMaci is AccQueueQuinary, MerkleQuinaryMaci {
  /// @notice Constructor for creating AccQueueQuinaryMaci contract
  /// @param _subDepth The depth of each subtree
  constructor(uint256 _subDepth) AccQueueQuinary(_subDepth) {}

  /// @notice Returns the zero leaf at a specified level
  /// @param _level The level at which to return the zero leaf
  /// @return zero The zero leaf at the specified level
  function getZero(uint256 _level) internal view override returns (uint256 zero) {
    zero = zeros[_level];
  }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (access/Ownable.sol)

pragma solidity ^0.8.20;

import {Context} from "../utils/Context.sol";

/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * The initial owner is set to the address provided by the deployer. This can
 * later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;

    /**
     * @dev The caller account is not authorized to perform an operation.
     */
    error OwnableUnauthorizedAccount(address account);

    /**
     * @dev The owner is not a valid owner account. (eg. `address(0)`)
     */
    error OwnableInvalidOwner(address owner);

    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);

    /**
     * @dev Initializes the contract setting the address provided by the deployer as the initial owner.
     */
    constructor(address initialOwner) {
        if (initialOwner == address(0)) {
            revert OwnableInvalidOwner(address(0));
        }
        _transferOwnership(initialOwner);
    }

    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        _checkOwner();
        _;
    }

    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }

    /**
     * @dev Throws if the sender is not the owner.
     */
    function _checkOwner() internal view virtual {
        if (owner() != _msgSender()) {
            revert OwnableUnauthorizedAccount(_msgSender());
        }
    }

    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby disabling any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _transferOwnership(address(0));
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        if (newOwner == address(0)) {
            revert OwnableInvalidOwner(address(0));
        }
        _transferOwnership(newOwner);
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Internal function without access restriction.
     */
    function _transferOwnership(address newOwner) internal virtual {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.1) (utils/Context.sol)

pragma solidity ^0.8.20;

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

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

    function _contextSuffixLength() internal view virtual returns (uint256) {
        return 0;
    }
}

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

import { SnarkConstants } from "./SnarkConstants.sol";
import { PoseidonT3 } from "./PoseidonT3.sol";
import { PoseidonT4 } from "./PoseidonT4.sol";
import { PoseidonT5 } from "./PoseidonT5.sol";
import { PoseidonT6 } from "./PoseidonT6.sol";

/// @notice A SHA256 hash function for any number of input elements, and Poseidon hash
/// functions for 2, 3, 4, 5, and 12 input elements.
contract Hasher is SnarkConstants {
  /// @notice Computes the SHA256 hash of an array of uint256 elements.
  /// @param array The array of uint256 elements.
  /// @return result The SHA256 hash of the array.
  function sha256Hash(uint256[] memory array) public pure returns (uint256 result) {
    result = uint256(sha256(abi.encodePacked(array))) % SNARK_SCALAR_FIELD;
  }

  /// @notice Computes the Poseidon hash of two uint256 elements.
  /// @param array An array of two uint256 elements.
  /// @return result The Poseidon hash of the two elements.
  function hash2(uint256[2] memory array) public pure returns (uint256 result) {
    result = PoseidonT3.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of three uint256 elements.
  /// @param array An array of three uint256 elements.
  /// @return result The Poseidon hash of the three elements.
  function hash3(uint256[3] memory array) public pure returns (uint256 result) {
    result = PoseidonT4.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of four uint256 elements.
  /// @param array An array of four uint256 elements.
  /// @return result The Poseidon hash of the four elements.
  function hash4(uint256[4] memory array) public pure returns (uint256 result) {
    result = PoseidonT5.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of five uint256 elements.
  /// @param array An array of five uint256 elements.
  /// @return result The Poseidon hash of the five elements.
  function hash5(uint256[5] memory array) public pure returns (uint256 result) {
    result = PoseidonT6.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of two uint256 elements.
  /// @param left the first element to hash.
  /// @param right the second element to hash.
  /// @return result The Poseidon hash of the two elements.
  function hashLeftRight(uint256 left, uint256 right) public pure returns (uint256 result) {
    uint256[2] memory input;
    input[0] = left;
    input[1] = right;
    result = hash2(input);
  }
}

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

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT3 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[2] memory input) public pure returns (uint256) {}
}

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

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT4 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[3] memory input) public pure returns (uint256) {}
}

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

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT5 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[4] memory input) public pure returns (uint256) {}
}

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

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT6 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[5] memory input) public pure returns (uint256) {}
}

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

/// @title SnarkConstants
/// @notice This contract contains constants related to the SNARK
/// components of MACI.
contract SnarkConstants {
  /// @notice The scalar field
  uint256 internal constant SNARK_SCALAR_FIELD =
    21888242871839275222246405745257275088548364400416034343698204186575808495617;

  /// @notice The public key here is the first Pedersen base
  /// point from iden3's circomlib implementation of the Pedersen hash.
  /// Since it is generated using a hash-to-curve function, we are
  /// confident that no-one knows the private key associated with this
  /// public key. See:
  /// https://github.com/iden3/circomlib/blob/d5ed1c3ce4ca137a6b3ca48bec4ac12c1b38957a/src/pedersen_printbases.js
  /// Its hash should equal
  /// 6769006970205099520508948723718471724660867171122235270773600567925038008762.
  uint256 internal constant PAD_PUBKEY_X =
    10457101036533406547632367118273992217979173478358440826365724437999023779287;
  uint256 internal constant PAD_PUBKEY_Y =
    19824078218392094440610104313265183977899662750282163392862422243483260492317;

  /// @notice The Keccack256 hash of 'Maci'
  uint256 internal constant NOTHING_UP_MY_SLEEVE =
    8370432830353022751713833565135785980866757267633941821328460903436894336785;
}

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

import { Ownable } from "@openzeppelin/contracts/access/Ownable.sol";
import { Hasher } from "../crypto/Hasher.sol";

/// @title AccQueue
/// @notice This contract defines a Merkle tree where each leaf insertion only updates a
/// subtree. To obtain the main tree root, the contract owner must merge the
/// subtrees together. Merging subtrees requires at least 2 operations:
/// mergeSubRoots(), and merge(). To get around the gas limit,
/// the mergeSubRoots() can be performed in multiple transactions.
abstract contract AccQueue is Ownable(msg.sender), Hasher {
  // The maximum tree depth
  uint256 public constant MAX_DEPTH = 32;

  /// @notice A Queue is a 2D array of Merkle roots and indices which represents nodes
  /// in a Merkle tree while it is progressively updated.
  struct Queue {
    /// @notice IMPORTANT: the following declares an array of b elements of type T: T[b]
    /// And the following declares an array of b elements of type T[a]: T[a][b]
    /// As such, the following declares an array of MAX_DEPTH+1 arrays of
    /// uint256[4] arrays, **not the other way round**:
    uint256[4][MAX_DEPTH + 1] levels;
    uint256[MAX_DEPTH + 1] indices;
  }

  // The depth of each subtree
  uint256 internal immutable subDepth;

  // The number of elements per hash operation. Should be either 2 (for
  // binary trees) or 5 (quinary trees). The limit is 5 because that is the
  // maximum supported number of inputs for the EVM implementation of the
  // Poseidon hash function
  uint256 internal immutable hashLength;

  // hashLength ** subDepth
  uint256 internal immutable subTreeCapacity;

  // True hashLength == 2, false if hashLength == 5
  bool internal isBinary;

  // The index of the current subtree. e.g. the first subtree has index 0, the
  // second has 1, and so on
  uint256 internal currentSubtreeIndex;

  // Tracks the current subtree.
  Queue internal leafQueue;

  // Tracks the smallest tree of subroots
  Queue internal subRootQueue;

  // Subtree roots
  mapping(uint256 => uint256) internal subRoots;

  // Merged roots
  uint256[MAX_DEPTH + 1] internal mainRoots;

  // Whether the subtrees have been merged
  bool public subTreesMerged;

  // Whether entire merkle tree has been merged
  bool public treeMerged;

  // The root of the shortest possible tree which fits all current subtree
  // roots
  uint256 internal smallSRTroot;

  // Tracks the next subroot to queue
  uint256 internal nextSubRootIndex;

  // The number of leaves inserted across all subtrees so far
  uint256 public numLeaves;

  /// @notice custom errors
  error SubDepthCannotBeZero();
  error SubdepthTooLarge(uint256 _subDepth, uint256 max);
  error InvalidHashLength();
  error DepthCannotBeZero();
  error SubTreesAlreadyMerged();
  error NothingToMerge();
  error SubTreesNotMerged();
  error DepthTooLarge(uint256 _depth, uint256 max);
  error DepthTooSmall(uint256 _depth, uint256 min);
  error InvalidIndex(uint256 _index);
  error InvalidLevel();

  /// @notice Create a new AccQueue
  /// @param _subDepth The depth of each subtree.
  /// @param _hashLength The number of leaves per node (2 or 5).
  constructor(uint256 _subDepth, uint256 _hashLength) payable {
    /// validation
    if (_subDepth == 0) revert SubDepthCannotBeZero();
    if (_subDepth > MAX_DEPTH) revert SubdepthTooLarge(_subDepth, MAX_DEPTH);
    if (_hashLength != 2 && _hashLength != 5) revert InvalidHashLength();

    isBinary = _hashLength == 2;
    subDepth = _subDepth;
    hashLength = _hashLength;
    subTreeCapacity = _hashLength ** _subDepth;
  }

  /// @notice Hash the contents of the specified level and the specified leaf.
  /// This is a virtual function as the hash function which the overriding
  /// contract uses will be either hashLeftRight or hash5, which require
  /// different input array lengths.
  /// @param _level The level to hash.
  /// @param _leaf The leaf include with the level.
  /// @return _hash The hash of the level and leaf.
  // solhint-disable-next-line no-empty-blocks
  function hashLevel(uint256 _level, uint256 _leaf) internal virtual returns (uint256 _hash) {}

  /// @notice Hash the contents of the specified level and the specified leaf.
  /// This is a virtual function as the hash function which the overriding
  /// contract uses will be either hashLeftRight or hash5, which require
  /// different input array lengths.
  /// @param _level The level to hash.
  /// @param _leaf The leaf include with the level.
  /// @return _hash The hash of the level and leaf.
  // solhint-disable-next-line no-empty-blocks
  function hashLevelLeaf(uint256 _level, uint256 _leaf) public view virtual returns (uint256 _hash) {}

  /// @notice Returns the zero leaf at a specified level.
  /// This is a virtual function as the hash function which the overriding
  /// contract uses will be either hashLeftRight or hash5, which will produce
  /// different zero values (e.g. hashLeftRight(0, 0) vs
  /// hash5([0, 0, 0, 0, 0]). Moreover, the zero value may be a
  /// nothing-up-my-sleeve value.
  /// @param _level The level at which to return the zero leaf.
  /// @return zero The zero leaf at the specified level.
  // solhint-disable-next-line no-empty-blocks
  function getZero(uint256 _level) internal virtual returns (uint256 zero) {}

  /// @notice Add a leaf to the queue for the current subtree.
  /// @param _leaf The leaf to add.
  /// @return leafIndex The index of the leaf in the queue.
  function enqueue(uint256 _leaf) public onlyOwner returns (uint256 leafIndex) {
    leafIndex = numLeaves;
    // Recursively queue the leaf
    _enqueue(_leaf, 0);

    // Update the leaf counter
    numLeaves = leafIndex + 1;

    // Now that a new leaf has been added, mainRoots and smallSRTroot are
    // obsolete
    delete mainRoots;
    delete smallSRTroot;
    subTreesMerged = false;

    // If a subtree is full
    if (numLeaves % subTreeCapacity == 0) {
      // Store the subroot
      subRoots[currentSubtreeIndex] = leafQueue.levels[subDepth][0];

      // Increment the index
      currentSubtreeIndex++;

      // Delete ancillary data
      delete leafQueue.levels[subDepth][0];
      delete leafQueue.indices;
    }
  }

  /// @notice Updates the queue at a given level and hashes any subroots
  /// that need to be hashed.
  /// @param _leaf The leaf to add.
  /// @param _level The level at which to queue the leaf.
  function _enqueue(uint256 _leaf, uint256 _level) internal {
    if (_level > subDepth) {
      revert InvalidLevel();
    }

    while (true) {
      uint256 n = leafQueue.indices[_level];

      if (n != hashLength - 1) {
        // Just store the leaf
        leafQueue.levels[_level][n] = _leaf;

        if (_level != subDepth) {
          // Update the index
          leafQueue.indices[_level]++;
        }

        return;
      }

      // Hash the leaves to next level
      _leaf = hashLevel(_level, _leaf);

      // Reset the index for this level
      delete leafQueue.indices[_level];

      // Queue the hash of the leaves into to the next level
      _level++;
    }
  }

  /// @notice Fill any empty leaves of the current subtree with zeros and store the
  /// resulting subroot.
  function fill() public onlyOwner {
    if (numLeaves % subTreeCapacity == 0) {
      // If the subtree is completely empty, then the subroot is a
      // precalculated zero value
      subRoots[currentSubtreeIndex] = getZero(subDepth);
    } else {
      // Otherwise, fill the rest of the subtree with zeros
      _fill(0);

      // Store the subroot
      subRoots[currentSubtreeIndex] = leafQueue.levels[subDepth][0];

      // Reset the subtree data
      delete leafQueue.levels;

      // Reset the merged roots
      delete mainRoots;
    }

    // Increment the subtree index
    uint256 curr = currentSubtreeIndex + 1;
    currentSubtreeIndex = curr;

    // Update the number of leaves
    numLeaves = curr * subTreeCapacity;

    // Reset the subroot tree root now that it is obsolete
    delete smallSRTroot;

    subTreesMerged = false;
  }

  /// @notice A function that queues zeros to the specified level, hashes,
  /// the level, and enqueues the hash to the next level.
  /// @param _level The level at which to queue zeros.
  // solhint-disable-next-line no-empty-blocks
  function _fill(uint256 _level) internal virtual {}

  /// Insert a subtree. Used for batch enqueues.
  function insertSubTree(uint256 _subRoot) public onlyOwner {
    subRoots[currentSubtreeIndex] = _subRoot;

    // Increment the subtree index
    currentSubtreeIndex++;

    // Update the number of leaves
    numLeaves += subTreeCapacity;

    // Reset the subroot tree root now that it is obsolete
    delete smallSRTroot;

    subTreesMerged = false;
  }

  /// @notice Calculate the lowest possible height of a tree with
  /// all the subroots merged together.
  /// @return depth The lowest possible height of a tree with all the
  function calcMinHeight() public view returns (uint256 depth) {
    depth = 1;
    while (true) {
      if (hashLength ** depth >= currentSubtreeIndex) {
        break;
      }
      depth++;
    }
  }

  /// @notice Merge all subtrees to form the shortest possible tree.
  /// This function can be called either once to merge all subtrees in a
  /// single transaction, or multiple times to do the same in multiple
  /// transactions.
  /// @param _numSrQueueOps The number of times this function will call
  ///                       queueSubRoot(), up to the maximum number of times
  ///                       necessary. If it is set to 0, it will call
  ///                       queueSubRoot() as many times as is necessary. Set
  ///                       this to a low number and call this function
  ///                       multiple times if there are many subroots to
  ///                       merge, or a single transaction could run out of
  ///                       gas.
  function mergeSubRoots(uint256 _numSrQueueOps) public onlyOwner {
    // This function can only be called once unless a new subtree is created
    if (subTreesMerged) revert SubTreesAlreadyMerged();

    // There must be subtrees to merge
    if (numLeaves == 0) revert NothingToMerge();

    // Fill any empty leaves in the current subtree with zeros only if the
    // current subtree is not full
    if (numLeaves % subTreeCapacity != 0) {
      fill();
    }

    // If there is only 1 subtree, use its root
    if (currentSubtreeIndex == 1) {
      smallSRTroot = getSubRoot(0);
      subTreesMerged = true;
      return;
    }

    uint256 depth = calcMinHeight();

    uint256 queueOpsPerformed = 0;
    for (uint256 i = nextSubRootIndex; i < currentSubtreeIndex; i++) {
      if (_numSrQueueOps != 0 && queueOpsPerformed == _numSrQueueOps) {
        // If the limit is not 0, stop if the limit has been reached
        return;
      }

      // Queue the next subroot
      queueSubRoot(getSubRoot(nextSubRootIndex), 0, depth);

      // Increment the next subroot counter
      nextSubRootIndex++;

      // Increment the ops counter
      queueOpsPerformed++;
    }

    // The height of the tree of subroots
    uint256 m = hashLength ** depth;

    // Queue zeroes to fill out the SRT
    if (nextSubRootIndex == currentSubtreeIndex) {
      uint256 z = getZero(subDepth);
      for (uint256 i = currentSubtreeIndex; i < m; i++) {
        queueSubRoot(z, 0, depth);
      }
    }

    // Store the smallest main root
    smallSRTroot = subRootQueue.levels[depth][0];
    subTreesMerged = true;
  }

  /// @notice Queues a subroot into the subroot tree.
  /// @param _leaf The value to queue.
  /// @param _level The level at which to queue _leaf.
  /// @param _maxDepth The depth of the tree.
  function queueSubRoot(uint256 _leaf, uint256 _level, uint256 _maxDepth) internal {
    if (_level > _maxDepth) {
      return;
    }

    uint256 n = subRootQueue.indices[_level];

    if (n != hashLength - 1) {
      // Just store the leaf
      subRootQueue.levels[_level][n] = _leaf;
      subRootQueue.indices[_level]++;
    } else {
      // Hash the elements in this level and queue it in the next level
      uint256 hashed;
      if (isBinary) {
        uint256[2] memory inputs;
        inputs[0] = subRootQueue.levels[_level][0];
        inputs[1] = _leaf;
        hashed = hash2(inputs);
      } else {
        uint256[5] memory inputs;
        for (uint8 i = 0; i < n; i++) {
          inputs[i] = subRootQueue.levels[_level][i];
        }
        inputs[n] = _leaf;
        hashed = hash5(inputs);
      }

      // TODO: change recursion to a while loop
      // Recurse
      delete subRootQueue.indices[_level];
      queueSubRoot(hashed, _level + 1, _maxDepth);
    }
  }

  /// @notice Merge all subtrees to form a main tree with a desired depth.
  /// @param _depth The depth of the main tree. It must fit all the leaves or
  ///               this function will revert.
  /// @return root The root of the main tree.
  function merge(uint256 _depth) public onlyOwner returns (uint256 root) {
    // The tree depth must be more than 0
    if (_depth == 0) revert DepthCannotBeZero();

    // Ensure that the subtrees have been merged
    if (!subTreesMerged) revert SubTreesNotMerged();

    // Check the depth
    if (_depth > MAX_DEPTH) revert DepthTooLarge(_depth, MAX_DEPTH);

    // Calculate the SRT depth
    uint256 srtDepth = subDepth;
    while (true) {
      if (hashLength ** srtDepth >= numLeaves) {
        break;
      }
      srtDepth++;
    }

    if (_depth < srtDepth) revert DepthTooSmall(_depth, srtDepth);

    // If the depth is the same as the SRT depth, just use the SRT root
    if (_depth == srtDepth) {
      mainRoots[_depth] = smallSRTroot;
      treeMerged = true;
      return smallSRTroot;
    } else {
      root = smallSRTroot;

      // Calculate the main root

      for (uint256 i = srtDepth; i < _depth; i++) {
        uint256 z = getZero(i);

        if (isBinary) {
          uint256[2] memory inputs;
          inputs[0] = root;
          inputs[1] = z;
          root = hash2(inputs);
        } else {
          uint256[5] memory inputs;
          inputs[0] = root;
          inputs[1] = z;
          inputs[2] = z;
          inputs[3] = z;
          inputs[4] = z;
          root = hash5(inputs);
        }
      }

      mainRoots[_depth] = root;
      treeMerged = true;
    }
  }

  /// @notice Returns the subroot at the specified index. Reverts if the index refers
  /// to a subtree which has not been filled yet.
  /// @param _index The subroot index.
  /// @return subRoot The subroot at the specified index.
  function getSubRoot(uint256 _index) public view returns (uint256 subRoot) {
    if (currentSubtreeIndex <= _index) revert InvalidIndex(_index);
    subRoot = subRoots[_index];
  }

  /// @notice Returns the subroot tree (SRT) root. Its value must first be computed
  /// using mergeSubRoots.
  /// @return smallSubTreeRoot The SRT root.
  function getSmallSRTroot() public view returns (uint256 smallSubTreeRoot) {
    if (!subTreesMerged) revert SubTreesNotMerged();
    smallSubTreeRoot = smallSRTroot;
  }

  /// @notice Return the merged Merkle root of all the leaves at a desired depth.
  /// @dev merge() or merged(_depth) must be called first.
  /// @param _depth The depth of the main tree. It must first be computed
  ///               using mergeSubRoots() and merge().
  /// @return mainRoot The root of the main tree.
  function getMainRoot(uint256 _depth) public view returns (uint256 mainRoot) {
    if (hashLength ** _depth < numLeaves) revert DepthTooSmall(_depth, numLeaves);

    mainRoot = mainRoots[_depth];
  }

  /// @notice Get the next subroot index and the current subtree index.
  function getSrIndices() public view returns (uint256 next, uint256 current) {
    next = nextSubRootIndex;
    current = currentSubtreeIndex;
  }
}

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

import { AccQueue } from "./AccQueue.sol";

/// @title AccQueueQuinary
/// @notice This contract defines a Merkle tree where each leaf insertion only updates a
/// subtree. To obtain the main tree root, the contract owner must merge the
/// subtrees together. Merging subtrees requires at least 2 operations:
/// mergeSubRoots(), and merge(). To get around the gas limit,
/// the mergeSubRoots() can be performed in multiple transactions.
/// @dev This contract is for a quinary tree (5 leaves per node)
abstract contract AccQueueQuinary is AccQueue {
  /// @notice Create a new AccQueueQuinary instance
  constructor(uint256 _subDepth) AccQueue(_subDepth, 5) {}

  /// @notice Hash the contents of the specified level and the specified leaf.
  /// @dev it also frees up storage slots to refund gas.
  /// @param _level The level to hash.
  /// @param _leaf The leaf include with the level.
  /// @return hashed The hash of the level and leaf.
  function hashLevel(uint256 _level, uint256 _leaf) internal override returns (uint256 hashed) {
    uint256[5] memory inputs;
    inputs[0] = leafQueue.levels[_level][0];
    inputs[1] = leafQueue.levels[_level][1];
    inputs[2] = leafQueue.levels[_level][2];
    inputs[3] = leafQueue.levels[_level][3];
    inputs[4] = _leaf;
    hashed = hash5(inputs);

    // Free up storage slots to refund gas. Note that using a loop here
    // would result in lower gas savings.
    delete leafQueue.levels[_level];
  }

  /// @notice Hash the contents of the specified level and the specified leaf.
  /// @param _level The level to hash.
  /// @param _leaf The leaf include with the level.
  /// @return hashed The hash of the level and leaf.
  function hashLevelLeaf(uint256 _level, uint256 _leaf) public view override returns (uint256 hashed) {
    uint256[5] memory inputs;
    inputs[0] = leafQueue.levels[_level][0];
    inputs[1] = leafQueue.levels[_level][1];
    inputs[2] = leafQueue.levels[_level][2];
    inputs[3] = leafQueue.levels[_level][3];
    inputs[4] = _leaf;
    hashed = hash5(inputs);
  }

  /// @notice An internal function which fills a subtree
  /// @param _level The level at which to fill the subtree
  function _fill(uint256 _level) internal override {
    while (_level < subDepth) {
      uint256 n = leafQueue.indices[_level];

      if (n != 0) {
        // Fill the subtree level with zeros and hash the level
        uint256 hashed;

        uint256[5] memory inputs;
        uint256 z = getZero(_level);
        uint8 i = 0;
        for (; i < n; i++) {
          inputs[i] = leafQueue.levels[_level][i];
        }

        for (; i < hashLength; i++) {
          inputs[i] = z;
        }
        hashed = hash5(inputs);

        // Update the subtree from the next level onwards with the new leaf
        _enqueue(hashed, _level + 1);
      }

      // Reset the current level
      delete leafQueue.indices[_level];

      _level++;
    }
  }
}

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

abstract contract MerkleZeros {
  uint256[33] internal zeros;

  // Quinary tree zeros (Keccak hash of 'Maci')
  constructor() {
    zeros[0] = uint256(8370432830353022751713833565135785980866757267633941821328460903436894336785);
    zeros[1] = uint256(12915444503621073454579416579430905206970714557680052030066757042249102605307);
    zeros[2] = uint256(15825388848727206932541662858173052318786639683743459477657913288690190505308);
    zeros[3] = uint256(20672917177817295069558894035958266756825295443848082659014905185716743537191);
    zeros[4] = uint256(448586013948167251740855715259393055429962470693972912240018559200278204556);
    zeros[5] = uint256(3228865992178886480410396198366133115832717015233640381802715479176981303177);
    zeros[6] = uint256(19116532419590876304532847271428641103751206695152259493043279205958851263600);
    zeros[7] = uint256(13531983203936271379763604150672239370281863210813769735936250692178889682484);
    zeros[8] = uint256(8276490051100115441938424474671329955897359239518198952109759468777824929104);
    zeros[9] = uint256(1234816188709792521426066175633785051600533236493067959807265450339481920006);
    zeros[10] = uint256(14253963034950198848796956783804665963745244419038717333683296599064556174281);
    zeros[11] = uint256(6367560368479067766970398112009211893636892126125767203198799843543931913172);
    zeros[12] = uint256(9086778412328290069463938062555298073857321633960448227011862356090607842391);
    zeros[13] = uint256(1440983698234119608650157588008070947531139377294971527360643096251396484622);
    zeros[14] = uint256(3957599085599383799297196095384587366602816424699353871878382158004571037876);
    zeros[15] = uint256(2874250189355749385170216620368454832544508482778847425177457138604069991955);
    zeros[16] = uint256(21009179226085449764156117702096359546848859855915028677582017987249294772778);
    zeros[17] = uint256(11639371146919469643603772238908032714588430905217730187804009793768292270213);
    zeros[18] = uint256(6279313411277883478350325643881386249374023631847602720184182017599127173896);
    zeros[19] = uint256(21059196126634383551994255775761712285020874549906884292741523421591865338509);
    zeros[20] = uint256(9444544622817172574621750245792527383369133221167610044960147559319164808325);
    zeros[21] = uint256(5374570219497355452080912323548395721574511162814862844226178635172695078543);
    zeros[22] = uint256(4155904241440251764630449308160227499466701168124519106689866311729092343061);
    zeros[23] = uint256(15881609944326576145786405158479503217901875433072026818450276983706463215155);
    zeros[24] = uint256(20831546672064137588434602157208687297579005252478070660473540633558666587287);
    zeros[25] = uint256(3209071488384365842993449718919243416332014108747571544339190291353564426179);
    zeros[26] = uint256(10030934989297780221224272248227257782450689603145083016739151821673604746295);
    zeros[27] = uint256(16504852316033851373501270056537918974469380446508638487151124538300880427080);
    zeros[28] = uint256(5226137093551352657015038416264755428944140743893702595442932837011856178457);
    zeros[29] = uint256(18779994066356991319291039019820482828679702085087990978933303018673869446075);
    zeros[30] = uint256(12037506572124351893114409509086276299115869080424687624451184925646292710978);
    zeros[31] = uint256(12049750997011422639258622747494178076018128204515149991024639355149614767606);
    zeros[32] = uint256(3171463916443906096008599541392648187002297410622977814790586531203175805057);
  }
}

{
  "optimizer": {
    "enabled": true,
    "runs": 200
  },
  "evmVersion": "paris",
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "libraries": {
    "contracts/crypto/PoseidonT3.sol": {
      "PoseidonT3": "0x88c2c6a7535463962a34757fe63cc4f296381aba"
    },
    "contracts/crypto/PoseidonT4.sol": {
      "PoseidonT4": "0xf8e637e5c9ec3a8d8fa8843a6df833348e1f1e66"
    },
    "contracts/crypto/PoseidonT5.sol": {
      "PoseidonT5": "0x0a0d66bafda8c8838281084d9c3d68dd9a6fc274"
    },
    "contracts/crypto/PoseidonT6.sol": {
      "PoseidonT6": "0xd2f6c828606ad8e985008cd825012f269b50cd58"
    }
  }
}

[{"inputs":[{"internalType":"uint256","name":"_subDepth","type":"uint256"}],"stateMutability":"nonpayable","type":"constructor"},{"inputs":[],"name":"DepthCannotBeZero","type":"error"},{"inputs":[{"internalType":"uint256","name":"_depth","type":"uint256"},{"internalType":"uint256","name":"max","type":"uint256"}],"name":"DepthTooLarge","type":"error"},{"inputs":[{"internalType":"uint256","name":"_depth","type":"uint256"},{"internalType":"uint256","name":"min","type":"uint256"}],"name":"DepthTooSmall","type":"error"},{"inputs":[],"name":"InvalidHashLength","type":"error"},{"inputs":[{"internalType":"uint256","name":"_index","type":"uint256"}],"name":"InvalidIndex","type":"error"},{"inputs":[],"name":"InvalidLevel","type":"error"},{"inputs":[],"name":"NothingToMerge","type":"error"},{"inputs":[{"internalType":"address","name":"owner","type":"address"}],"name":"OwnableInvalidOwner","type":"error"},{"inputs":[{"internalType":"address","name":"account","type":"address"}],"name":"OwnableUnauthorizedAccount","type":"error"},{"inputs":[],"name":"SubDepthCannotBeZero","type":"error"},{"inputs":[],"name":"SubTreesAlreadyMerged","type":"error"},{"inputs":[],"name":"SubTreesNotMerged","type":"error"},{"inputs":[{"internalType":"uint256","name":"_subDepth","type":"uint256"},{"internalType":"uint256","name":"max","type":"uint256"}],"name":"SubdepthTooLarge","type":"error"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"address","name":"previousOwner","type":"address"},{"indexed":true,"internalType":"address","name":"newOwner","type":"address"}],"name":"OwnershipTransferred","type":"event"},{"inputs":[],"name":"MAX_DEPTH","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"calcMinHeight","outputs":[{"internalType":"uint256","name":"depth","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256","name":"_leaf","type":"uint256"}],"name":"enqueue","outputs":[{"internalType":"uint256","name":"leafIndex","type":"uint256"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"fill","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256","name":"_depth","type":"uint256"}],"name":"getMainRoot","outputs":[{"internalType":"uint256","name":"mainRoot","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"getSmallSRTroot","outputs":[{"internalType":"uint256","name":"smallSubTreeRoot","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"getSrIndices","outputs":[{"internalType":"uint256","name":"next","type":"uint256"},{"internalType":"uint256","name":"current","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256","name":"_index","type":"uint256"}],"name":"getSubRoot","outputs":[{"internalType":"uint256","name":"subRoot","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256[2]","name":"array","type":"uint256[2]"}],"name":"hash2","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256[3]","name":"array","type":"uint256[3]"}],"name":"hash3","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256[4]","name":"array","type":"uint256[4]"}],"name":"hash4","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256[5]","name":"array","type":"uint256[5]"}],"name":"hash5","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256","name":"left","type":"uint256"},{"internalType":"uint256","name":"right","type":"uint256"}],"name":"hashLeftRight","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256","name":"_level","type":"uint256"},{"internalType":"uint256","name":"_leaf","type":"uint256"}],"name":"hashLevelLeaf","outputs":[{"internalType":"uint256","name":"hashed","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256","name":"_subRoot","type":"uint256"}],"name":"insertSubTree","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256","name":"_depth","type":"uint256"}],"name":"merge","outputs":[{"internalType":"uint256","name":"root","type":"uint256"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256","name":"_numSrQueueOps","type":"uint256"}],"name":"mergeSubRoots","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"numLeaves","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"owner","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"renounceOwnership","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256[]","name":"array","type":"uint256[]"}],"name":"sha256Hash","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[],"name":"subTreesMerged","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"newOwner","type":"address"}],"name":"transferOwnership","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"treeMerged","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"}]

0x60e06040523480156200001157600080fd5b50604051620022dc380380620022dc83398101604081905262000034916200063d565b8080600533806200006057604051631e4fbdf760e01b8152600060048201526024015b60405180910390fd5b6200006b81620005ed565b50816000036200008e5760405163682e504160e11b815260040160405180910390fd5b6020821115620000bc57604051637ccdcc9760e11b8152600481018390526020602482015260440162000057565b80600214158015620000cf575080600514155b15620000ee57604051636f7b6c0360e01b815260040160405180910390fd5b6000805460ff60a01b191660028314600160a01b02179055608082905260a08190526200011c82826200076c565b60c05250507f12817f4161f2f5ded33f26c55735a77e80e4f8975483c8c2704745128417f7116101725550507f1c8de1edeabc24fc4c1595acaabb70be9b70f351d58c6fa338e1e9a994413bfb610173557f22fcda488c14b34fc60eb073fbe92fe10793e2ab14682e0f057332ddbef3d55c610174557f2db474db7c7212646cb15c6177d87be30711e6c04f1139d8e495ef1d1d998227610175557efde404053ec39a19f6ac347121a2264815dda84f910a388cb372e967a5d08c610176557f0723792ffab6ec6cfb3ece1509b9b4fb07e5bdb2299d1538e6e1db916f90cf89610177557f2a4392ec4e3d1811cd6a950cc865ee6f2342910a6551c5dce38cb995576c7c70610178557f1dead4c14f75e9d8449c80b648dcd4694c2ee50da2ba16e5e438f0d77ab02e34610179557f124c53ce0953fffb7ab5e3c143df6cd48ba747d3959fcb8086405d763ed5455061017a557f02bae19605746a8cd3f0927b2c01630f36f4d1bab9216ca839833e7ff6efa20661017b557f1f8375099becf17173d457d0d07bfb74c7067df1143b5ad987046e8e66817bc961017c557f0e13e954d61bb3fa3b03e7d136ca909b610fa2ca4443d920d94d16684f2b83d461017d557f1416ef2fc4f88fcfc4f9eb12f8e214b1c3e31c6c10ece9cfa51f078a3bbf345761017e557f032f915ff71e198a7955d2697249f40fb94c65812ed24e670c9700f52fdf6e0e61017f557f08bfebf4b3ddb0f8c51dd40193f5996da9f3d799ee0d8beb6be4038132df60b4610180557f065ac498cf4a5acaeb3b6cee826da9f834c961fa39feff6ae925b90dff79b613610181557f2e72c628101a93201b912a3e3fe96d39b0a9076ec39b7935a015c59bb32b8a2a610182557f19bba68e7b9da1e6ec42e52d7ab2adaf3b6a5521b1a454ec70f62e0ab702c085610183557f0de1f72745a5af2a34cac412e00eb6c8b5db1f3b52fa1bff88076c2726b83b08610184557f2e8f152603b2fac10d6a14c841327c23c502537367ccb1e42fab9a3bd9db2a8d610185557f14e16c3e0dcfd7e621a32627ebf37f6c0afb4467d34c7b7aeffded11769dec85610186557f0be1e62127948b4805c85a1d836574f0892ca6473fcde98f3fd1781248a9768f610187557f0930288fbd7c849197c8372f1dd8f9087f8a03f09b9cd904a469c15ef6b1b515610188557f231cac34e215e3f404d2fcfb79e0705deeb3d40978f0ee31072f6cbc1b579e33610189557f2e0e3cd2718ac7199b81dc14e841de40a9536b7ffe95fa1fc9c6b799e43e2c9761018a557f0718452506f0a232e98966d84b1a4675a66bd80263a2dc58bdac873825752fc361018b557f162d4ed998307d6e132edbf5c11f62f53d4636aa10cb3c2244c2bf5577168c3761018c557f247d6a5544a8f295a894ae77c7efcdcbf52e3bf4e5d0c0d2f40557a61d44984861018d557f0b8de3868471f109e91670daca698dba917d1c5535821f33aa9598d1db8e3d1961018e557f29851997020f527c92e20f030d232b81d334144a641e6a8866b46dd925005bbb61018f557f1a9cfcbe29a2b6503a03049727c0bca3111afd62f2836f392080321d1b4ef642610190557f1aa3ead91fa89cc1d6cb1d0eb76a27190c6abfdd3265d6d0a1e5c58feddaddf6610191557f0702fc26a7d367e6677efefd95204a7e00144c2fc7dbc2a581aa00d99f51f0816101925562000781565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b6000602082840312156200065057600080fd5b5051919050565b634e487b7160e01b600052601160045260246000fd5b600181815b80851115620006ae57816000190482111562000692576200069262000657565b80851615620006a057918102915b93841c939080029062000672565b509250929050565b600082620006c75750600162000766565b81620006d65750600062000766565b8160018114620006ef5760028114620006fa576200071a565b600191505062000766565b60ff8411156200070e576200070e62000657565b50506001821b62000766565b5060208310610133831016604e8410600b84101617156200073f575081810a62000766565b6200074b83836200066d565b806000190482111562000762576200076262000657565b0290505b92915050565b60006200077a8383620006b6565b9392505050565b60805160a05160c051611aad6200082f600039600081816103ea01528181610a2501528181610ac201528181610c7f0152610d820152600081816103230152818161056e015281816106e401528181610bb401528181610ec301528181611037015261129801526000818161041a0152818161047b0152818161054401528181610bed01528181610cb801528181610d0201528181610e6401528181610f1a01526111d30152611aad6000f3fe608060405234801561001057600080fd5b50600436106101585760003560e01c806381d6a24a116100c3578063c00bdbcc1161007c578063c00bdbcc146102b8578063c15da65b146102cb578063d9c55ce1146102de578063dda89a6e146102e6578063e93fb4d4146102f0578063f2fde38b1461030357600080fd5b806381d6a24a146102455780638da5cb5b146102615780639cfced971461027c578063a27154ba1461028f578063b6a64acd14610297578063bea140b3146102a557600080fd5b806358bfc3791161011557806358bfc379146101cc5780635bb93995146101df5780635bf1fa4d146101f257806362a361bb1461020557806369e7c58614610218578063715018a61461023b57600080fd5b80631b9b8aa71461015d5780631ffc735d1461018357806324a47aeb146101965780633bfa6fce146101a95780633dfb88b2146101b15780633e1a8cc1146101c4575b600080fd5b61017061016b3660046114ba565b610316565b6040519081526020015b60405180910390f35b6101706101913660046114ba565b610399565b6101706101a43660046114ba565b6104c7565b6101706106d8565b6101706101bf36600461151a565b610723565b6101706107a4565b6101706101da366004611598565b6107d3565b6101706101ed36600461163e565b61086d565b61017061020036600461163e565b610892565b610170610213366004611660565b610931565b61016e5461022b90610100900460ff1681565b604051901515815260200161017a565b61024361096b565b005b610170546001546040805192835260208301919091520161017a565b6000546040516001600160a01b03909116815260200161017a565b61017061028a3660046116bb565b61097f565b610170602081565b61016e5461022b9060ff1681565b6101706102b3366004611714565b6109b9565b6102436102c63660046114ba565b6109f3565b6102436102d93660046114ba565b610a6f565b610243610c75565b6101706101715481565b6101706102fe3660046114ba565b610dbf565b61024361031136600461176d565b610dfa565b61017154600090610347837f0000000000000000000000000000000000000000000000000000000000000000611897565b101561037d5761017154604051627289df60e61b8152610374918491600401918252602082015260400190565b60405180910390fd5b61014d8260218110610391576103916118a3565b015492915050565b60006103a3610e35565b50610171546103b3826000610e62565b6103be8160016118b9565b610171556103cf61014d600061141f565b600061016f5561016e805460ff191690556101715461040f907f0000000000000000000000000000000000000000000000000000000000000000906118cc565b6000036104c25760027f000000000000000000000000000000000000000000000000000000000000000060218110610449576104496118a3565b600402015460018054600090815261014c6020526040812092909255805491610471836118ee565b90915550600290507f0000000000000000000000000000000000000000000000000000000000000000602181106104aa576104aa6118a3565b6004020160008091018190556104c29060869061141f565b919050565b60006104d1610e35565b816000036104f257604051630543d40760e11b815260040160405180910390fd5b61016e5460ff1661051657604051631e596e4360e11b815260040160405180910390fd5b602082111561054257604051632cd31ae960e01b81526004810183905260206024820152604401610374565b7f00000000000000000000000000000000000000000000000000000000000000005b61017154610592827f0000000000000000000000000000000000000000000000000000000000000000611897565b10156105aa57806105a2816118ee565b915050610564565b808310156105d457604051627289df60e61b81526004810184905260248101829052604401610374565b8083036106105761016f5461014d84602181106105f3576105f36118a3565b0155505061016e805461ff00191661010017905561016f54919050565b61016f549150805b838110156106aa57600061062b82610fa3565b600054909150600160a01b900460ff16156106635761064861142e565b8481526020810182905261065b81610931565b945050610697565b61066b61144c565b848152602081018290526040810182905260608101829052608081018290526106938161097f565b9450505b50806106a2816118ee565b915050610618565b508161014d84602181106106c0576106c06118a3565b015561016e805461ff00191661010017905550919050565b60015b600154610708827f0000000000000000000000000000000000000000000000000000000000000000611897565b10156107205780610718816118ee565b9150506106db565b90565b60405163248f667760e01b8152600090730a0d66bafda8c8838281084d9c3d68dd9a6fc2749063248f66779061075d908590600401611907565b602060405180830381865af415801561077a573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061079e9190611938565b92915050565b61016e5460009060ff166107cb57604051631e596e4360e11b815260040160405180910390fd5b5061016f5490565b60007f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f00000016002836040516020016108099190611951565b60408051601f198184030181529082905261082391611987565b602060405180830381855afa158015610840573d6000803e3d6000fd5b5050506040513d601f19601f820116820180604052508101906108639190611938565b61079e91906118cc565b600061087761142e565b8381526020810183905261088a81610931565b949350505050565b600061089c61144c565b600284602181106108af576108af6118a3565b60040201548152600284602181106108c9576108c96118a3565b60040201600101548160016020020152600284602181106108ec576108ec6118a3565b600402016002015481600260200201526002846021811061090f5761090f6118a3565b6004020160030154816003602002015282816004602002015261088a8161097f565b6040516314d2f97b60e11b81526000907388c2c6a7535463962a34757fe63cc4f296381aba906329a5f2f69061075d9085906004016119b6565b610973610e35565b61097d6000610fb9565b565b604051630926f44b60e31b815260009073d2f6c828606ad8e985008cd825012f269b50cd5890634937a2589061075d9085906004016119de565b6040516304b98e1d60e31b815260009073f8e637e5c9ec3a8d8fa8843a6df833348e1f1e66906325cc70e89061075d908590600401611a06565b6109fb610e35565b60018054600090815261014c6020526040812083905581549190610a1e836118ee565b91905055507f00000000000000000000000000000000000000000000000000000000000000006101716000828254610a5691906118b9565b9091555050600061016f555061016e805460ff19169055565b610a77610e35565b61016e5460ff1615610a9c57604051630d36aec160e01b815260040160405180910390fd5b61017154600003610ac0576040516316a0341160e11b815260040160405180910390fd5b7f000000000000000000000000000000000000000000000000000000000000000061017154610aef91906118cc565b15610afc57610afc610c75565b600154600103610b2557610b106000610dbf565b61016f5561016e805460ff1916600117905550565b6000610b2f6106d8565b610170549091506000905b600154811015610bab578315801590610b5257508382145b15610b5d5750505050565b610b74610b6c61017054610dbf565b600085611009565b6101708054906000610b85836118ee565b91905055508180610b95906118ee565b9250508080610ba3906118ee565b915050610b3a565b506000610bd8837f0000000000000000000000000000000000000000000000000000000000000000611897565b90506001546101705403610c41576000610c117f0000000000000000000000000000000000000000000000000000000000000000610fa3565b6001549091505b82811015610c3e57610c2c82600087611009565b80610c36816118ee565b915050610c18565b50505b60a78360218110610c5457610c546118a3565b600402016000015461016f55505061016e805460ff19166001179055505b50565b610c7d610e35565b7f000000000000000000000000000000000000000000000000000000000000000061017154610cac91906118cc565b600003610cf457610cdc7f0000000000000000000000000000000000000000000000000000000000000000610fa3565b600154600090815261014c6020526040902055610d65565b610cfe60006111d1565b60027f000000000000000000000000000000000000000000000000000000000000000060218110610d3157610d316118a3565b6004020154600154600090815261014c6020526040812091909155610d589060029061146a565b610d6561014d600061141f565b60006001546001610d7691906118b9565b60018190559050610da77f000000000000000000000000000000000000000000000000000000000000000082611a2e565b6101715550600061016f5561016e805460ff19169055565b60008160015411610de65760405163042a2e7160e11b815260048101839052602401610374565b50600090815261014c602052604090205490565b610e02610e35565b6001600160a01b038116610e2c57604051631e4fbdf760e01b815260006004820152602401610374565b610c7281610fb9565b6000546001600160a01b0316331461097d5760405163118cdaa760e01b8152336004820152602401610374565b7f0000000000000000000000000000000000000000000000000000000000000000811115610ea35760405163d1459f7960e01b815260040160405180910390fd5b600060868260218110610eb857610eb86118a3565b01549050610ee760017f0000000000000000000000000000000000000000000000000000000000000000611a45565b8114610f6c578260028360218110610f0157610f016118a3565b600402018260048110610f1657610f166118a3565b01557f00000000000000000000000000000000000000000000000000000000000000008214610f675760868260218110610f5257610f526118a3565b018054906000610f61836118ee565b91905055505b505050565b610f76828461133d565b925060868260218110610f8b57610f8b6118a3565b600091015581610f9a816118ee565b92505050610ea3565b60006101728260218110610391576103916118a3565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b8082111561101657505050565b600061012b836021811061102c5761102c6118a3565b0154905061105b60017f0000000000000000000000000000000000000000000000000000000000000000611a45565b81146110b9578360a78460218110611075576110756118a3565b60040201826004811061108a5761108a6118a3565b015561012b83602181106110a0576110a06118a3565b0180549060006110af836118ee565b91905055506111cb565b60008054600160a01b900460ff1615611106576110d461142e565b60a785602181106110e7576110e76118a3565b60040201548152602081018690526110fe81610931565b91505061119b565b61110e61144c565b60005b838160ff1610156111755760a7866021811061112f5761112f6118a3565b600402018160ff1660048110611147576111476118a3565b0154828260ff166005811061115e5761115e6118a3565b60200201528061116d81611a58565b915050611111565b5085818460058110611189576111896118a3565b60200201526111978161097f565b9150505b61012b84602181106111af576111af6118a3565b60009101556111c9816111c38660016118b9565b85611009565b505b50505050565b7f0000000000000000000000000000000000000000000000000000000000000000811015610c725760006086826021811061120e5761120e6118a3565b01549050801561131257600061122261144c565b600061122d85610fa3565b905060005b848160ff1610156112965760028660218110611250576112506118a3565b600402018160ff1660048110611268576112686118a3565b0154838260ff166005811061127f5761127f6118a3565b60200201528061128e81611a58565b915050611232565b7f00000000000000000000000000000000000000000000000000000000000000008160ff1610156112ee5781838260ff16600581106112d7576112d76118a3565b6020020152806112e681611a58565b915050611296565b6112f78361097f565b935061130d846113088860016118b9565b610e62565b505050505b60868260218110611325576113256118a3565b600091015581611334816118ee565b925050506111d1565b600061134761144c565b6002846021811061135a5761135a6118a3565b6004020154815260028460218110611374576113746118a3565b6004020160010154816001602002015260028460218110611397576113976118a3565b60040201600201548160026020020152600284602181106113ba576113ba6118a3565b600402016003015481600360200201528281600460200201526113dc8161097f565b9150600284602181106113f1576113f16118a3565b60040201600061141891905060008155600101600081556001016000815560010160009055565b5092915050565b50610c72906021810190611479565b60405180604001604052806002906020820280368337509192915050565b6040518060a001604052806005906020820280368337509192915050565b50610c72906084810190611492565b5b8082111561148e576000815560010161147a565b5090565b8082111561148e57600080825560018201819055600282018190556003820155600401611492565b6000602082840312156114cc57600080fd5b5035919050565b634e487b7160e01b600052604160045260246000fd5b604051601f8201601f1916810167ffffffffffffffff81118282101715611512576115126114d3565b604052919050565b60006080828403121561152c57600080fd5b82601f83011261153b57600080fd5b6040516080810181811067ffffffffffffffff8211171561155e5761155e6114d3565b60405280608084018581111561157357600080fd5b845b8181101561158d578035835260209283019201611575565b509195945050505050565b600060208083850312156115ab57600080fd5b823567ffffffffffffffff808211156115c357600080fd5b818501915085601f8301126115d757600080fd5b8135818111156115e9576115e96114d3565b8060051b91506115fa8483016114e9565b818152918301840191848101908884111561161457600080fd5b938501935b8385101561163257843582529385019390850190611619565b98975050505050505050565b6000806040838503121561165157600080fd5b50508035926020909101359150565b60006040828403121561167257600080fd5b82601f83011261168157600080fd5b6040516040810181811067ffffffffffffffff821117156116a4576116a46114d3565b806040525080604084018581111561157357600080fd5b600060a082840312156116cd57600080fd5b82601f8301126116dc57600080fd5b60405160a0810181811067ffffffffffffffff821117156116ff576116ff6114d3565b6040528060a084018581111561157357600080fd5b60006060828403121561172657600080fd5b82601f83011261173557600080fd5b6040516060810181811067ffffffffffffffff82111715611758576117586114d3565b60405280606084018581111561157357600080fd5b60006020828403121561177f57600080fd5b81356001600160a01b038116811461179657600080fd5b9392505050565b634e487b7160e01b600052601160045260246000fd5b600181815b808511156117ee5781600019048211156117d4576117d461179d565b808516156117e157918102915b93841c93908002906117b8565b509250929050565b6000826118055750600161079e565b816118125750600061079e565b816001811461182857600281146118325761184e565b600191505061079e565b60ff8411156118435761184361179d565b50506001821b61079e565b5060208310610133831016604e8410600b8410161715611871575081810a61079e565b61187b83836117b3565b806000190482111561188f5761188f61179d565b029392505050565b600061179683836117f6565b634e487b7160e01b600052603260045260246000fd5b8082018082111561079e5761079e61179d565b6000826118e957634e487b7160e01b600052601260045260246000fd5b500690565b6000600182016119005761190061179d565b5060010190565b60808101818360005b600481101561192f578151835260209283019290910190600101611910565b50505092915050565b60006020828403121561194a57600080fd5b5051919050565b815160009082906020808601845b8381101561197b5781518552938201939082019060010161195f565b50929695505050505050565b6000825160005b818110156119a8576020818601810151858301520161198e565b506000920191825250919050565b60408101818360005b600281101561192f5781518352602092830192909101906001016119bf565b60a08101818360005b600581101561192f5781518352602092830192909101906001016119e7565b60608101818360005b600381101561192f578151835260209283019290910190600101611a0f565b808202811582820484141761079e5761079e61179d565b8181038181111561079e5761079e61179d565b600060ff821660ff8103611a6e57611a6e61179d565b6001019291505056fea2646970667358221220de48377ebab560ef190138d15ea2cd48ec74d706562bdc76aca8c6093ed43a8e64736f6c634300081400330000000000000000000000000000000000000000000000000000000000000001

0x608060405234801561001057600080fd5b50600436106101585760003560e01c806381d6a24a116100c3578063c00bdbcc1161007c578063c00bdbcc146102b8578063c15da65b146102cb578063d9c55ce1146102de578063dda89a6e146102e6578063e93fb4d4146102f0578063f2fde38b1461030357600080fd5b806381d6a24a146102455780638da5cb5b146102615780639cfced971461027c578063a27154ba1461028f578063b6a64acd14610297578063bea140b3146102a557600080fd5b806358bfc3791161011557806358bfc379146101cc5780635bb93995146101df5780635bf1fa4d146101f257806362a361bb1461020557806369e7c58614610218578063715018a61461023b57600080fd5b80631b9b8aa71461015d5780631ffc735d1461018357806324a47aeb146101965780633bfa6fce146101a95780633dfb88b2146101b15780633e1a8cc1146101c4575b600080fd5b61017061016b3660046114ba565b610316565b6040519081526020015b60405180910390f35b6101706101913660046114ba565b610399565b6101706101a43660046114ba565b6104c7565b6101706106d8565b6101706101bf36600461151a565b610723565b6101706107a4565b6101706101da366004611598565b6107d3565b6101706101ed36600461163e565b61086d565b61017061020036600461163e565b610892565b610170610213366004611660565b610931565b61016e5461022b90610100900460ff1681565b604051901515815260200161017a565b61024361096b565b005b610170546001546040805192835260208301919091520161017a565b6000546040516001600160a01b03909116815260200161017a565b61017061028a3660046116bb565b61097f565b610170602081565b61016e5461022b9060ff1681565b6101706102b3366004611714565b6109b9565b6102436102c63660046114ba565b6109f3565b6102436102d93660046114ba565b610a6f565b610243610c75565b6101706101715481565b6101706102fe3660046114ba565b610dbf565b61024361031136600461176d565b610dfa565b61017154600090610347837f0000000000000000000000000000000000000000000000000000000000000005611897565b101561037d5761017154604051627289df60e61b8152610374918491600401918252602082015260400190565b60405180910390fd5b61014d8260218110610391576103916118a3565b015492915050565b60006103a3610e35565b50610171546103b3826000610e62565b6103be8160016118b9565b610171556103cf61014d600061141f565b600061016f5561016e805460ff191690556101715461040f907f0000000000000000000000000000000000000000000000000000000000000005906118cc565b6000036104c25760027f000000000000000000000000000000000000000000000000000000000000000160218110610449576104496118a3565b600402015460018054600090815261014c6020526040812092909255805491610471836118ee565b90915550600290507f0000000000000000000000000000000000000000000000000000000000000001602181106104aa576104aa6118a3565b6004020160008091018190556104c29060869061141f565b919050565b60006104d1610e35565b816000036104f257604051630543d40760e11b815260040160405180910390fd5b61016e5460ff1661051657604051631e596e4360e11b815260040160405180910390fd5b602082111561054257604051632cd31ae960e01b81526004810183905260206024820152604401610374565b7f00000000000000000000000000000000000000000000000000000000000000015b61017154610592827f0000000000000000000000000000000000000000000000000000000000000005611897565b10156105aa57806105a2816118ee565b915050610564565b808310156105d457604051627289df60e61b81526004810184905260248101829052604401610374565b8083036106105761016f5461014d84602181106105f3576105f36118a3565b0155505061016e805461ff00191661010017905561016f54919050565b61016f549150805b838110156106aa57600061062b82610fa3565b600054909150600160a01b900460ff16156106635761064861142e565b8481526020810182905261065b81610931565b945050610697565b61066b61144c565b848152602081018290526040810182905260608101829052608081018290526106938161097f565b9450505b50806106a2816118ee565b915050610618565b508161014d84602181106106c0576106c06118a3565b015561016e805461ff00191661010017905550919050565b60015b600154610708827f0000000000000000000000000000000000000000000000000000000000000005611897565b10156107205780610718816118ee565b9150506106db565b90565b60405163248f667760e01b8152600090730a0d66bafda8c8838281084d9c3d68dd9a6fc2749063248f66779061075d908590600401611907565b602060405180830381865af415801561077a573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061079e9190611938565b92915050565b61016e5460009060ff166107cb57604051631e596e4360e11b815260040160405180910390fd5b5061016f5490565b60007f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f00000016002836040516020016108099190611951565b60408051601f198184030181529082905261082391611987565b602060405180830381855afa158015610840573d6000803e3d6000fd5b5050506040513d601f19601f820116820180604052508101906108639190611938565b61079e91906118cc565b600061087761142e565b8381526020810183905261088a81610931565b949350505050565b600061089c61144c565b600284602181106108af576108af6118a3565b60040201548152600284602181106108c9576108c96118a3565b60040201600101548160016020020152600284602181106108ec576108ec6118a3565b600402016002015481600260200201526002846021811061090f5761090f6118a3565b6004020160030154816003602002015282816004602002015261088a8161097f565b6040516314d2f97b60e11b81526000907388c2c6a7535463962a34757fe63cc4f296381aba906329a5f2f69061075d9085906004016119b6565b610973610e35565b61097d6000610fb9565b565b604051630926f44b60e31b815260009073d2f6c828606ad8e985008cd825012f269b50cd5890634937a2589061075d9085906004016119de565b6040516304b98e1d60e31b815260009073f8e637e5c9ec3a8d8fa8843a6df833348e1f1e66906325cc70e89061075d908590600401611a06565b6109fb610e35565b60018054600090815261014c6020526040812083905581549190610a1e836118ee565b91905055507f00000000000000000000000000000000000000000000000000000000000000056101716000828254610a5691906118b9565b9091555050600061016f555061016e805460ff19169055565b610a77610e35565b61016e5460ff1615610a9c57604051630d36aec160e01b815260040160405180910390fd5b61017154600003610ac0576040516316a0341160e11b815260040160405180910390fd5b7f000000000000000000000000000000000000000000000000000000000000000561017154610aef91906118cc565b15610afc57610afc610c75565b600154600103610b2557610b106000610dbf565b61016f5561016e805460ff1916600117905550565b6000610b2f6106d8565b610170549091506000905b600154811015610bab578315801590610b5257508382145b15610b5d5750505050565b610b74610b6c61017054610dbf565b600085611009565b6101708054906000610b85836118ee565b91905055508180610b95906118ee565b9250508080610ba3906118ee565b915050610b3a565b506000610bd8837f0000000000000000000000000000000000000000000000000000000000000005611897565b90506001546101705403610c41576000610c117f0000000000000000000000000000000000000000000000000000000000000001610fa3565b6001549091505b82811015610c3e57610c2c82600087611009565b80610c36816118ee565b915050610c18565b50505b60a78360218110610c5457610c546118a3565b600402016000015461016f55505061016e805460ff19166001179055505b50565b610c7d610e35565b7f000000000000000000000000000000000000000000000000000000000000000561017154610cac91906118cc565b600003610cf457610cdc7f0000000000000000000000000000000000000000000000000000000000000001610fa3565b600154600090815261014c6020526040902055610d65565b610cfe60006111d1565b60027f000000000000000000000000000000000000000000000000000000000000000160218110610d3157610d316118a3565b6004020154600154600090815261014c6020526040812091909155610d589060029061146a565b610d6561014d600061141f565b60006001546001610d7691906118b9565b60018190559050610da77f000000000000000000000000000000000000000000000000000000000000000582611a2e565b6101715550600061016f5561016e805460ff19169055565b60008160015411610de65760405163042a2e7160e11b815260048101839052602401610374565b50600090815261014c602052604090205490565b610e02610e35565b6001600160a01b038116610e2c57604051631e4fbdf760e01b815260006004820152602401610374565b610c7281610fb9565b6000546001600160a01b0316331461097d5760405163118cdaa760e01b8152336004820152602401610374565b7f0000000000000000000000000000000000000000000000000000000000000001811115610ea35760405163d1459f7960e01b815260040160405180910390fd5b600060868260218110610eb857610eb86118a3565b01549050610ee760017f0000000000000000000000000000000000000000000000000000000000000005611a45565b8114610f6c578260028360218110610f0157610f016118a3565b600402018260048110610f1657610f166118a3565b01557f00000000000000000000000000000000000000000000000000000000000000018214610f675760868260218110610f5257610f526118a3565b018054906000610f61836118ee565b91905055505b505050565b610f76828461133d565b925060868260218110610f8b57610f8b6118a3565b600091015581610f9a816118ee565b92505050610ea3565b60006101728260218110610391576103916118a3565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b8082111561101657505050565b600061012b836021811061102c5761102c6118a3565b0154905061105b60017f0000000000000000000000000000000000000000000000000000000000000005611a45565b81146110b9578360a78460218110611075576110756118a3565b60040201826004811061108a5761108a6118a3565b015561012b83602181106110a0576110a06118a3565b0180549060006110af836118ee565b91905055506111cb565b60008054600160a01b900460ff1615611106576110d461142e565b60a785602181106110e7576110e76118a3565b60040201548152602081018690526110fe81610931565b91505061119b565b61110e61144c565b60005b838160ff1610156111755760a7866021811061112f5761112f6118a3565b600402018160ff1660048110611147576111476118a3565b0154828260ff166005811061115e5761115e6118a3565b60200201528061116d81611a58565b915050611111565b5085818460058110611189576111896118a3565b60200201526111978161097f565b9150505b61012b84602181106111af576111af6118a3565b60009101556111c9816111c38660016118b9565b85611009565b505b50505050565b7f0000000000000000000000000000000000000000000000000000000000000001811015610c725760006086826021811061120e5761120e6118a3565b01549050801561131257600061122261144c565b600061122d85610fa3565b905060005b848160ff1610156112965760028660218110611250576112506118a3565b600402018160ff1660048110611268576112686118a3565b0154838260ff166005811061127f5761127f6118a3565b60200201528061128e81611a58565b915050611232565b7f00000000000000000000000000000000000000000000000000000000000000058160ff1610156112ee5781838260ff16600581106112d7576112d76118a3565b6020020152806112e681611a58565b915050611296565b6112f78361097f565b935061130d846113088860016118b9565b610e62565b505050505b60868260218110611325576113256118a3565b600091015581611334816118ee565b925050506111d1565b600061134761144c565b6002846021811061135a5761135a6118a3565b6004020154815260028460218110611374576113746118a3565b6004020160010154816001602002015260028460218110611397576113976118a3565b60040201600201548160026020020152600284602181106113ba576113ba6118a3565b600402016003015481600360200201528281600460200201526113dc8161097f565b9150600284602181106113f1576113f16118a3565b60040201600061141891905060008155600101600081556001016000815560010160009055565b5092915050565b50610c72906021810190611479565b60405180604001604052806002906020820280368337509192915050565b6040518060a001604052806005906020820280368337509192915050565b50610c72906084810190611492565b5b8082111561148e576000815560010161147a565b5090565b8082111561148e57600080825560018201819055600282018190556003820155600401611492565b6000602082840312156114cc57600080fd5b5035919050565b634e487b7160e01b600052604160045260246000fd5b604051601f8201601f1916810167ffffffffffffffff81118282101715611512576115126114d3565b604052919050565b60006080828403121561152c57600080fd5b82601f83011261153b57600080fd5b6040516080810181811067ffffffffffffffff8211171561155e5761155e6114d3565b60405280608084018581111561157357600080fd5b845b8181101561158d578035835260209283019201611575565b509195945050505050565b600060208083850312156115ab57600080fd5b823567ffffffffffffffff808211156115c357600080fd5b818501915085601f8301126115d757600080fd5b8135818111156115e9576115e96114d3565b8060051b91506115fa8483016114e9565b818152918301840191848101908884111561161457600080fd5b938501935b8385101561163257843582529385019390850190611619565b98975050505050505050565b6000806040838503121561165157600080fd5b50508035926020909101359150565b60006040828403121561167257600080fd5b82601f83011261168157600080fd5b6040516040810181811067ffffffffffffffff821117156116a4576116a46114d3565b806040525080604084018581111561157357600080fd5b600060a082840312156116cd57600080fd5b82601f8301126116dc57600080fd5b60405160a0810181811067ffffffffffffffff821117156116ff576116ff6114d3565b6040528060a084018581111561157357600080fd5b60006060828403121561172657600080fd5b82601f83011261173557600080fd5b6040516060810181811067ffffffffffffffff82111715611758576117586114d3565b60405280606084018581111561157357600080fd5b60006020828403121561177f57600080fd5b81356001600160a01b038116811461179657600080fd5b9392505050565b634e487b7160e01b600052601160045260246000fd5b600181815b808511156117ee5781600019048211156117d4576117d461179d565b808516156117e157918102915b93841c93908002906117b8565b509250929050565b6000826118055750600161079e565b816118125750600061079e565b816001811461182857600281146118325761184e565b600191505061079e565b60ff8411156118435761184361179d565b50506001821b61079e565b5060208310610133831016604e8410600b8410161715611871575081810a61079e565b61187b83836117b3565b806000190482111561188f5761188f61179d565b029392505050565b600061179683836117f6565b634e487b7160e01b600052603260045260246000fd5b8082018082111561079e5761079e61179d565b6000826118e957634e487b7160e01b600052601260045260246000fd5b500690565b6000600182016119005761190061179d565b5060010190565b60808101818360005b600481101561192f578151835260209283019290910190600101611910565b50505092915050565b60006020828403121561194a57600080fd5b5051919050565b815160009082906020808601845b8381101561197b5781518552938201939082019060010161195f565b50929695505050505050565b6000825160005b818110156119a8576020818601810151858301520161198e565b506000920191825250919050565b60408101818360005b600281101561192f5781518352602092830192909101906001016119bf565b60a08101818360005b600581101561192f5781518352602092830192909101906001016119e7565b60608101818360005b600381101561192f578151835260209283019290910190600101611a0f565b808202811582820484141761079e5761079e61179d565b8181038181111561079e5761079e61179d565b600060ff821660ff8103611a6e57611a6e61179d565b6001019291505056fea2646970667358221220de48377ebab560ef190138d15ea2cd48ec74d706562bdc76aca8c6093ed43a8e64736f6c63430008140033