// File: @openzeppelin/contracts/access/Ownable.sol



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

pragma solidity ^0.8.0;

import "../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.
 *
 * By default, the owner account will be the one that deploys the contract. 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;

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

    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _transferOwnership(_msgSender());
    }

    /**
     * @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 {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
    }

    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing 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 {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _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);
    }
}

// File: @openzeppelin/contracts/proxy/Clones.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (proxy/Clones.sol)

pragma solidity ^0.8.0;

/**
 * @dev https://eips.ethereum.org/EIPS/eip-1167[EIP 1167] is a standard for
 * deploying minimal proxy contracts, also known as "clones".
 *
 * > To simply and cheaply clone contract functionality in an immutable way, this standard specifies
 * > a minimal bytecode implementation that delegates all calls to a known, fixed address.
 *
 * The library includes functions to deploy a proxy using either `create` (traditional deployment) or `create2`
 * (salted deterministic deployment). It also includes functions to predict the addresses of clones deployed using the
 * deterministic method.
 *
 * _Available since v3.4._
 */
library Clones {
    /**
     * @dev Deploys and returns the address of a clone that mimics the behaviour of `implementation`.
     *
     * This function uses the create opcode, which should never revert.
     */
    function clone(address implementation) internal returns (address instance) {
        /// @solidity memory-safe-assembly
        assembly {
            // Cleans the upper 96 bits of the `implementation` word, then packs the first 3 bytes
            // of the `implementation` address with the bytecode before the address.
            mstore(0x00, or(shr(0xe8, shl(0x60, implementation)), 0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000))
            // Packs the remaining 17 bytes of `implementation` with the bytecode after the address.
            mstore(0x20, or(shl(0x78, implementation), 0x5af43d82803e903d91602b57fd5bf3))
            instance := create(0, 0x09, 0x37)
        }
        require(instance != address(0), "ERC1167: create failed");
    }

    /**
     * @dev Deploys and returns the address of a clone that mimics the behaviour of `implementation`.
     *
     * This function uses the create2 opcode and a `salt` to deterministically deploy
     * the clone. Using the same `implementation` and `salt` multiple time will revert, since
     * the clones cannot be deployed twice at the same address.
     */
    function cloneDeterministic(address implementation, bytes32 salt) internal returns (address instance) {
        /// @solidity memory-safe-assembly
        assembly {
            // Cleans the upper 96 bits of the `implementation` word, then packs the first 3 bytes
            // of the `implementation` address with the bytecode before the address.
            mstore(0x00, or(shr(0xe8, shl(0x60, implementation)), 0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000))
            // Packs the remaining 17 bytes of `implementation` with the bytecode after the address.
            mstore(0x20, or(shl(0x78, implementation), 0x5af43d82803e903d91602b57fd5bf3))
            instance := create2(0, 0x09, 0x37, salt)
        }
        require(instance != address(0), "ERC1167: create2 failed");
    }

    /**
     * @dev Computes the address of a clone deployed using {Clones-cloneDeterministic}.
     */
    function predictDeterministicAddress(
        address implementation,
        bytes32 salt,
        address deployer
    ) internal pure returns (address predicted) {
        /// @solidity memory-safe-assembly
        assembly {
            let ptr := mload(0x40)
            mstore(add(ptr, 0x38), deployer)
            mstore(add(ptr, 0x24), 0x5af43d82803e903d91602b57fd5bf3ff)
            mstore(add(ptr, 0x14), implementation)
            mstore(ptr, 0x3d602d80600a3d3981f3363d3d373d3d3d363d73)
            mstore(add(ptr, 0x58), salt)
            mstore(add(ptr, 0x78), keccak256(add(ptr, 0x0c), 0x37))
            predicted := keccak256(add(ptr, 0x43), 0x55)
        }
    }

    /**
     * @dev Computes the address of a clone deployed using {Clones-cloneDeterministic}.
     */
    function predictDeterministicAddress(address implementation, bytes32 salt)
        internal
        view
        returns (address predicted)
    {
        return predictDeterministicAddress(implementation, salt, address(this));
    }
}

// File: @openzeppelin/contracts/security/ReentrancyGuard.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (security/ReentrancyGuard.sol)

pragma solidity ^0.8.0;

/**
 * @dev Contract module that helps prevent reentrant calls to a function.
 *
 * Inheriting from `ReentrancyGuard` will make the {nonReentrant} modifier
 * available, which can be applied to functions to make sure there are no nested
 * (reentrant) calls to them.
 *
 * Note that because there is a single `nonReentrant` guard, functions marked as
 * `nonReentrant` may not call one another. This can be worked around by making
 * those functions `private`, and then adding `external` `nonReentrant` entry
 * points to them.
 *
 * TIP: If you would like to learn more about reentrancy and alternative ways
 * to protect against it, check out our blog post
 * https://blog.openzeppelin.com/reentrancy-after-istanbul/[Reentrancy After Istanbul].
 */
abstract contract ReentrancyGuard {
    // Booleans are more expensive than uint256 or any type that takes up a full
    // word because each write operation emits an extra SLOAD to first read the
    // slot's contents, replace the bits taken up by the boolean, and then write
    // back. This is the compiler's defense against contract upgrades and
    // pointer aliasing, and it cannot be disabled.

    // The values being non-zero value makes deployment a bit more expensive,
    // but in exchange the refund on every call to nonReentrant will be lower in
    // amount. Since refunds are capped to a percentage of the total
    // transaction's gas, it is best to keep them low in cases like this one, to
    // increase the likelihood of the full refund coming into effect.
    uint256 private constant _NOT_ENTERED = 1;
    uint256 private constant _ENTERED = 2;

    uint256 private _status;

    constructor() {
        _status = _NOT_ENTERED;
    }

    /**
     * @dev Prevents a contract from calling itself, directly or indirectly.
     * Calling a `nonReentrant` function from another `nonReentrant`
     * function is not supported. It is possible to prevent this from happening
     * by making the `nonReentrant` function external, and making it call a
     * `private` function that does the actual work.
     */
    modifier nonReentrant() {
        _nonReentrantBefore();
        _;
        _nonReentrantAfter();
    }

    function _nonReentrantBefore() private {
        // On the first call to nonReentrant, _status will be _NOT_ENTERED
        require(_status != _ENTERED, "ReentrancyGuard: reentrant call");

        // Any calls to nonReentrant after this point will fail
        _status = _ENTERED;
    }

    function _nonReentrantAfter() private {
        // By storing the original value once again, a refund is triggered (see
        // https://eips.ethereum.org/EIPS/eip-2200)
        _status = _NOT_ENTERED;
    }
}

// File: @openzeppelin/contracts/token/ERC721/ERC721.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (token/ERC721/ERC721.sol)

pragma solidity ^0.8.0;

import "./IERC721.sol";
import "./IERC721Receiver.sol";
import "./extensions/IERC721Metadata.sol";
import "../../utils/Address.sol";
import "../../utils/Context.sol";
import "../../utils/Strings.sol";
import "../../utils/introspection/ERC165.sol";

/**
 * @dev Implementation of https://eips.ethereum.org/EIPS/eip-721[ERC721] Non-Fungible Token Standard, including
 * the Metadata extension, but not including the Enumerable extension, which is available separately as
 * {ERC721Enumerable}.
 */
contract ERC721 is Context, ERC165, IERC721, IERC721Metadata {
    using Address for address;
    using Strings for uint256;

    // Token name
    string private _name;

    // Token symbol
    string private _symbol;

    // Mapping from token ID to owner address
    mapping(uint256 => address) private _owners;

    // Mapping owner address to token count
    mapping(address => uint256) private _balances;

    // Mapping from token ID to approved address
    mapping(uint256 => address) private _tokenApprovals;

    // Mapping from owner to operator approvals
    mapping(address => mapping(address => bool)) private _operatorApprovals;

    /**
     * @dev Initializes the contract by setting a `name` and a `symbol` to the token collection.
     */
    constructor(string memory name_, string memory symbol_) {
        _name = name_;
        _symbol = symbol_;
    }

    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override(ERC165, IERC165) returns (bool) {
        return
            interfaceId == type(IERC721).interfaceId ||
            interfaceId == type(IERC721Metadata).interfaceId ||
            super.supportsInterface(interfaceId);
    }

    /**
     * @dev See {IERC721-balanceOf}.
     */
    function balanceOf(address owner) public view virtual override returns (uint256) {
        require(owner != address(0), "ERC721: address zero is not a valid owner");
        return _balances[owner];
    }

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId) public view virtual override returns (address) {
        address owner = _ownerOf(tokenId);
        require(owner != address(0), "ERC721: invalid token ID");
        return owner;
    }

    /**
     * @dev See {IERC721Metadata-name}.
     */
    function name() public view virtual override returns (string memory) {
        return _name;
    }

    /**
     * @dev See {IERC721Metadata-symbol}.
     */
    function symbol() public view virtual override returns (string memory) {
        return _symbol;
    }

    /**
     * @dev See {IERC721Metadata-tokenURI}.
     */
    function tokenURI(uint256 tokenId) public view virtual override returns (string memory) {
        _requireMinted(tokenId);

        string memory baseURI = _baseURI();
        return bytes(baseURI).length > 0 ? string(abi.encodePacked(baseURI, tokenId.toString())) : "";
    }

    /**
     * @dev Base URI for computing {tokenURI}. If set, the resulting URI for each
     * token will be the concatenation of the `baseURI` and the `tokenId`. Empty
     * by default, can be overridden in child contracts.
     */
    function _baseURI() internal view virtual returns (string memory) {
        return "";
    }

    /**
     * @dev See {IERC721-approve}.
     */
    function approve(address to, uint256 tokenId) public virtual override {
        address owner = ERC721.ownerOf(tokenId);
        require(to != owner, "ERC721: approval to current owner");

        require(
            _msgSender() == owner || isApprovedForAll(owner, _msgSender()),
            "ERC721: approve caller is not token owner or approved for all"
        );

        _approve(to, tokenId);
    }

    /**
     * @dev See {IERC721-getApproved}.
     */
    function getApproved(uint256 tokenId) public view virtual override returns (address) {
        _requireMinted(tokenId);

        return _tokenApprovals[tokenId];
    }

    /**
     * @dev See {IERC721-setApprovalForAll}.
     */
    function setApprovalForAll(address operator, bool approved) public virtual override {
        _setApprovalForAll(_msgSender(), operator, approved);
    }

    /**
     * @dev See {IERC721-isApprovedForAll}.
     */
    function isApprovedForAll(address owner, address operator) public view virtual override returns (bool) {
        return _operatorApprovals[owner][operator];
    }

    /**
     * @dev See {IERC721-transferFrom}.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public virtual override {
        //solhint-disable-next-line max-line-length
        require(_isApprovedOrOwner(_msgSender(), tokenId), "ERC721: caller is not token owner or approved");

        _transfer(from, to, tokenId);
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public virtual override {
        safeTransferFrom(from, to, tokenId, "");
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes memory data
    ) public virtual override {
        require(_isApprovedOrOwner(_msgSender(), tokenId), "ERC721: caller is not token owner or approved");
        _safeTransfer(from, to, tokenId, data);
    }

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking first that contract recipients
     * are aware of the ERC721 protocol to prevent tokens from being forever locked.
     *
     * `data` is additional data, it has no specified format and it is sent in call to `to`.
     *
     * This internal function is equivalent to {safeTransferFrom}, and can be used to e.g.
     * implement alternative mechanisms to perform token transfer, such as signature-based.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function _safeTransfer(
        address from,
        address to,
        uint256 tokenId,
        bytes memory data
    ) internal virtual {
        _transfer(from, to, tokenId);
        require(_checkOnERC721Received(from, to, tokenId, data), "ERC721: transfer to non ERC721Receiver implementer");
    }

    /**
     * @dev Returns the owner of the `tokenId`. Does NOT revert if token doesn't exist
     */
    function _ownerOf(uint256 tokenId) internal view virtual returns (address) {
        return _owners[tokenId];
    }

    /**
     * @dev Returns whether `tokenId` exists.
     *
     * Tokens can be managed by their owner or approved accounts via {approve} or {setApprovalForAll}.
     *
     * Tokens start existing when they are minted (`_mint`),
     * and stop existing when they are burned (`_burn`).
     */
    function _exists(uint256 tokenId) internal view virtual returns (bool) {
        return _ownerOf(tokenId) != address(0);
    }

    /**
     * @dev Returns whether `spender` is allowed to manage `tokenId`.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function _isApprovedOrOwner(address spender, uint256 tokenId) internal view virtual returns (bool) {
        address owner = ERC721.ownerOf(tokenId);
        return (spender == owner || isApprovedForAll(owner, spender) || getApproved(tokenId) == spender);
    }

    /**
     * @dev Safely mints `tokenId` and transfers it to `to`.
     *
     * Requirements:
     *
     * - `tokenId` must not exist.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function _safeMint(address to, uint256 tokenId) internal virtual {
        _safeMint(to, tokenId, "");
    }

    /**
     * @dev Same as {xref-ERC721-_safeMint-address-uint256-}[`_safeMint`], with an additional `data` parameter which is
     * forwarded in {IERC721Receiver-onERC721Received} to contract recipients.
     */
    function _safeMint(
        address to,
        uint256 tokenId,
        bytes memory data
    ) internal virtual {
        _mint(to, tokenId);
        require(
            _checkOnERC721Received(address(0), to, tokenId, data),
            "ERC721: transfer to non ERC721Receiver implementer"
        );
    }

    /**
     * @dev Mints `tokenId` and transfers it to `to`.
     *
     * WARNING: Usage of this method is discouraged, use {_safeMint} whenever possible
     *
     * Requirements:
     *
     * - `tokenId` must not exist.
     * - `to` cannot be the zero address.
     *
     * Emits a {Transfer} event.
     */
    function _mint(address to, uint256 tokenId) internal virtual {
        require(to != address(0), "ERC721: mint to the zero address");
        require(!_exists(tokenId), "ERC721: token already minted");

        _beforeTokenTransfer(address(0), to, tokenId, 1);

        // Check that tokenId was not minted by `_beforeTokenTransfer` hook
        require(!_exists(tokenId), "ERC721: token already minted");

        unchecked {
            // Will not overflow unless all 2**256 token ids are minted to the same owner.
            // Given that tokens are minted one by one, it is impossible in practice that
            // this ever happens. Might change if we allow batch minting.
            // The ERC fails to describe this case.
            _balances[to] += 1;
        }

        _owners[tokenId] = to;

        emit Transfer(address(0), to, tokenId);

        _afterTokenTransfer(address(0), to, tokenId, 1);
    }

    /**
     * @dev Destroys `tokenId`.
     * The approval is cleared when the token is burned.
     * This is an internal function that does not check if the sender is authorized to operate on the token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     *
     * Emits a {Transfer} event.
     */
    function _burn(uint256 tokenId) internal virtual {
        address owner = ERC721.ownerOf(tokenId);

        _beforeTokenTransfer(owner, address(0), tokenId, 1);

        // Update ownership in case tokenId was transferred by `_beforeTokenTransfer` hook
        owner = ERC721.ownerOf(tokenId);

        // Clear approvals
        delete _tokenApprovals[tokenId];

        unchecked {
            // Cannot overflow, as that would require more tokens to be burned/transferred
            // out than the owner initially received through minting and transferring in.
            _balances[owner] -= 1;
        }
        delete _owners[tokenId];

        emit Transfer(owner, address(0), tokenId);

        _afterTokenTransfer(owner, address(0), tokenId, 1);
    }

    /**
     * @dev Transfers `tokenId` from `from` to `to`.
     *  As opposed to {transferFrom}, this imposes no restrictions on msg.sender.
     *
     * Requirements:
     *
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     *
     * Emits a {Transfer} event.
     */
    function _transfer(
        address from,
        address to,
        uint256 tokenId
    ) internal virtual {
        require(ERC721.ownerOf(tokenId) == from, "ERC721: transfer from incorrect owner");
        require(to != address(0), "ERC721: transfer to the zero address");

        _beforeTokenTransfer(from, to, tokenId, 1);

        // Check that tokenId was not transferred by `_beforeTokenTransfer` hook
        require(ERC721.ownerOf(tokenId) == from, "ERC721: transfer from incorrect owner");

        // Clear approvals from the previous owner
        delete _tokenApprovals[tokenId];

        unchecked {
            // `_balances[from]` cannot overflow for the same reason as described in `_burn`:
            // `from`'s balance is the number of token held, which is at least one before the current
            // transfer.
            // `_balances[to]` could overflow in the conditions described in `_mint`. That would require
            // all 2**256 token ids to be minted, which in practice is impossible.
            _balances[from] -= 1;
            _balances[to] += 1;
        }
        _owners[tokenId] = to;

        emit Transfer(from, to, tokenId);

        _afterTokenTransfer(from, to, tokenId, 1);
    }

    /**
     * @dev Approve `to` to operate on `tokenId`
     *
     * Emits an {Approval} event.
     */
    function _approve(address to, uint256 tokenId) internal virtual {
        _tokenApprovals[tokenId] = to;
        emit Approval(ERC721.ownerOf(tokenId), to, tokenId);
    }

    /**
     * @dev Approve `operator` to operate on all of `owner` tokens
     *
     * Emits an {ApprovalForAll} event.
     */
    function _setApprovalForAll(
        address owner,
        address operator,
        bool approved
    ) internal virtual {
        require(owner != operator, "ERC721: approve to caller");
        _operatorApprovals[owner][operator] = approved;
        emit ApprovalForAll(owner, operator, approved);
    }

    /**
     * @dev Reverts if the `tokenId` has not been minted yet.
     */
    function _requireMinted(uint256 tokenId) internal view virtual {
        require(_exists(tokenId), "ERC721: invalid token ID");
    }

    /**
     * @dev Internal function to invoke {IERC721Receiver-onERC721Received} on a target address.
     * The call is not executed if the target address is not a contract.
     *
     * @param from address representing the previous owner of the given token ID
     * @param to target address that will receive the tokens
     * @param tokenId uint256 ID of the token to be transferred
     * @param data bytes optional data to send along with the call
     * @return bool whether the call correctly returned the expected magic value
     */
    function _checkOnERC721Received(
        address from,
        address to,
        uint256 tokenId,
        bytes memory data
    ) private returns (bool) {
        if (to.isContract()) {
            try IERC721Receiver(to).onERC721Received(_msgSender(), from, tokenId, data) returns (bytes4 retval) {
                return retval == IERC721Receiver.onERC721Received.selector;
            } catch (bytes memory reason) {
                if (reason.length == 0) {
                    revert("ERC721: transfer to non ERC721Receiver implementer");
                } else {
                    /// @solidity memory-safe-assembly
                    assembly {
                        revert(add(32, reason), mload(reason))
                    }
                }
            }
        } else {
            return true;
        }
    }

    /**
     * @dev Hook that is called before any token transfer. This includes minting and burning. If {ERC721Consecutive} is
     * used, the hook may be called as part of a consecutive (batch) mint, as indicated by `batchSize` greater than 1.
     *
     * Calling conditions:
     *
     * - When `from` and `to` are both non-zero, ``from``'s tokens will be transferred to `to`.
     * - When `from` is zero, the tokens will be minted for `to`.
     * - When `to` is zero, ``from``'s tokens will be burned.
     * - `from` and `to` are never both zero.
     * - `batchSize` is non-zero.
     *
     * To learn more about hooks, head to xref:ROOT:extending-contracts.adoc#using-hooks[Using Hooks].
     */
    function _beforeTokenTransfer(
        address from,
        address to,
        uint256, /* firstTokenId */
        uint256 batchSize
    ) internal virtual {
        if (batchSize > 1) {
            if (from != address(0)) {
                _balances[from] -= batchSize;
            }
            if (to != address(0)) {
                _balances[to] += batchSize;
            }
        }
    }

    /**
     * @dev Hook that is called after any token transfer. This includes minting and burning. If {ERC721Consecutive} is
     * used, the hook may be called as part of a consecutive (batch) mint, as indicated by `batchSize` greater than 1.
     *
     * Calling conditions:
     *
     * - When `from` and `to` are both non-zero, ``from``'s tokens were transferred to `to`.
     * - When `from` is zero, the tokens were minted for `to`.
     * - When `to` is zero, ``from``'s tokens were burned.
     * - `from` and `to` are never both zero.
     * - `batchSize` is non-zero.
     *
     * To learn more about hooks, head to xref:ROOT:extending-contracts.adoc#using-hooks[Using Hooks].
     */
    function _afterTokenTransfer(
        address from,
        address to,
        uint256 firstTokenId,
        uint256 batchSize
    ) internal virtual {}
}

// File: @openzeppelin/contracts/token/ERC721/extensions/IERC721Metadata.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (token/ERC721/extensions/IERC721Metadata.sol)

pragma solidity ^0.8.0;

import "../IERC721.sol";

/**
 * @title ERC-721 Non-Fungible Token Standard, optional metadata extension
 * @dev See https://eips.ethereum.org/EIPS/eip-721
 */
interface IERC721Metadata is IERC721 {
    /**
     * @dev Returns the token collection name.
     */
    function name() external view returns (string memory);

    /**
     * @dev Returns the token collection symbol.
     */
    function symbol() external view returns (string memory);

    /**
     * @dev Returns the Uniform Resource Identifier (URI) for `tokenId` token.
     */
    function tokenURI(uint256 tokenId) external view returns (string memory);
}

// File: @openzeppelin/contracts/token/ERC721/IERC721.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (token/ERC721/IERC721.sol)

pragma solidity ^0.8.0;

import "../../utils/introspection/IERC165.sol";

/**
 * @dev Required interface of an ERC721 compliant contract.
 */
interface IERC721 is IERC165 {
    /**
     * @dev Emitted when `tokenId` token is transferred from `from` to `to`.
     */
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables `approved` to manage the `tokenId` token.
     */
    event Approval(address indexed owner, address indexed approved, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables or disables (`approved`) `operator` to manage all of its assets.
     */
    event ApprovalForAll(address indexed owner, address indexed operator, bool approved);

    /**
     * @dev Returns the number of tokens in ``owner``'s account.
     */
    function balanceOf(address owner) external view returns (uint256 balance);

    /**
     * @dev Returns the owner of the `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function ownerOf(uint256 tokenId) external view returns (address owner);

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes calldata data
    ) external;

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking first that contract recipients
     * are aware of the ERC721 protocol to prevent tokens from being forever locked.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must have been allowed to move this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external;

    /**
     * @dev Transfers `tokenId` token from `from` to `to`.
     *
     * WARNING: Note that the caller is responsible to confirm that the recipient is capable of receiving ERC721
     * or else they may be permanently lost. Usage of {safeTransferFrom} prevents loss, though the caller must
     * understand this adds an external call which potentially creates a reentrancy vulnerability.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external;

    /**
     * @dev Gives permission to `to` to transfer `tokenId` token to another account.
     * The approval is cleared when the token is transferred.
     *
     * Only a single account can be approved at a time, so approving the zero address clears previous approvals.
     *
     * Requirements:
     *
     * - The caller must own the token or be an approved operator.
     * - `tokenId` must exist.
     *
     * Emits an {Approval} event.
     */
    function approve(address to, uint256 tokenId) external;

    /**
     * @dev Approve or remove `operator` as an operator for the caller.
     * Operators can call {transferFrom} or {safeTransferFrom} for any token owned by the caller.
     *
     * Requirements:
     *
     * - The `operator` cannot be the caller.
     *
     * Emits an {ApprovalForAll} event.
     */
    function setApprovalForAll(address operator, bool _approved) external;

    /**
     * @dev Returns the account approved for `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function getApproved(uint256 tokenId) external view returns (address operator);

    /**
     * @dev Returns if the `operator` is allowed to manage all of the assets of `owner`.
     *
     * See {setApprovalForAll}
     */
    function isApprovedForAll(address owner, address operator) external view returns (bool);
}

// File: @openzeppelin/contracts/token/ERC721/IERC721Receiver.sol



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

pragma solidity ^0.8.0;

/**
 * @title ERC721 token receiver interface
 * @dev Interface for any contract that wants to support safeTransfers
 * from ERC721 asset contracts.
 */
interface IERC721Receiver {
    /**
     * @dev Whenever an {IERC721} `tokenId` token is transferred to this contract via {IERC721-safeTransferFrom}
     * by `operator` from `from`, this function is called.
     *
     * It must return its Solidity selector to confirm the token transfer.
     * If any other value is returned or the interface is not implemented by the recipient, the transfer will be reverted.
     *
     * The selector can be obtained in Solidity with `IERC721Receiver.onERC721Received.selector`.
     */
    function onERC721Received(
        address operator,
        address from,
        uint256 tokenId,
        bytes calldata data
    ) external returns (bytes4);
}

// File: @openzeppelin/contracts/utils/Address.sol



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

pragma solidity ^0.8.1;

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

        return account.code.length > 0;
    }

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

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

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

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

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

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

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

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

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

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and revert (either by bubbling
     * the revert reason or using the provided one) in case of unsuccessful call or if target was not a contract.
     *
     * _Available since v4.8._
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        if (success) {
            if (returndata.length == 0) {
                // only check isContract if the call was successful and the return data is empty
                // otherwise we already know that it was a contract
                require(isContract(target), "Address: call to non-contract");
            }
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    /**
     * @dev Tool to verify that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason or using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    function _revert(bytes memory returndata, string memory errorMessage) private pure {
        // Look for revert reason and bubble it up if present
        if (returndata.length > 0) {
            // The easiest way to bubble the revert reason is using memory via assembly
            /// @solidity memory-safe-assembly
            assembly {
                let returndata_size := mload(returndata)
                revert(add(32, returndata), returndata_size)
            }
        } else {
            revert(errorMessage);
        }
    }
}

// File: @openzeppelin/contracts/utils/Context.sol



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

pragma solidity ^0.8.0;

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

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

// File: @openzeppelin/contracts/utils/introspection/ERC165.sol



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

pragma solidity ^0.8.0;

import "./IERC165.sol";

/**
 * @dev Implementation of the {IERC165} interface.
 *
 * Contracts that want to implement ERC165 should inherit from this contract and override {supportsInterface} to check
 * for the additional interface id that will be supported. For example:
 *
 * ```solidity
 * function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
 *     return interfaceId == type(MyInterface).interfaceId || super.supportsInterface(interfaceId);
 * }
 * ```
 *
 * Alternatively, {ERC165Storage} provides an easier to use but more expensive implementation.
 */
abstract contract ERC165 is IERC165 {
    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IERC165).interfaceId;
    }
}

// File: @openzeppelin/contracts/utils/introspection/IERC165.sol



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

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC165 standard, as defined in the
 * https://eips.ethereum.org/EIPS/eip-165[EIP].
 *
 * Implementers can declare support of contract interfaces, which can then be
 * queried by others ({ERC165Checker}).
 *
 * For an implementation, see {ERC165}.
 */
interface IERC165 {
    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified[EIP section]
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30 000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);
}

// File: @openzeppelin/contracts/utils/math/Math.sol



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

pragma solidity ^0.8.0;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        // For our first guess, we get the biggest power of 2 which is smaller than the square root of the target.
        //
        // We know that the "msb" (most significant bit) of our target number `a` is a power of 2 such that we have
        // `msb(a) <= a < 2*msb(a)`. This value can be written `msb(a)=2**k` with `k=log2(a)`.
        //
        // This can be rewritten `2**log2(a) <= a < 2**(log2(a) + 1)`
        // → `sqrt(2**k) <= sqrt(a) < sqrt(2**(k+1))`
        // → `2**(k/2) <= sqrt(a) < 2**((k+1)/2) <= 2**(k/2 + 1)`
        //
        // Consequently, `2**(log2(a) / 2)` is a good first approximation of `sqrt(a)` with at least 1 correct bit.
        uint256 result = 1 << (log2(a) >> 1);

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

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

    /**
     * @dev Return the log in base 2, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 128;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 64;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 32;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 16;
            }
            if (value >> 8 > 0) {
                value >>= 8;
                result += 8;
            }
            if (value >> 4 > 0) {
                value >>= 4;
                result += 4;
            }
            if (value >> 2 > 0) {
                value >>= 2;
                result += 2;
            }
            if (value >> 1 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 2, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log2(value);
            return result + (rounding == Rounding.Up && 1 << result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 10, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >= 10**64) {
                value /= 10**64;
                result += 64;
            }
            if (value >= 10**32) {
                value /= 10**32;
                result += 32;
            }
            if (value >= 10**16) {
                value /= 10**16;
                result += 16;
            }
            if (value >= 10**8) {
                value /= 10**8;
                result += 8;
            }
            if (value >= 10**4) {
                value /= 10**4;
                result += 4;
            }
            if (value >= 10**2) {
                value /= 10**2;
                result += 2;
            }
            if (value >= 10**1) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 10, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log10(value);
            return result + (rounding == Rounding.Up && 10**result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 256, rounded down, of a positive value.
     * Returns 0 if given 0.
     *
     * Adding one to the result gives the number of pairs of hex symbols needed to represent `value` as a hex string.
     */
    function log256(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 16;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 8;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 4;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 2;
            }
            if (value >> 8 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 10, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log256(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log256(value);
            return result + (rounding == Rounding.Up && 1 << (result * 8) < value ? 1 : 0);
        }
    }
}

// File: @openzeppelin/contracts/utils/Strings.sol



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

pragma solidity ^0.8.0;

import "./math/Math.sol";

/**
 * @dev String operations.
 */
library Strings {
    bytes16 private constant _SYMBOLS = "0123456789abcdef";
    uint8 private constant _ADDRESS_LENGTH = 20;

    /**
     * @dev Converts a `uint256` to its ASCII `string` decimal representation.
     */
    function toString(uint256 value) internal pure returns (string memory) {
        unchecked {
            uint256 length = Math.log10(value) + 1;
            string memory buffer = new string(length);
            uint256 ptr;
            /// @solidity memory-safe-assembly
            assembly {
                ptr := add(buffer, add(32, length))
            }
            while (true) {
                ptr--;
                /// @solidity memory-safe-assembly
                assembly {
                    mstore8(ptr, byte(mod(value, 10), _SYMBOLS))
                }
                value /= 10;
                if (value == 0) break;
            }
            return buffer;
        }
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation.
     */
    function toHexString(uint256 value) internal pure returns (string memory) {
        unchecked {
            return toHexString(value, Math.log256(value) + 1);
        }
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation with fixed length.
     */
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory) {
        bytes memory buffer = new bytes(2 * length + 2);
        buffer[0] = "0";
        buffer[1] = "x";
        for (uint256 i = 2 * length + 1; i > 1; --i) {
            buffer[i] = _SYMBOLS[value & 0xf];
            value >>= 4;
        }
        require(value == 0, "Strings: hex length insufficient");
        return string(buffer);
    }

    /**
     * @dev Converts an `address` with fixed length of 20 bytes to its not checksummed ASCII `string` hexadecimal representation.
     */
    function toHexString(address addr) internal pure returns (string memory) {
        return toHexString(uint256(uint160(addr)), _ADDRESS_LENGTH);
    }
}

// File: contracts/modules/Json.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import '../Polly.sol';

contract Json is PMReadOnly {

  enum Type {
    STRING, BOOL, NUMBER, OBJECT, ARRAY
  }

  enum Format {
    KEY_VALUE, VALUE, ARRAY, OBJECT
  }

  struct Item {
    Type _type;
    string _key;
    string _string;
    bool _bool;
    uint _uint;
  }

  string public constant override PMNAME = 'Json';
  uint public constant override PMVERSION = 1;

  function encode(Item[] memory items_, Format format_) public pure returns(string memory){

      bytes[] memory parts_ = new bytes[](items_.length);
      bytes memory append_ = ',';
      bool include_key_;

      for (uint i = 0; i < items_.length; i++) {

        Item memory item = items_[i];

        if(i+1 == items_.length) {
          append_ = '';
        }

        if((format_ == Format.OBJECT || format_ == Format.KEY_VALUE))
          include_key_ = true;
        else
          include_key_ = false;

        if (item._type == Type.OBJECT || item._type == Type.ARRAY) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', item._string, append_);
        } else if (item._type == Type.STRING) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', '"', item._string, '"', append_);
        } else if (item._type == Type.BOOL) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', item._bool ? 'true' : 'false', append_);
        } else if (item._type == Type.NUMBER) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', Strings.toString(item._uint), append_);
        }

      }

      bytes memory open_;
      bytes memory close_;

      if(format_ == Format.ARRAY){
        open_ = '[';
        close_ = ']';
      }
      else if(format_ == Format.OBJECT){
        open_ = '{';
        close_ = '}';
      }

      bytes memory json_;
      for (uint i = 0; i < parts_.length; i++) {
        json_ = abi.encodePacked(json_, parts_[i]);
      }
      json_ = abi.encodePacked(open_, json_, close_);

      return string(json_);
  }


  function _getKeyJson(string memory key_) private pure returns(string memory){
    return string(abi.encodePacked('"', key_,'":'));
  }

}

// File: contracts/modules/Meta.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import '../Polly.sol';
import '../PollyConfigurator.sol';
import './Json.sol';


contract Meta is PMClone {

  Json private _json_parser;
  string public constant override PMNAME = 'Meta';
  uint public constant override PMVERSION = 1;

  struct Item {
    Json.Type _type;
    string _key;
    string _inject;
  }

  mapping(uint => mapping(string => Polly.Param)) private _keys;
  mapping(uint => mapping(string => bool)) private _locked_id_keys;
  mapping(string => bool) private _locked_keys;
  mapping(uint => bool) private _locked_ids;

  modifier onlyManager() {
    require(hasRole('manager', msg.sender), 'ONLY_MANAGER');
    _;
  }

  constructor() PMClone(){
    _setConfigurator(address(new MetaConfigurator()));
  }

  function setJsonParser(address json_parser) public onlyManager {
    _json_parser = Json(json_parser);
  }

  function _reqValidKeyID(uint id_, string memory key_) private view {
    require(!isLockedId(id_), string(abi.encodePacked('ID_KEY_LOCKED', Strings.toString(id_))));
    require(!isLockedKey(key_), string(abi.encodePacked('KEY_LOCKED', key_)));
    require(!isLockedIdKey(id_, key_), string(abi.encodePacked('KEY_LOCKED', Strings.toString(id_), ':', key_)));
  }



  /// JSON
  function getJSON(uint id_, Item[] memory items_, Json.Format format_) public view returns (string memory) {

    Json.Item[] memory json_items_ = new Json.Item[](items_.length);
    Item memory item;

    for (uint i = 0; i < items_.length; i++) {

      item = items_[i];

      json_items_[i]._key = item._key;
      json_items_[i]._type = item._type;

      if(item._type == Json.Type.ARRAY || item._type == Json.Type.OBJECT) {
        json_items_[i]._string = item._inject;
      } else if (item._type == Json.Type.STRING) {
        json_items_[i]._string = _keys[id_][item._key]._string;
      } else if (item._type == Json.Type.BOOL) {
        json_items_[i]._bool = _keys[id_][item._key]._bool;
      } else if (item._type == Json.Type.NUMBER) {
        json_items_[i]._uint = _keys[id_][item._key]._uint;
      }

    }

    string memory json_ = _json_parser.encode(json_items_, format_);

    return string(json_);

  }

  function _getKeyJson(string memory key_) private pure returns(string memory){
    return string(abi.encodePacked('"', key_,'":'));
  }


  /// Access
  function lockKey(string memory key_) public onlyManager {
    _locked_keys[key_] = true;
  }

  function lockId(uint id_) public onlyManager {
    _locked_ids[id_] = true;
  }

  function lockIdKey(uint id_, string memory key_) public onlyManager {
    _locked_id_keys[id_][key_] = true;
  }

  function isLockedKey(string memory key_) public view returns (bool) {
    return _locked_keys[key_];
  }

  function isLockedId(uint id_) public view returns (bool) {
    return _locked_ids[id_];
  }

  function isLockedIdKey(uint id_, string memory key_) public view returns (bool) {
    return _locked_id_keys[id_][key_];
  }

  function isLocked(uint id_, string memory key_) public view returns (bool) {
    return isLockedKey(key_) || isLockedId(id_) || isLockedIdKey(id_, key_);
  }


  /// Setters
  function set(uint id_, string memory key_, Polly.Param memory value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._string = value_._string;
    _keys[id_][key_]._uint = value_._uint;
    _keys[id_][key_]._int = value_._int;
    _keys[id_][key_]._bool = value_._bool;
    _keys[id_][key_]._address = value_._address;
  }

  function setString(uint id_, string memory key_, string memory value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._string = value_;
  }

  function setUint(uint id_, string memory key_, uint value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._uint = value_;
  }

  function setInt(uint id_, string memory key_, int value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._int = value_;
  }

  function setBool(uint id_, string memory key_, bool value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._bool = value_;
  }

  function setAddress(uint id_, string memory key_, address value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._address = value_;
  }

  function wipeKey(uint id_, string memory key_) public onlyManager {
    _reqValidKeyID(id_, key_);
    delete _keys[id_][key_];
  }



  /// Getters

  /// @dev Get a key param value
  /// @param id_ The id of the param
  /// @param key_ The key of the param
  /// @return The param value
  function get(uint id_, string memory key_) public view returns (Polly.Param memory) {
    return _keys[id_][key_];
  }

  /// @dev a function to retrieve a string value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getString(uint id_, string memory key_) public view returns (string memory) {
    return _keys[id_][key_]._string;
  }

  /// @dev a function to retrieve a uint value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getUint(uint id_, string memory key_) public view returns (uint) {
    return _keys[id_][key_]._uint;
  }

  /// @dev a function to retrieve a int value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getInt(uint id_, string memory key_) public view returns (int) {
    return _keys[id_][key_]._int;
  }

  /// @dev a function to retrieve a bool value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getBool(uint id_, string memory key_) public view returns (bool) {
    return _keys[id_][key_]._bool;
  }

  /// @dev a function to retrieve a address value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getAddress(uint id_, string memory key_) public view returns (address) {
    return _keys[id_][key_]._address;
  }


  function getBatchForId(uint id_, string[] memory keys_) public view returns (Polly.Param[] memory) {
    Polly.Param[] memory params_ = new Polly.Param[](keys_.length);
    for (uint i = 0; i < keys_.length; i++) {
      params_[i] = _keys[id_][keys_[i]];
    }
    return params_;
  }

  function setBatchForId(uint id_, string[] memory keys_, Polly.Param[] memory values_) public onlyManager {
    require(keys_.length == values_.length, "KEY_VALUE_LENGHT_MISMATCH");
    for (uint i = 0; i < keys_.length; i++) {
      _reqValidKeyID(id_, keys_[i]);
      _keys[id_][keys_[i]] = values_[i];
    }
  }

}


contract MetaConfigurator is PollyConfigurator {

  function outputs() public pure override returns (string[] memory) {

    string[] memory outputs_ = new string[](1);
    outputs_[0] = "module || Meta || address of the Meta module clone";

    return outputs_;

  }

  function run(Polly polly_, address for_, Polly.Param[] memory) public override payable returns(Polly.Param[] memory){

    // Clone a Meta module)
    Meta meta_ = Meta(polly_.cloneModule('Meta', 1));

    // Set the json module to use
    meta_.setJsonParser(polly_.getModule('Json', 1).implementation);

    // Grant roles to the address calling the configurator
    _transfer(address(meta_), for_);

    // Return the cloned module as part of the return parameters
    Polly.Param[] memory return_ = new Polly.Param[](1);
    return_[0]._string = 'Meta';
    return_[0]._address = address(meta_); // The address of newly cloned and configured meta module
    return_[0]._uint = 1; // The version of the module

    return return_;

  }


}

// File: contracts/modules/Token721.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import "@openzeppelin/contracts/token/ERC721/ERC721.sol";
import "@openzeppelin/contracts/security/ReentrancyGuard.sol";
import '../Polly.sol';
import '../PollyConfigurator.sol';
import '../PollyAux.sol';
import '../PollyToken.sol';
import './Json.sol';
import './Meta.sol';

contract Token721 is PollyToken, ERC721, ReentrancyGuard {


  string public constant override PMNAME = 'Token721';
  uint public constant override PMVERSION = 1;

  uint internal _minted;

  constructor() ERC721("", "") {
    _setConfigurator(address(new Token721Configurator()));
  }


  /*

  ERC721

  */


  function name() public view override returns (string memory) {
    return getMeta(0, 'collectionName')._string;
  }

  function symbol() public view override returns (string memory) {
    return getMeta(0, 'collectionSymbol')._string;
  }

  function exists(uint id_) public view returns (bool) {
    return _exists(id_);
  }

  function totalSupply() public view returns (uint) {
    return _minted;
  }


  /*

  TOKENS

  */

  /// @dev create a new token
  function createToken(PollyToken.MetaEntry[] memory meta_, address mint_) public returns (uint) {

    _requireRole('manager', msg.sender);

    uint id_ = _createToken(meta_);

    if(mint_ != address(0))
      _mintFor(mint_, id_, true, PollyAux.Msg(msg.sender, 0, msg.data, msg.sig));

    return id_;

  }



  /// @dev mint a token
  /// @param id_ the id of the token
  function _mintFor(address for_, uint id_, bool pre_, PollyAux.Msg memory msg_) private {

    address hook_ = getHookAddress('action_BeforeMint721');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_BeforeMint721(address,uint256,bool,(address,uint256,bytes,bytes4))', for_, id_, pre_, msg_));

    _mint(for_, id_);
    _minted++;

    hook_ = getHookAddress('action_AfterMint721');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_AfterMint721(address,uint256,bool,(address,uint256,bytes,bytes4))', for_, id_, pre_, msg_));

  }




  /// @dev mint a token
  /// @param id_ the id of the token
  function mint(uint id_) public payable nonReentrant {
    _mintFor(msg.sender, id_, false, PollyAux.Msg(msg.sender, msg.value, msg.data, msg.sig));
    _postMintTransfer(id_, msg.value);
  }


  /// @dev get the token uri
  /// @param id_ the id of the token
  function tokenURI(uint id_) public view override returns(string memory) {
    require(exists(id_), 'TOKEN_DOES_NOT_EXIST');
    return _tokenUri(id_);
  }


  /// Override
  function supportsInterface(bytes4 interfaceId) public view virtual override(PollyToken, ERC721) returns (bool){
      return super.supportsInterface(interfaceId);
  }


}







contract Token721Configurator is PollyConfigurator, ReentrancyGuard {

  function inputs() public pure override virtual returns (string[] memory) {

    string[] memory inputs_ = new string[](1);
    inputs_[0] = '...address || Aux addresses || addresses of the aux contracts to attach';
    return inputs_;
  }

  function outputs() public pure override virtual returns (string[] memory) {

    string[] memory outputs_ = new string[](2);

    outputs_[0] = 'module || Token721 || the main Token721 module address';
    outputs_[1] = 'module || Meta || the meta handler address';

    return outputs_;

  }

  function run(Polly polly_, address for_, Polly.Param[] memory inputs_) public override payable nonReentrant returns(Polly.Param[] memory) {

    Polly.Param[] memory rparams_ = new Polly.Param[](3);

    // Clone the Token721 module
    Token721 token_ = Token721(polly_.cloneModule('Token721', 1));
    rparams_[0]._string = 'Token721';
    rparams_[0]._address = address(token_);
    rparams_[0]._uint = 1;

    // Configure a Meta module
    Polly.Param[] memory meta_params_ = polly_.configureModule(
      'Meta', // module name
      1, // version
      new Polly.Param[](0), // No inputs
      false, // Don't store
      '' // No config name
    );

    token_.setMetaHandler(meta_params_[0]._address);
    token_.grantRole('manager', meta_params_[0]._address);

    Meta meta_ = Meta(meta_params_[0]._address);
    meta_.grantRole('manager', address(token_));

    rparams_[1] = meta_params_[0];


    /// Configure all the Token721Aux modules passed to the configurator
    if(inputs_.length > 0){
      for(uint i = 0; i < inputs_.length; i++){
        token_.registerAux(inputs_[i]._address);
      }
    }


    // Transfer to sender
    _transfer(address(token_), for_);
    _transfer(meta_params_[0]._address, for_);

    return rparams_;

  }


}

// File: contracts/Polly.sol



/*

       -*%%+++*#+:              .+     --
        =@*     *@*           -#@-  .=#%
        %@.      @@:          .@*    :@:
       -@*       @@.          =@.    #*  :=     --
       #@.      =@#  +*+#:    @=    =@: *=%*    *@
      .@*      :@#.-%-  =@   +%    .@*.+  +@    =#
      *@.    .+%= =%.   =@. :@-    *@     =@:   *-
     :@#---===-  -@-    #@  %%    :@-     -@-  .#
     #@:        .@*    .@+ +@:    ##      -@-  #.
    :@%         *@.    *% .@+    :@.      -@- =:
    #@-         @*    -@. +%  =. %+ .=    -@::=
   :@#          @=   -@- .@-==  +@-+-     -@-*
   *@-          #*  *#.  #@*.  :@@+       =@+
.:=++=:.         ===:    +:    :=.        +=
                                         +-
                                       =+.
                                  +*-=+.

v1

*/

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

import "@openzeppelin/contracts/proxy/Clones.sol";
import "@openzeppelin/contracts/access/Ownable.sol";
import "./PollyModule.sol";
import "./PollyConfigurator.sol";
import "./PollyFeeHandler.sol";

/// @title Polly main contract
/// @author polly.tools

/**
 *
 * Polly is a modular smart contract framework that allows anyone to deploy registered modules as proxy contracts onchain.
 * The framework is built and designed by continuousengagement.xyz and is open source.
 */

contract Polly is Ownable {


    enum ModuleType {
        READONLY, CLONE
    }

    enum ParamType {
      UINT, INT, BOOL, STRING, ADDRESS
    }

    /// @dev struct for an uninstantiated module
    struct Module {
      string name;
      uint version;
      address implementation;
      bool clone;
    }

    /// @dev struct for an instantiated module
    struct ModuleInstance {
      string name;
      uint version;
      address location;
    }

    /// @dev struct for a module configuration
    struct Config {
      string name;
      string module;
      uint version;
      Param[] params;
    }

    /// @dev struct for a general type parameter
    struct Param {
      uint _uint;
      int _int;
      bool _bool;
      string _string;
      address _address;
    }


    /// PRIVATE PROPERTIES ///
    string[] private _module_names; // names of registered modules
    mapping(string => mapping(uint => address)) private _modules; // mapping of registered modules and their versions - name => (id => implementation)
    uint private _module_count; // the total number of registered modules
    mapping(string => uint) private _module_versions; // mapping of registered modules and their latest version - name => version
    mapping(address => mapping(uint => Config)) private _configs; // mapping of module configs - owner => (id => config)
    mapping(address => uint) private _configs_count; // mapping of owner config count - owner => count
    mapping(address => bool) private _configurators; // mapping of configurators - address => bool
    PollyFeeHandler private _fee_handler; // fee handler contract
    //////////////////



    /// EVENTS ///
    event moduleUpdated(
      string indexed indexedName, string name, uint version, address indexed implementation
    );

    event moduleCloned(
      string indexed indexedName, string name, uint version, address location
    );

    event moduleConfigured(
      string indexedName, string name, uint version, Polly.Param[] params
    );


    /// CONSTRUCTOR ///

    constructor() {
      _fee_handler = new PollyFeeHandler();
    }


    /// FEE ///
    function fee(address for_, uint value_) public view returns (uint) {
      return _fee_handler.get(for_, value_);
    }


    /// MODULES ///

    /// @dev adds or updates a given module implemenation
    /// @param implementation_ address of the module implementation
    function updateModule(address implementation_) public onlyOwner {

      string memory name_ = PollyModule(implementation_).PMNAME();
      uint version_ = PollyModule(implementation_).PMVERSION();

      require(_modules[name_][version_] == address(0), "MODULE_VERSION_EXISTS");
      require(version_ == _module_versions[name_]+1, "MODULE_VERSION_INVALID");

      _modules[name_][version_] = implementation_; // add module implementation address
      _module_versions[name_] = version_; // update module latest version

      if(version_ == 1)
        _module_names.push(name_); // This is a new module, add to module names mapping

      address configurator_ = getConfigurator(name_, version_); // get configurator address

      if(configurator_ != address(0))
        _configurators[configurator_] = true; // Store the configurator address for this module

      emit moduleUpdated(name_, name_, version_, implementation_); // emit event moduleUpated

    }


    /// @dev retrieves a specific module version base
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return address of the module implementation
    function getModule(string memory name_, uint version_) public view returns(Module memory){

      if(version_ < 1)
        version_ = getLatestModuleVersion(name_); // version_ is 0, get latest version

      require(moduleExists(name_, version_), string(abi.encodePacked('INVALID_MODULE_OR_VERSION: ', name_, '@', Strings.toString(version_))));

      Polly.ModuleType type_ = PollyModule(_modules[name_][version_]).PMTYPE(); // get module info from stored implementation
      bool clone_ = type_ == Polly.ModuleType.CLONE;

      return Module(name_, version_, _modules[name_][version_], clone_); // return module

    }


    /// @dev returns a list of modules available
    /// @param limit_ uint maximum number of modules to return
    /// @param page_ uint page of modules to return
    /// @param ascending_ bool sort modules ascending (true) or descending (false)
    /// @return Module[] array of modules
    function getModules(uint limit_, uint page_, bool ascending_) public view returns(Module[] memory){

      uint count_ = _module_names.length; // get total number of modules

      if(limit_ < 1 || limit_ > count_)
        limit_ = count_; // limit_ is 0, get all modules

      if(page_ < 1)
        page_ = 1; // page_ is 0, get first page

      uint i; // iterator
      uint index_; // index of module name in _module_names


      if(ascending_)
        index_ = page_ == 1 ? 0 : (page_-1)*limit_; // ascending, set index to last module result set
      else
        index_ = page_ == 1 ? count_ : count_ - (limit_*(page_-1)); // descending, set index to first module on result set


      if(
        (ascending_ && index_ >= count_) // ascending, index is greater than total number of modules
        || // or
        (!ascending_ && index_ == 0) // descending, index is 0
      )
        return new Module[](0); // no modules available - bail early


      Module[] memory modules_ = new Module[](limit_); // create array of modules

      if(ascending_){

        // ASCENDING
        while(index_ < limit_){
            modules_[i] = getModule(_module_names[index_], 0);
            ++i;
            ++index_;
        }

      }
      else {

        /// DESCENDING
        while(index_ > 0 && i < limit_){
            modules_[i] = getModule(_module_names[index_-1], 0);
            ++i;
            --index_;
        }

      }


      return modules_; // return modules

    }


    /// @dev retrieves the most recent version number for a module
    /// @param name_ string name of the module
    /// @return uint version number of the module
    function getLatestModuleVersion(string memory name_) public view returns(uint){
      return _module_versions[name_];
    }


    /// @dev check if a module version exists
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return exists_ bool true if module version exists
    function moduleExists(string memory name_, uint version_) public view returns(bool exists_){
      if(_modules[name_][version_] != address(0))
        exists_ = true;
      return exists_;
    }


    /// @dev get the configurator for a given module
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return address of the module configurator
    function getConfigurator(string memory name_, uint version_) public view returns(address){
      return PollyModule(_modules[name_][version_]).configurator();
    }

    /// @dev get the configurator fee for a given module
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return fee_ uint fee in points
    function getConfiguratorFee(address for_, string memory name_, uint version_, Polly.Param[] memory params_) public view returns(uint){

      address conf_address_ = getConfigurator(name_, version_);
      if(conf_address_ == address(0))
        return 0;
      return PollyConfigurator(conf_address_).fee(this, for_, params_);

    }


    /// @dev clone a given module
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return address of the cloned module implementation
    function cloneModule(string memory name_, uint version_) public returns(address) {

      if(version_ == 0)
        version_ = getLatestModuleVersion(name_); // version_ is 0, get latest version

      require(moduleExists(name_, version_), string(abi.encodePacked('INVALID_MODULE_OR_VERSION: ', name_, '@', Strings.toString(version_))));
      require(PollyModule(_modules[name_][version_]).PMTYPE() == Polly.ModuleType.CLONE, 'MODULE_NOT_CLONABLE'); // module is not clonable

      address implementation_ = _modules[name_][version_]; // get module implementation address

      PollyModule module_ = PollyModule(Clones.clone(implementation_)); // clone module implementation
      module_.init(msg.sender); // initialize module


      emit moduleCloned(name_, name_, version_, address(module_)); // emit module cloned event
      return address(module_); // return cloned module address

    }


    /// @dev if a module is configurable run the configurator
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @param params_ array of configuration input parameters
    /// @return rparams_ array of configuration return parameters
    function configureModule(string memory name_, uint version_, Polly.Param[] memory params_, bool store_, string memory config_name_) public payable returns(Polly.Param[] memory rparams_) {

      if(version_ == 0)
        version_ = getLatestModuleVersion(name_); // version_ is 0, get latest version

      Module memory module_ = getModule(name_, version_); // get module
      address configurator_ = PollyModule(module_.implementation).configurator(); // get module configurator address
      require(configurator_ != address(0), 'NO_MODULE_CONFIGURATOR'); // module is not configurable - revert

      PollyConfigurator config_ = PollyConfigurator(configurator_); // get configurator instance

      // Fee
      uint fee_ = config_.fee(this, msg.sender, params_); // get configurator fee info
      if(!_configurators[msg.sender]){
        fee_ = fee_+_fee_handler.get(msg.sender, fee_);
      }

      require(fee_ == msg.value, 'INVALID_FEE');

      // Configure
      rparams_ = config_.run{value: fee_}(this, msg.sender, params_); // run configurator with params

      // Store
      if(store_){

        uint new_count_ = _configs_count[msg.sender] + 1; // get new config count for storing
        _configs[msg.sender][new_count_].name = config_name_; // store config name
        _configs[msg.sender][new_count_].module = name_; // store module name
        _configs[msg.sender][new_count_].version = version_; // store module name

        for (uint i = 0; i < rparams_.length; i++){ // store each config params
          _configs[msg.sender][new_count_].params.push(rparams_[i]);
        }

        _configs_count[msg.sender] = new_count_; // update config count

      }

      emit moduleConfigured(name_, name_, version_, rparams_); // emit module configured event
      return rparams_;  // return configuration params

    }

    /// @dev retrieves the stored configurations for a given address
    /// @param address_ address of the user
    /// @param limit_ maximum number of configurations to return
    /// @param page_ page of configurations to return
    /// @param ascending_ sort configurations ascending (true) or descending (false)
    /// @return PollyConfigurator.Config[] array of configurations
    function getConfigsForAddress(address address_, uint limit_, uint page_, bool ascending_) public view returns(Config[] memory){

      uint count_ = _configs_count[address_]; // get total number of configs for address

      if(limit_ < 1 || limit_ > count_)
        limit_ = count_;  // limit is 0 or greater than total number of configs, set limit to total number of configs

      if(page_ < 1)
        page_ = 1; // page is less than 1, set page to 1

      uint i; // counter
      uint id_; // config id

      if(ascending_)
        id_ = page_ == 1 ? 1 : ((page_-1)*limit_)+1; // calculate ascending start id
      else
        id_ = page_ == 1 ? count_ : count_ - (limit_*(page_-1)); // calculate descending start id


      if(
        (ascending_ && id_ > count_) // ascending and id is greater than total number of configs
        ||
        (!ascending_ && id_ == 0) // descending and id is 0
      )
        return new Config[](0); // no modules available - bail early


      Config[] memory configs_ = new Config[](limit_);  // create array of configs


      if(ascending_){

        // ASCENDING
        while(id_ <= count_ && i < limit_){
            configs_[i] = _configs[address_][id_];
            ++i;
            ++id_;
        }

      }
      else {

        /// DESCENDING
        while(id_ > 0 && i < limit_){
            configs_[i] = _configs[address_][id_];
            ++i;
            --id_;
        }

      }

      return configs_;

    }


    /// @dev retrieve a stored configuration for a given address and config index
    /// @param address_ address of the user
    /// @param index_ index of the configuration
    /// @return Polly.Config configuration
    function getConfigForAddress(address address_, uint index_) public view returns(Config memory){
      require(index_ > 0 && index_ <= _configs_count[address_], 'INVALID_CONFIG_INDEX'); // invalid config index
      return _configs[address_][index_]; // return config
    }


}

// File: contracts/PollyAux.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import "./Polly.sol";

abstract contract PollyAux {

  struct Msg {
    address _sender;
    uint _value;
    bytes _data;
    bytes4 _sig;
  }

  fallback() external {}
  function hooks() external view virtual returns (string[] memory);
  function filter(string memory, uint, Polly.Param memory, Msg memory msg_) external view virtual returns (Polly.Param memory) {}
  function filter(string memory, uint, string memory, Msg memory msg_) external view virtual returns (string memory) {}
  function filter(string memory, uint, uint, Msg memory msg_) external view virtual returns (uint) {}
  function filter(string memory, uint, address, Msg memory msg_) external view virtual returns (address) {}
  function filter(string memory, uint, bool, Msg memory msg_) external view virtual returns (bool) {}

}



abstract contract PollyAuxParent {

  mapping(string => address) internal _aux_hooks;

  function registerAux(address aux_) public virtual;
  function _registerHooks(string[] memory hooks_, address aux_) internal {
    for (uint i = 0; i < hooks_.length; i++){
      _aux_hooks[hooks_[i]] = aux_;
    }
  }

  function getHookAddress(string memory hook_) public view returns (address) {
    return _aux_hooks[hook_];
  }

}

// File: contracts/PollyConfigurator.sol




//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import './Polly.sol';
import './PollyModule.sol';

abstract contract PollyConfigurator {

  string internal constant ADMIN = 'admin';
  string internal constant MANAGER = 'manager';

  function fee(Polly, address, Polly.Param[] memory) public view virtual returns(uint){return 0;}
  function inputs() external view virtual returns (string[] memory){return new string[](0);}
  function outputs() external view virtual returns (string[] memory){return new string[](0);}
  function run(Polly, address, Polly.Param[] memory) external virtual payable returns(Polly.Param[] memory){return new Polly.Param[](0);}

  function _transfer(address module_, address to_) internal {
    _grantAll(to_, module_);
    _revokeAll(address(this), module_);
  }

  function _grantManager(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.grantRole(MANAGER, to_);
  }

  function _grantAdmin(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.grantRole(ADMIN, to_);
  }

  function _grantAll(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.grantRole(ADMIN, to_);
    m_.grantRole(MANAGER, to_);
  }

  function _revokeManager(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.revokeRole(MANAGER, to_);
  }

  function _revokeAdmin(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.revokeRole(ADMIN, to_);
  }

  function _revokeAll(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.revokeRole(MANAGER, to_);
    m_.revokeRole(ADMIN, to_);
  }

}

// File: contracts/PollyFeeHandler.sol



// SPDX-License-Identifier: MIT

pragma solidity ^0.8.4;

contract PollyFeeHandler {

  /// @dev get the fee for a given address and amount
  function get(
    address,
    uint value_
  )
  public pure returns (uint){
    if(value_ == 0)
      return 0;
    return (value_/100)*5;
  }

}

// File: contracts/PollyModule.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import "@openzeppelin/contracts/proxy/Clones.sol";
import "@openzeppelin/contracts/utils/Strings.sol";
import "./Polly.sol";

/// @dev full interface for a PollyModule
interface PollyModule {

  function PMTYPE() external view returns(Polly.ModuleType);
  function PMNAME() external view returns(string memory);
  function PMVERSION() external view returns(uint);

  // Clonable
  function init(address for_) external;
  function didInit() external view returns(bool);
  function configurator() external view returns(address);
  function isManager(address address_) external view returns(bool);

  // Keystore
  function lockKey(string memory key_) external;
  function isLockedKey(string memory key_) external view returns(bool);
  function set(Polly.ParamType type_, string memory key_, Polly.Param memory value_) external;
  function get(string memory key_) external view returns(Polly.Param memory value_);

}


abstract contract PMBase {

  address private _configurator;

  function PMTYPE() external view virtual returns(Polly.ModuleType);
  function PMNAME() external view virtual returns(string memory);
  function PMVERSION() external view virtual returns(uint);

  // Configuration
  function _setConfigurator(address configurator_) internal {
    _configurator = configurator_;
  }

  function configurator() public view returns(address){
    return _configurator;
  }

}


abstract contract PMReadOnly is PMBase {

  Polly.ModuleType public constant override PMTYPE = Polly.ModuleType.READONLY;

}


abstract contract PMClone is PMBase {

  Polly.ModuleType public constant override PMTYPE = Polly.ModuleType.CLONE;

  bool private _did_init = false;

  address private _owner;
  mapping(address => mapping(string => bool)) private _roles;

  modifier onlyRole(string memory role_){
    require(hasRole(role_, msg.sender), string(abi.encodePacked('MISSING_ROLE: ', role_, ' - ', Strings.toHexString(uint160(msg.sender), 20))));
    _;
  }


  // Initialization
  constructor(){
    init(msg.sender);
  }

  function init(address for_) public virtual {
    require(!_did_init, 'ALREADY_INITIALIZED');
    _did_init = true;
    _grantRole('admin', for_);
    _grantRole('manager', for_);
  }

  function didInit() public view returns(bool){
    return _did_init;
  }


  /// Access control

  function _requireRole(string memory role_, address address_) internal view {
    require(hasRole(role_, address_), string(abi.encodePacked('MISSING_ROLE: ', role_, ' - ', Strings.toHexString(uint160(address_), 20))));
  }

  function owner() public view returns(address){
    return _owner;
  }

  function _setOwner(address new_owner_) internal {
    _owner = new_owner_;
    _grantRole('admin', new_owner_);
  }

  function setOwner(address new_owner_) public {
    _requireRole('admin', msg.sender);
    _setOwner(new_owner_);
  }

  function hasRole(string memory role_, address check_) public view returns(bool){
    return _roles[check_][role_];
  }

  function _grantRole(string memory role_, address to_) internal {
    _roles[to_][role_] = true;
  }

  function grantRole(string memory role_, address to_) public {
    _requireRole('admin', msg.sender);
    _grantRole(role_, to_);
  }

  function revokeRole(string memory role_, address to_) public {
    _requireRole('admin', msg.sender);
    _roles[to_][role_] = false;
  }

  function renounceRole(string memory role_) public {
    _requireRole(role_, msg.sender);
    _roles[msg.sender][role_] = false;
  }


}

// File: contracts/PollyToken.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;
import '@openzeppelin/contracts/utils/introspection/ERC165.sol';
import './Polly.sol';
import './PollyAux.sol';
import './modules/Meta.sol';


/// @title IERC2981Royalties
/// @dev Interface for the ERC2981 - Token Royalty standard
interface IERC2981Royalties {
    /// @notice Called with the sale price to determine how much royalty
    //          is owed and to whom.
    /// @param id_ - the NFT asset queried for royalty information
    /// @param value_ - the sale price of the NFT asset specified by id_
    /// @return receiver_ - address of who should be sent the royalty payment
    /// @return amount_ - the royalty payment amount for value sale price
    function royaltyInfo(uint256 id_, uint256 value_)
        external
        view
        returns (address receiver_, uint256 amount_);
}



contract PollyToken is PMClone, PollyAuxParent, ERC165, IERC2981Royalties {

  /// DEFINITIONS

  struct MetaEntry {
    string _key;
    Polly.Param _value;
  }

  Meta internal _meta;

  uint[] internal _tokens;
  uint public highestId;

  event TokenCreated(uint id);


  /// @dev get the name of the module
  function PMNAME() external pure override virtual returns (string memory) {
    return 'PollyToken';
  }

  /// @dev get the version of the module
  function PMVERSION() external pure override virtual returns (uint) {
    return 1;
  }



  function _call(address target_, bytes memory data_) internal returns (bytes memory) {

      (bool success_, bytes memory result_) = target_.call(data_);

      if(!success_){
        if(result_.length < 68) revert();
        assembly {
          result_ := add(result_, 0x04)
        }
        revert(abi.decode(result_, (string)));
      }

      return result_;

  }

  function _staticcall(address target_, bytes memory data_) internal view returns (bytes memory) {

      (bool success_, bytes memory result_) = target_.staticcall(data_);

      if(!success_){
        if(result_.length < 68) revert();
        assembly {
          result_ := add(result_, 0x04)
        }
        revert(abi.decode(result_, (string)));
      }

      return result_;

  }


  /////////////////////////
  // AUX
  /////////////////////////

  /// @dev register aux
  /// @param aux_ the aux to register
  function registerAux(address aux_) public override virtual {
    _requireRole('admin', msg.sender);
    _registerHooks(PollyAux(aux_).hooks(), aux_);
  }


  /////////////////////////
  // META
  /////////////////////////


  /// @dev set meta handler
  /// @param handler_ the address of the meta handler
  function setMetaHandler(address handler_) public {
    _requireRole('admin', msg.sender);
    require(address(_meta) == address(0), 'META_HANDLER_SET');
    _meta = Meta(handler_);
  }


  /// @dev get meta handler attached to this contract
  function getMetaHandler() public view returns (Meta) {
    return _meta;
  }


  function getMeta(uint id_, string memory key_) public view returns (Polly.Param memory) {

    // Check for token specific filter
    string memory hook_ = string(abi.encodePacked('filter_Meta_', key_));
    address filter_ = getHookAddress(hook_);

    Polly.Param memory meta_ = _meta.get(id_, key_);

    if(filter_ != address(0)){
      bytes memory data_ = _staticcall(filter_, abi.encodeWithSignature(string(abi.encodePacked(hook_, '(uint256,(uint256,int256,bool,string,address))')), id_, _meta.get(id_, key_)));
      meta_ = abi.decode(data_, (Polly.Param));
    }

    return meta_;

  }




  /////////////////////////
  // TOKENS
  /////////////////////////


  /// @dev create a new token
  function _createToken(MetaEntry[] memory meta_) internal returns (uint) {

    uint id_ = highestId + 1;

    address hook_ = getHookAddress('action_BeforeCreateToken');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_BeforeCreateToken(uint256,(uint256,int256,bool,string,address)[])', id_, meta_));

    for(uint i = 0; i < meta_.length; i++) {
      _meta.set(id_, meta_[i]._key, meta_[i]._value);
    }

    _tokens.push(id_);
    _meta.setBool(id_, 'created', true);
    _meta.lockIdKey(id_, 'created');

    hook_ = getHookAddress('action_AfterCreateToken');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_AfterCreateToken(uint256)', id_, meta_));

    emit TokenCreated(id_);
    if(id_ > highestId) highestId = id_;
    return id_;

  }


  function getTokens(uint limit_, uint page_) public view returns (uint[] memory) {

    uint[] memory tokens_ = new uint[](limit_);
    uint count_ = 0;
    uint offset_ = page_ > 1 ? page_-1 * limit_ : 0;
    for(uint i = offset_; i < _tokens.length; i++){
      if(count_ == limit_) break;
      tokens_[count_] = _tokens[i];
      count_++;
    }

    return tokens_;

  }


  function _tokenUri(uint id_) internal view returns (string memory){
    return getMeta(id_, 'tokenUri')._string;
  }




  /////////////////////////
  // MISC
  /////////////////////////



  /// @dev get the contract metadata uri
  function contractURI() public view returns(string memory) {
    return getMeta(0, 'collectionUri')._string;
  }


  /// @dev get the royalty info
  /// @param id_ the id of the token
  /// @param value_ the value of the sale
  function royaltyInfo(uint id_, uint value_) public view override returns (address recipient_, uint amount_) {

     // Get royalty base and recipient for the token
    uint base_ = getMeta(id_, 'royaltyBase')._uint;
    recipient_ = getMeta(id_, 'royaltyRecipient')._address;

    // Use default royalty if no royalty is set for the token
    if(base_ == 0 && getMeta(0, 'royaltyBase')._uint > 0)
      base_ = getMeta(0, 'royaltyBase')._uint;

    // Use default recipient if no recipient is set for the token
    if(recipient_ == address(0) && getMeta(0, 'royaltyRecipient')._address != address(0))
      recipient_ = getMeta(0, 'royaltyRecipient')._address;

    // If either base or recipient is not set, return 0
    if(base_ == 0 || recipient_ == address(0) || value_ == 0)
      return (recipient_, 0);

    // Limit base to 10000 (100%)
    if(base_ > 10000)
      base_ = 10000;

    // Calculate and return royalty
    return (recipient_, (value_ * base_) / 10000);

  }


  // Withdraw all ETH from this contract
  function withdraw() public {
    _requireRole('admin', msg.sender);
    payable(msg.sender).transfer(address(this).balance);
  }


  function _postMintTransfer(uint id_, uint amount_) internal {

    // Send msg.value to the recipient address for token
    if(amount_ > 0){

      Meta meta_ = getMetaHandler();
      // Check if the token has a recipient address
      address recipient_ = meta_.getAddress(id_, 'collectionRecipient');
      // If not, check if contract has a recipient address
      if(recipient_ == address(0))
        recipient_ = meta_.getAddress(0, 'collectionRecipient');

      if(recipient_ != address(0))
        payable(recipient_).transfer(amount_);

    }

  }


  /// Override
  function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool){
      return interfaceId == type(IERC2981Royalties).interfaceId;
  }


}