// File: @openzeppelin/contracts-upgradeable/access/OwnableUpgradeable.sol



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

pragma solidity ^0.8.0;

import "../utils/ContextUpgradeable.sol";
import "../proxy/utils/Initializable.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 OwnableUpgradeable is Initializable, ContextUpgradeable {
    address private _owner;

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

    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    function __Ownable_init() internal onlyInitializing {
        __Ownable_init_unchained();
    }

    function __Ownable_init_unchained() internal onlyInitializing {
        _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);
    }

    /**
     * @dev This empty reserved space is put in place to allow future versions to add new
     * variables without shifting down storage in the inheritance chain.
     * See https://docs.openzeppelin.com/contracts/4.x/upgradeable#storage_gaps
     */
    uint256[49] private __gap;
}

// File: @openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.1) (proxy/utils/Initializable.sol)

pragma solidity ^0.8.2;

import "../../utils/AddressUpgradeable.sol";

/**
 * @dev This is a base contract to aid in writing upgradeable contracts, or any kind of contract that will be deployed
 * behind a proxy. Since proxied contracts do not make use of a constructor, it's common to move constructor logic to an
 * external initializer function, usually called `initialize`. It then becomes necessary to protect this initializer
 * function so it can only be called once. The {initializer} modifier provided by this contract will have this effect.
 *
 * The initialization functions use a version number. Once a version number is used, it is consumed and cannot be
 * reused. This mechanism prevents re-execution of each "step" but allows the creation of new initialization steps in
 * case an upgrade adds a module that needs to be initialized.
 *
 * For example:
 *
 * [.hljs-theme-light.nopadding]
 * ```
 * contract MyToken is ERC20Upgradeable {
 *     function initialize() initializer public {
 *         __ERC20_init("MyToken", "MTK");
 *     }
 * }
 * contract MyTokenV2 is MyToken, ERC20PermitUpgradeable {
 *     function initializeV2() reinitializer(2) public {
 *         __ERC20Permit_init("MyToken");
 *     }
 * }
 * ```
 *
 * TIP: To avoid leaving the proxy in an uninitialized state, the initializer function should be called as early as
 * possible by providing the encoded function call as the `_data` argument to {ERC1967Proxy-constructor}.
 *
 * CAUTION: When used with inheritance, manual care must be taken to not invoke a parent initializer twice, or to ensure
 * that all initializers are idempotent. This is not verified automatically as constructors are by Solidity.
 *
 * [CAUTION]
 * ====
 * Avoid leaving a contract uninitialized.
 *
 * An uninitialized contract can be taken over by an attacker. This applies to both a proxy and its implementation
 * contract, which may impact the proxy. To prevent the implementation contract from being used, you should invoke
 * the {_disableInitializers} function in the constructor to automatically lock it when it is deployed:
 *
 * [.hljs-theme-light.nopadding]
 * ```
 * /// @custom:oz-upgrades-unsafe-allow constructor
 * constructor() {
 *     _disableInitializers();
 * }
 * ```
 * ====
 */
abstract contract Initializable {
    /**
     * @dev Indicates that the contract has been initialized.
     * @custom:oz-retyped-from bool
     */
    uint8 private _initialized;

    /**
     * @dev Indicates that the contract is in the process of being initialized.
     */
    bool private _initializing;

    /**
     * @dev Triggered when the contract has been initialized or reinitialized.
     */
    event Initialized(uint8 version);

    /**
     * @dev A modifier that defines a protected initializer function that can be invoked at most once. In its scope,
     * `onlyInitializing` functions can be used to initialize parent contracts.
     *
     * Similar to `reinitializer(1)`, except that functions marked with `initializer` can be nested in the context of a
     * constructor.
     *
     * Emits an {Initialized} event.
     */
    modifier initializer() {
        bool isTopLevelCall = !_initializing;
        require(
            (isTopLevelCall && _initialized < 1) || (!AddressUpgradeable.isContract(address(this)) && _initialized == 1),
            "Initializable: contract is already initialized"
        );
        _initialized = 1;
        if (isTopLevelCall) {
            _initializing = true;
        }
        _;
        if (isTopLevelCall) {
            _initializing = false;
            emit Initialized(1);
        }
    }

    /**
     * @dev A modifier that defines a protected reinitializer function that can be invoked at most once, and only if the
     * contract hasn't been initialized to a greater version before. In its scope, `onlyInitializing` functions can be
     * used to initialize parent contracts.
     *
     * A reinitializer may be used after the original initialization step. This is essential to configure modules that
     * are added through upgrades and that require initialization.
     *
     * When `version` is 1, this modifier is similar to `initializer`, except that functions marked with `reinitializer`
     * cannot be nested. If one is invoked in the context of another, execution will revert.
     *
     * Note that versions can jump in increments greater than 1; this implies that if multiple reinitializers coexist in
     * a contract, executing them in the right order is up to the developer or operator.
     *
     * WARNING: setting the version to 255 will prevent any future reinitialization.
     *
     * Emits an {Initialized} event.
     */
    modifier reinitializer(uint8 version) {
        require(!_initializing && _initialized < version, "Initializable: contract is already initialized");
        _initialized = version;
        _initializing = true;
        _;
        _initializing = false;
        emit Initialized(version);
    }

    /**
     * @dev Modifier to protect an initialization function so that it can only be invoked by functions with the
     * {initializer} and {reinitializer} modifiers, directly or indirectly.
     */
    modifier onlyInitializing() {
        require(_initializing, "Initializable: contract is not initializing");
        _;
    }

    /**
     * @dev Locks the contract, preventing any future reinitialization. This cannot be part of an initializer call.
     * Calling this in the constructor of a contract will prevent that contract from being initialized or reinitialized
     * to any version. It is recommended to use this to lock implementation contracts that are designed to be called
     * through proxies.
     *
     * Emits an {Initialized} event the first time it is successfully executed.
     */
    function _disableInitializers() internal virtual {
        require(!_initializing, "Initializable: contract is initializing");
        if (_initialized < type(uint8).max) {
            _initialized = type(uint8).max;
            emit Initialized(type(uint8).max);
        }
    }

    /**
     * @dev Returns the highest version that has been initialized. See {reinitializer}.
     */
    function _getInitializedVersion() internal view returns (uint8) {
        return _initialized;
    }

    /**
     * @dev Returns `true` if the contract is currently initializing. See {onlyInitializing}.
     */
    function _isInitializing() internal view returns (bool) {
        return _initializing;
    }
}

// File: @openzeppelin/contracts-upgradeable/utils/AddressUpgradeable.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 AddressUpgradeable {
    /**
     * @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 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-upgradeable/utils/ContextUpgradeable.sol



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

pragma solidity ^0.8.0;
import "../proxy/utils/Initializable.sol";

/**
 * @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 ContextUpgradeable is Initializable {
    function __Context_init() internal onlyInitializing {
    }

    function __Context_init_unchained() internal onlyInitializing {
    }
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }

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

    /**
     * @dev This empty reserved space is put in place to allow future versions to add new
     * variables without shifting down storage in the inheritance chain.
     * See https://docs.openzeppelin.com/contracts/4.x/upgradeable#storage_gaps
     */
    uint256[50] private __gap;
}

// File: @openzeppelin/contracts/token/ERC1155/IERC1155.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (token/ERC1155/IERC1155.sol)

pragma solidity ^0.8.0;

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

/**
 * @dev Required interface of an ERC1155 compliant contract, as defined in the
 * https://eips.ethereum.org/EIPS/eip-1155[EIP].
 *
 * _Available since v3.1._
 */
interface IERC1155 is IERC165 {
    /**
     * @dev Emitted when `value` tokens of token type `id` are transferred from `from` to `to` by `operator`.
     */
    event TransferSingle(address indexed operator, address indexed from, address indexed to, uint256 id, uint256 value);

    /**
     * @dev Equivalent to multiple {TransferSingle} events, where `operator`, `from` and `to` are the same for all
     * transfers.
     */
    event TransferBatch(
        address indexed operator,
        address indexed from,
        address indexed to,
        uint256[] ids,
        uint256[] values
    );

    /**
     * @dev Emitted when `account` grants or revokes permission to `operator` to transfer their tokens, according to
     * `approved`.
     */
    event ApprovalForAll(address indexed account, address indexed operator, bool approved);

    /**
     * @dev Emitted when the URI for token type `id` changes to `value`, if it is a non-programmatic URI.
     *
     * If an {URI} event was emitted for `id`, the standard
     * https://eips.ethereum.org/EIPS/eip-1155#metadata-extensions[guarantees] that `value` will equal the value
     * returned by {IERC1155MetadataURI-uri}.
     */
    event URI(string value, uint256 indexed id);

    /**
     * @dev Returns the amount of tokens of token type `id` owned by `account`.
     *
     * Requirements:
     *
     * - `account` cannot be the zero address.
     */
    function balanceOf(address account, uint256 id) external view returns (uint256);

    /**
     * @dev xref:ROOT:erc1155.adoc#batch-operations[Batched] version of {balanceOf}.
     *
     * Requirements:
     *
     * - `accounts` and `ids` must have the same length.
     */
    function balanceOfBatch(address[] calldata accounts, uint256[] calldata ids)
        external
        view
        returns (uint256[] memory);

    /**
     * @dev Grants or revokes permission to `operator` to transfer the caller's tokens, according to `approved`,
     *
     * Emits an {ApprovalForAll} event.
     *
     * Requirements:
     *
     * - `operator` cannot be the caller.
     */
    function setApprovalForAll(address operator, bool approved) external;

    /**
     * @dev Returns true if `operator` is approved to transfer ``account``'s tokens.
     *
     * See {setApprovalForAll}.
     */
    function isApprovedForAll(address account, address operator) external view returns (bool);

    /**
     * @dev Transfers `amount` tokens of token type `id` from `from` to `to`.
     *
     * Emits a {TransferSingle} event.
     *
     * Requirements:
     *
     * - `to` cannot be the zero address.
     * - If the caller is not `from`, it must have been approved to spend ``from``'s tokens via {setApprovalForAll}.
     * - `from` must have a balance of tokens of type `id` of at least `amount`.
     * - If `to` refers to a smart contract, it must implement {IERC1155Receiver-onERC1155Received} and return the
     * acceptance magic value.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 id,
        uint256 amount,
        bytes calldata data
    ) external;

    /**
     * @dev xref:ROOT:erc1155.adoc#batch-operations[Batched] version of {safeTransferFrom}.
     *
     * Emits a {TransferBatch} event.
     *
     * Requirements:
     *
     * - `ids` and `amounts` must have the same length.
     * - If `to` refers to a smart contract, it must implement {IERC1155Receiver-onERC1155BatchReceived} and return the
     * acceptance magic value.
     */
    function safeBatchTransferFrom(
        address from,
        address to,
        uint256[] calldata ids,
        uint256[] calldata amounts,
        bytes calldata data
    ) external;
}

// File: @openzeppelin/contracts/token/ERC1155/IERC1155Receiver.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.5.0) (token/ERC1155/IERC1155Receiver.sol)

pragma solidity ^0.8.0;

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

/**
 * @dev _Available since v3.1._
 */
interface IERC1155Receiver is IERC165 {
    /**
     * @dev Handles the receipt of a single ERC1155 token type. This function is
     * called at the end of a `safeTransferFrom` after the balance has been updated.
     *
     * NOTE: To accept the transfer, this must return
     * `bytes4(keccak256("onERC1155Received(address,address,uint256,uint256,bytes)"))`
     * (i.e. 0xf23a6e61, or its own function selector).
     *
     * @param operator The address which initiated the transfer (i.e. msg.sender)
     * @param from The address which previously owned the token
     * @param id The ID of the token being transferred
     * @param value The amount of tokens being transferred
     * @param data Additional data with no specified format
     * @return `bytes4(keccak256("onERC1155Received(address,address,uint256,uint256,bytes)"))` if transfer is allowed
     */
    function onERC1155Received(
        address operator,
        address from,
        uint256 id,
        uint256 value,
        bytes calldata data
    ) external returns (bytes4);

    /**
     * @dev Handles the receipt of a multiple ERC1155 token types. This function
     * is called at the end of a `safeBatchTransferFrom` after the balances have
     * been updated.
     *
     * NOTE: To accept the transfer(s), this must return
     * `bytes4(keccak256("onERC1155BatchReceived(address,address,uint256[],uint256[],bytes)"))`
     * (i.e. 0xbc197c81, or its own function selector).
     *
     * @param operator The address which initiated the batch transfer (i.e. msg.sender)
     * @param from The address which previously owned the token
     * @param ids An array containing ids of each token being transferred (order and length must match values array)
     * @param values An array containing amounts of each token being transferred (order and length must match ids array)
     * @param data Additional data with no specified format
     * @return `bytes4(keccak256("onERC1155BatchReceived(address,address,uint256[],uint256[],bytes)"))` if transfer is allowed
     */
    function onERC1155BatchReceived(
        address operator,
        address from,
        uint256[] calldata ids,
        uint256[] calldata values,
        bytes calldata data
    ) external returns (bytes4);
}

// 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/cryptography/ECDSA.sol



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

pragma solidity ^0.8.0;

import "../Strings.sol";

/**
 * @dev Elliptic Curve Digital Signature Algorithm (ECDSA) operations.
 *
 * These functions can be used to verify that a message was signed by the holder
 * of the private keys of a given address.
 */
library ECDSA {
    enum RecoverError {
        NoError,
        InvalidSignature,
        InvalidSignatureLength,
        InvalidSignatureS,
        InvalidSignatureV // Deprecated in v4.8
    }

    function _throwError(RecoverError error) private pure {
        if (error == RecoverError.NoError) {
            return; // no error: do nothing
        } else if (error == RecoverError.InvalidSignature) {
            revert("ECDSA: invalid signature");
        } else if (error == RecoverError.InvalidSignatureLength) {
            revert("ECDSA: invalid signature length");
        } else if (error == RecoverError.InvalidSignatureS) {
            revert("ECDSA: invalid signature 's' value");
        }
    }

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with
     * `signature` or error string. This address can then be used for verification purposes.
     *
     * The `ecrecover` EVM opcode allows for malleable (non-unique) signatures:
     * this function rejects them by requiring the `s` value to be in the lower
     * half order, and the `v` value to be either 27 or 28.
     *
     * IMPORTANT: `hash` _must_ be the result of a hash operation for the
     * verification to be secure: it is possible to craft signatures that
     * recover to arbitrary addresses for non-hashed data. A safe way to ensure
     * this is by receiving a hash of the original message (which may otherwise
     * be too long), and then calling {toEthSignedMessageHash} on it.
     *
     * Documentation for signature generation:
     * - with https://web3js.readthedocs.io/en/v1.3.4/web3-eth-accounts.html#sign[Web3.js]
     * - with https://docs.ethers.io/v5/api/signer/#Signer-signMessage[ethers]
     *
     * _Available since v4.3._
     */
    function tryRecover(bytes32 hash, bytes memory signature) internal pure returns (address, RecoverError) {
        if (signature.length == 65) {
            bytes32 r;
            bytes32 s;
            uint8 v;
            // ecrecover takes the signature parameters, and the only way to get them
            // currently is to use assembly.
            /// @solidity memory-safe-assembly
            assembly {
                r := mload(add(signature, 0x20))
                s := mload(add(signature, 0x40))
                v := byte(0, mload(add(signature, 0x60)))
            }
            return tryRecover(hash, v, r, s);
        } else {
            return (address(0), RecoverError.InvalidSignatureLength);
        }
    }

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with
     * `signature`. This address can then be used for verification purposes.
     *
     * The `ecrecover` EVM opcode allows for malleable (non-unique) signatures:
     * this function rejects them by requiring the `s` value to be in the lower
     * half order, and the `v` value to be either 27 or 28.
     *
     * IMPORTANT: `hash` _must_ be the result of a hash operation for the
     * verification to be secure: it is possible to craft signatures that
     * recover to arbitrary addresses for non-hashed data. A safe way to ensure
     * this is by receiving a hash of the original message (which may otherwise
     * be too long), and then calling {toEthSignedMessageHash} on it.
     */
    function recover(bytes32 hash, bytes memory signature) internal pure returns (address) {
        (address recovered, RecoverError error) = tryRecover(hash, signature);
        _throwError(error);
        return recovered;
    }

    /**
     * @dev Overload of {ECDSA-tryRecover} that receives the `r` and `vs` short-signature fields separately.
     *
     * See https://eips.ethereum.org/EIPS/eip-2098[EIP-2098 short signatures]
     *
     * _Available since v4.3._
     */
    function tryRecover(
        bytes32 hash,
        bytes32 r,
        bytes32 vs
    ) internal pure returns (address, RecoverError) {
        bytes32 s = vs & bytes32(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff);
        uint8 v = uint8((uint256(vs) >> 255) + 27);
        return tryRecover(hash, v, r, s);
    }

    /**
     * @dev Overload of {ECDSA-recover} that receives the `r and `vs` short-signature fields separately.
     *
     * _Available since v4.2._
     */
    function recover(
        bytes32 hash,
        bytes32 r,
        bytes32 vs
    ) internal pure returns (address) {
        (address recovered, RecoverError error) = tryRecover(hash, r, vs);
        _throwError(error);
        return recovered;
    }

    /**
     * @dev Overload of {ECDSA-tryRecover} that receives the `v`,
     * `r` and `s` signature fields separately.
     *
     * _Available since v4.3._
     */
    function tryRecover(
        bytes32 hash,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) internal pure returns (address, RecoverError) {
        // EIP-2 still allows signature malleability for ecrecover(). Remove this possibility and make the signature
        // unique. Appendix F in the Ethereum Yellow paper (https://ethereum.github.io/yellowpaper/paper.pdf), defines
        // the valid range for s in (301): 0 < s < secp256k1n ÷ 2 + 1, and for v in (302): v ∈ {27, 28}. Most
        // signatures from current libraries generate a unique signature with an s-value in the lower half order.
        //
        // If your library generates malleable signatures, such as s-values in the upper range, calculate a new s-value
        // with 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 - s1 and flip v from 27 to 28 or
        // vice versa. If your library also generates signatures with 0/1 for v instead 27/28, add 27 to v to accept
        // these malleable signatures as well.
        if (uint256(s) > 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0) {
            return (address(0), RecoverError.InvalidSignatureS);
        }

        // If the signature is valid (and not malleable), return the signer address
        address signer = ecrecover(hash, v, r, s);
        if (signer == address(0)) {
            return (address(0), RecoverError.InvalidSignature);
        }

        return (signer, RecoverError.NoError);
    }

    /**
     * @dev Overload of {ECDSA-recover} that receives the `v`,
     * `r` and `s` signature fields separately.
     */
    function recover(
        bytes32 hash,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) internal pure returns (address) {
        (address recovered, RecoverError error) = tryRecover(hash, v, r, s);
        _throwError(error);
        return recovered;
    }

    /**
     * @dev Returns an Ethereum Signed Message, created from a `hash`. This
     * produces hash corresponding to the one signed with the
     * https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`]
     * JSON-RPC method as part of EIP-191.
     *
     * See {recover}.
     */
    function toEthSignedMessageHash(bytes32 hash) internal pure returns (bytes32) {
        // 32 is the length in bytes of hash,
        // enforced by the type signature above
        return keccak256(abi.encodePacked("\x19Ethereum Signed Message:\n32", hash));
    }

    /**
     * @dev Returns an Ethereum Signed Message, created from `s`. This
     * produces hash corresponding to the one signed with the
     * https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`]
     * JSON-RPC method as part of EIP-191.
     *
     * See {recover}.
     */
    function toEthSignedMessageHash(bytes memory s) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked("\x19Ethereum Signed Message:\n", Strings.toString(s.length), s));
    }

    /**
     * @dev Returns an Ethereum Signed Typed Data, created from a
     * `domainSeparator` and a `structHash`. This produces hash corresponding
     * to the one signed with the
     * https://eips.ethereum.org/EIPS/eip-712[`eth_signTypedData`]
     * JSON-RPC method as part of EIP-712.
     *
     * See {recover}.
     */
    function toTypedDataHash(bytes32 domainSeparator, bytes32 structHash) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked("\x19\x01", domainSeparator, structHash));
    }
}

// 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/distributors/Distributooor.sol



// SPDX-License-Identifier: BUSL-1.1
pragma solidity 0.8.17;

import {Strings} from "@openzeppelin/contracts/utils/Strings.sol";
import {IERC721} from "@openzeppelin/contracts/token/ERC721/IERC721.sol";
import {IERC1155} from "@openzeppelin/contracts/token/ERC1155/IERC1155.sol";
import {IERC721Receiver} from "@openzeppelin/contracts/token/ERC721/IERC721Receiver.sol";
import {IERC1155Receiver} from "@openzeppelin/contracts/token/ERC1155/IERC1155Receiver.sol";
import {Initializable} from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import {OwnableUpgradeable} from "@openzeppelin/contracts-upgradeable/access/OwnableUpgradeable.sol";
import {ECDSA} from "@openzeppelin/contracts/utils/cryptography/ECDSA.sol";
import {IRaffleChef} from "../interfaces/IRaffleChef.sol";
import {TypeAndVersion} from "../interfaces/TypeAndVersion.sol";
import {IRandomiser} from "../interfaces/IRandomiser.sol";
import {IRandomiserCallback} from "../interfaces/IRandomiserCallback.sol";
import {IDistributooor} from "../interfaces/IDistributooor.sol";
import {IDistributooorFactory} from "../interfaces/IDistributooorFactory.sol";

// solhint-disable not-rely-on-time
// solhint-disable no-inline-assembly

/// @title Distributooor
/// @notice Base contract that implements helpers to consume a raffle from a
///     {RaffleChef}. Keeps track of participants that have claimed a winning
///     (and prevents them from claiming twice).
contract Distributooor is
    IDistributooor,
    IERC721Receiver,
    IERC1155Receiver,
    IRandomiserCallback,
    TypeAndVersion,
    Initializable,
    OwnableUpgradeable
{
    using Strings for uint256;
    using Strings for address;

    /// @notice Type of prize
    enum PrizeType {
        ERC721,
        ERC1155
    }

    address public distributooorFactory;
    /// @notice {RaffleChef} instance to consume
    address public raffleChef;
    /// @notice Raffle ID corresponding to a raffle in {RaffleChef}
    uint256 public raffleId;
    /// @notice Randomiser
    address public randomiser;
    /// @notice Track whether a given leaf (representing a participant) has
    /// claimed or not
    mapping(bytes32 => bool) public hasClaimed;

    /// @notice Array of bytes representing prize data
    bytes[] private prizes;

    /// @notice Due date (block timestamp) after which the raffle is allowed
    ///     to be performed. CANNOT be changed after initialisation.
    uint256 public raffleActivationTimestamp;
    /// @notice The block timestamp after which the owner may reclaim the
    ///     prizes from this contract. CANNOT be changed after initialisation.
    uint256 public prizeExpiryTimestamp;

    /// @notice Committed merkle root from collector
    bytes32 public merkleRoot;
    /// @notice Commited number of entries from collector
    uint256 public nParticipants;
    /// @notice Committed provenance
    string public provenance;

    /// @notice VRF request ID
    uint256 public randRequestId;
    /// @notice Timestamp of last VRF requesst
    uint256 public lastRandRequest;

    uint256[37] private __Distributooor_gap;

    event Claimed(
        address claimooor,
        uint256 originalIndex,
        uint256 permutedIndex
    );

    error ERC721NotReceived(address nftContract, uint256 tokenId);
    error ERC1155NotReceived(
        address nftContract,
        uint256 tokenId,
        uint256 amount
    );
    error InvalidPrizeType(uint8 prizeType);
    error InvalidTimestamp(uint256 timestamp);
    error RaffleActivationPending(uint256 secondsLeft);
    error PrizeExpiryTimestampPending(uint256 secondsLeft);
    error IncorrectSignatureLength(uint256 sigLength);
    error InvalidRandomWords(uint256[] randomWords);
    error RandomnessAlreadySet(
        uint256 existingRandomness,
        uint256 newRandomness
    );
    error UnknownRandomiser(address randomiser);
    error RandomRequestInFlight(uint256 requestId);

    constructor() {
        _disableInitializers();
    }

    function init(
        address raffleOwner,
        address raffleChef_,
        address randomiser_,
        uint256 raffleActivationTimestamp_,
        uint256 prizeExpiryTimestamp_
    ) public initializer {
        bool isActivationInThePast = raffleActivationTimestamp_ <=
            block.timestamp;
        bool isActivationOnOrAfterExpiry = raffleActivationTimestamp_ >=
            prizeExpiryTimestamp_;
        bool isClaimDurationTooShort = prizeExpiryTimestamp_ -
            raffleActivationTimestamp_ <
            1 hours;
        if (
            raffleActivationTimestamp_ == 0 ||
            isActivationInThePast ||
            isActivationOnOrAfterExpiry ||
            isClaimDurationTooShort
        ) {
            revert InvalidTimestamp(raffleActivationTimestamp_);
        }
        if (prizeExpiryTimestamp_ == 0) {
            revert InvalidTimestamp(prizeExpiryTimestamp_);
        }

        __Ownable_init();
        _transferOwnership(raffleOwner);

        // Assumes that the DistributooorFactory is the deployer
        distributooorFactory = _msgSender();
        raffleChef = raffleChef_;
        randomiser = randomiser_;
        raffleActivationTimestamp = raffleActivationTimestamp_;
        prizeExpiryTimestamp = prizeExpiryTimestamp_;
    }

    /// @notice See {TypeAndVersion-typeAndVersion}
    function typeAndVersion()
        external
        pure
        virtual
        override
        returns (string memory)
    {
        return "Distributooor 1.1.0";
    }

    /// @notice {IERC165-supportsInterface}
    function supportsInterface(
        bytes4 interfaceId
    ) public view virtual override returns (bool) {
        return
            interfaceId == type(TypeAndVersion).interfaceId ||
            interfaceId == type(IERC721Receiver).interfaceId ||
            interfaceId == type(IERC1155Receiver).interfaceId;
    }

    /// @notice Revert if raffle has not yet been finalised
    modifier onlyCommittedRaffle() {
        uint256 raffleId_ = raffleId;
        require(
            raffleId_ != 0 &&
                IRaffleChef(raffleChef).getRaffleState(raffleId_) ==
                IRaffleChef.RaffleState.Committed,
            "Raffle is not yet finalised"
        );
        _;
    }

    /// @notice Revert if raffle has not yet reached activation
    modifier onlyAfterActivation() {
        if (!isReadyForActivation()) {
            revert RaffleActivationPending(
                raffleActivationTimestamp - block.timestamp
            );
        }
        _;
    }

    /// @notice Revert if raffle has not passed its deadline
    modifier onlyAfterExpiry() {
        if (!isPrizeExpired()) {
            revert PrizeExpiryTimestampPending(
                prizeExpiryTimestamp - block.timestamp
            );
        }
        _;
    }

    modifier onlyFactory() {
        if (_msgSender() != distributooorFactory) {
            revert Unauthorised(_msgSender());
        }
        _;
    }

    function isReadyForActivation() public view returns (bool) {
        return block.timestamp >= raffleActivationTimestamp;
    }

    function isPrizeExpired() public view returns (bool) {
        return block.timestamp >= prizeExpiryTimestamp;
    }

    /// @notice Verify that a proof is valid, and that it is part of the set of
    ///     winners. Revert otherwise. A winner is defined as an account that
    ///     has a shuffled index x' s.t. x' < nWinners
    /// @param leaf The leaf value representing the participant
    /// @param index Index of account in original participants list
    /// @param proof Merkle proof of inclusion of account in original
    ///     participants list
    /// @return permuted index
    function _verifyAndRecordClaim(
        bytes32 leaf,
        uint256 index,
        bytes32[] memory proof
    ) internal virtual onlyCommittedRaffle returns (uint256) {
        (bool isWinner, uint256 permutedIndex) = IRaffleChef(raffleChef)
            .verifyRaffleWinner(raffleId, leaf, proof, index);
        // Nullifier identifies a unique entry in the merkle tree
        bytes32 nullifier = keccak256(abi.encode(leaf, index));
        require(isWinner, "Not a raffle winner");
        require(!hasClaimed[nullifier], "Already claimed");
        hasClaimed[nullifier] = true;
        return permutedIndex;
    }

    /// @notice Check if preimage of `leaf` is a winner
    /// @param leaf Hash of entry
    /// @param index Index of account in original participants list
    /// @param proof Merkle proof of inclusion of account in original
    ///     participants list
    function check(
        bytes32 leaf,
        uint256 index,
        bytes32[] calldata proof
    )
        external
        view
        onlyCommittedRaffle
        returns (bool isWinner, uint256 permutedIndex)
    {
        (isWinner, permutedIndex) = IRaffleChef(raffleChef).verifyRaffleWinner(
            raffleId,
            leaf,
            proof,
            index
        );
    }

    function checkSig(
        address expectedSigner,
        bytes32 messageHash,
        bytes calldata signature
    ) public pure returns (bool, address) {
        // signature should be in the format (r,s,v)
        address recoveredSigner = ECDSA.recover(messageHash, signature);
        bool isValid = expectedSigner == recoveredSigner;
        return (isValid, recoveredSigner);
    }

    /// @notice Claim a prize from the contract. The caller must be included in
    ///     the Merkle tree of participants.
    /// @param index IndpermutedIndexccount in original participants list
    /// @param proof Merkle proof of inclusion of account in original
    ///     participants list
    function claim(
        uint256 index,
        bytes32[] calldata proof
    ) external onlyCommittedRaffle {
        address claimooor = _msgSender();
        bytes32 hashedLeaf = keccak256(abi.encodePacked(claimooor));

        uint256 permutedIndex = _verifyAndRecordClaim(hashedLeaf, index, proof);

        // Decode the prize & transfer it to claimooor
        bytes memory rawPrize = prizes[permutedIndex];
        PrizeType prizeType = _getPrizeType(rawPrize);
        if (prizeType == PrizeType.ERC721) {
            (address nftContract, uint256 tokenId) = _getERC721Prize(rawPrize);
            IERC721(nftContract).safeTransferFrom(
                address(this),
                claimooor,
                tokenId
            );
        } else if (prizeType == PrizeType.ERC1155) {
            (
                address nftContract,
                uint256 tokenId,
                uint256 amount
            ) = _getERC1155Prize(rawPrize);
            IERC1155(nftContract).safeTransferFrom(
                address(this),
                claimooor,
                tokenId,
                amount,
                bytes("")
            );
        }

        emit Claimed(claimooor, index, permutedIndex);
    }

    function requestMerkleRoot(
        uint256 chainId,
        address collectooorFactory,
        address collectooor
    ) external onlyAfterActivation onlyOwner {
        IDistributooorFactory(distributooorFactory).requestMerkleRoot(
            chainId,
            collectooorFactory,
            collectooor
        );
    }

    /// @notice See {IDistributooor-receiveParticipantsMerkleRoot}
    function receiveParticipantsMerkleRoot(
        uint256 srcChainId,
        address srcCollector,
        uint256 blockNumber,
        bytes32 merkleRoot_,
        uint256 nParticipants_
    ) external onlyAfterActivation onlyFactory {
        if (raffleId != 0 || merkleRoot != 0 || nParticipants != 0) {
            // Only allow merkle root to be received once;
            // otherwise it's already finalised
            revert MerkleRootRejected(merkleRoot_, nParticipants_, blockNumber);
        }
        if (randRequestId != 0 && block.timestamp - lastRandRequest < 1 hours) {
            // Allow retrying a VRF call if 1 hour has passed
            revert RandomRequestInFlight(randRequestId);
        }
        lastRandRequest = block.timestamp;

        merkleRoot = merkleRoot_;
        nParticipants = nParticipants_;
        emit MerkleRootReceived(merkleRoot_, nParticipants_, blockNumber);

        provenance = string(
            abi.encodePacked(
                srcChainId.toString(),
                ":",
                srcCollector.toHexString()
            )
        );

        // Next step: call VRF
        randRequestId = IRandomiser(randomiser).getRandomNumber(address(this));
    }

    /// @notice See {IRandomiserCallback}
    function receiveRandomWords(
        uint256 requestId,
        uint256[] calldata randomWords
    ) external {
        if (_msgSender() != randomiser) {
            revert UnknownRandomiser(_msgSender());
        }
        if (randRequestId != requestId) {
            revert InvalidRequestId(requestId);
        }
        if (merkleRoot == 0 || nParticipants == 0) {
            revert MerkleRootNotReady(requestId);
        }
        if (raffleId != 0) {
            revert AlreadyFinalised(raffleId);
        }
        if (randomWords.length == 0) {
            revert InvalidRandomWords(randomWords);
        }

        // Finalise raffle
        bytes32 merkleRoot_ = merkleRoot;
        uint256 nParticipants_ = nParticipants;
        uint256 randomness = randomWords[0];
        string memory provenance_ = provenance;
        uint256 raffleId_ = IRaffleChef(raffleChef).commit(
            merkleRoot_,
            nParticipants_,
            prizes.length,
            provenance_,
            randomness
        );
        raffleId = raffleId_;

        emit Finalised(
            raffleId_,
            merkleRoot_,
            nParticipants_,
            randomness,
            provenance_
        );
    }

    /// @notice Load a prize into this contract as the nth prize where
    ///     n == |prizes|
    function onERC721Received(
        address,
        address,
        uint256 tokenId,
        bytes calldata
    ) external returns (bytes4) {
        _addERC721Prize(_msgSender(), tokenId);
        return this.onERC721Received.selector;
    }

    /// @notice Add prize as nth prize if ERC721 token is already loaded into
    ///     this contract.
    /// @param nftContract NFT contract address
    /// @param tokenId Token ID of the NFT to accept
    function _addERC721Prize(address nftContract, uint256 tokenId) internal {
        // Ensure that this contract actually has custody of the ERC721
        if (IERC721(nftContract).ownerOf(tokenId) != address(this)) {
            revert ERC721NotReceived(nftContract, tokenId);
        }

        // Record prize
        bytes memory prize = abi.encode(
            uint8(PrizeType.ERC721),
            nftContract,
            tokenId
        );
        prizes.push(prize);
        emit ERC721Received(nftContract, tokenId);
    }

    /// @notice Load prize(s) into this contract. If amount > 1, then
    ///     prizes are inserted sequentially as individual prizes.
    function onERC1155Received(
        address,
        address,
        uint256 id,
        uint256 amount,
        bytes calldata options
    ) external returns (bytes4) {
        bool isSinglePrize;
        if (options.length > 0) {
            isSinglePrize = abi.decode(options, (bool));
        }

        if (isSinglePrize) {
            _addERC1155Prize(_msgSender(), id, amount);
        } else {
            for (uint256 i; i < amount; ++i) {
                _addERC1155Prize(_msgSender(), id, 1);
            }
        }
        return this.onERC1155Received.selector;
    }

    /// @notice Load prize(s) into this contract. If amount > 1, then
    ///     prizes are inserted sequentially as individual prizes.
    function onERC1155BatchReceived(
        address,
        address,
        uint256[] calldata ids,
        uint256[] calldata amounts,
        bytes calldata options
    ) external returns (bytes4) {
        require(ids.length == amounts.length);

        bool isSinglePrize;
        if (options.length > 0) {
            isSinglePrize = abi.decode(options, (bool));
        }

        for (uint256 i; i < ids.length; ++i) {
            if (isSinglePrize) {
                _addERC1155Prize(_msgSender(), ids[i], amounts[i]);
            } else {
                for (uint256 j; j < amounts[i]; ++j) {
                    _addERC1155Prize(_msgSender(), ids[i], 1);
                }
            }
        }
        return this.onERC1155BatchReceived.selector;
    }

    /// @notice Add prize as nth prize if ERC1155 token is already loaded into
    ///     this contract.
    /// @notice NB: The contract does not check that there is enough ERC1155
    ///     tokens to distribute as prizes.
    /// @param nftContract NFT contract address
    /// @param tokenId Token ID of the NFT to accept
    /// @param amount Amount of ERC1155 tokens
    function _addERC1155Prize(
        address nftContract,
        uint256 tokenId,
        uint256 amount
    ) internal {
        // Ensure that this contract actually has custody of the ERC721
        if (IERC1155(nftContract).balanceOf(nftContract, tokenId) >= amount) {
            revert ERC1155NotReceived(nftContract, tokenId, amount);
        }

        // Record prize
        bytes memory prize = abi.encode(
            uint8(PrizeType.ERC1155),
            nftContract,
            tokenId,
            amount
        );
        prizes.push(prize);
        emit ERC1155Received(nftContract, tokenId, amount);
    }

    /// @notice Add k ERC1155 tokens as the [n+0..n+k)th prizes
    /// @notice NB: The contract does not check that there is enough ERC1155
    ///     tokens to distribute as prizes.
    /// @param nftContract NFT contract address
    /// @param tokenId Token ID of the NFT to accept
    /// @param amount Amount of ERC1155 tokens
    function _addERC1155SequentialPrizes(
        address nftContract,
        uint256 tokenId,
        uint256 amount
    ) internal {
        // Ensure that this contract actually has custody of the ERC721
        if (IERC1155(nftContract).balanceOf(nftContract, tokenId) >= amount) {
            revert ERC1155NotReceived(nftContract, tokenId, amount);
        }

        // Record prizes
        for (uint256 i; i < amount; ++i) {
            bytes memory prize = abi.encode(
                uint8(PrizeType.ERC1155),
                nftContract,
                tokenId,
                1
            );
            prizes.push(prize);
        }
    }

    function _getPrizeType(
        bytes memory prize
    ) internal pure returns (PrizeType) {
        uint8 rawType;
        assembly {
            rawType := and(mload(add(prize, 0x20)), 0xff)
        }
        if (rawType > 1) {
            revert InvalidPrizeType(rawType);
        }
        return PrizeType(rawType);
    }

    function _getERC721Prize(
        bytes memory prize
    ) internal pure returns (address nftContract, uint256 tokenId) {
        (, nftContract, tokenId) = abi.decode(prize, (uint8, address, uint256));
    }

    function _getERC1155Prize(
        bytes memory prize
    )
        internal
        pure
        returns (address nftContract, uint256 tokenId, uint256 amount)
    {
        (, nftContract, tokenId, amount) = abi.decode(
            prize,
            (uint8, address, uint256, uint256)
        );
    }

    /// @notice Self-explanatory
    function getPrizeCount() public view returns (uint256) {
        return prizes.length;
    }

    /// @notice Get a slice of the prize list at the desired offset. The prize
    ///     list is represented in raw bytes, with the 0th byte signifying
    ///     whether it's an ERC-721 or ERC-1155 prize. See {_getPrizeType},
    ///     {_getERC721Prize}, and {_getERC1155Prize} functions for how to
    ///     decode each prize.
    /// @param offset Prize index to start slice at (0-based)
    /// @param limit How many prizes to fetch at maximum (may return fewer)
    function getPrizes(
        uint256 offset,
        uint256 limit
    ) public view returns (bytes[] memory prizes_) {
        uint256 len = prizes.length;
        if (len == 0 || offset >= prizes.length) {
            return new bytes[](0);
        }
        limit = offset + limit >= prizes.length
            ? prizes.length - offset
            : limit;
        prizes_ = new bytes[](limit);
        for (uint256 i; i < limit; ++i) {
            prizes_[i] = prizes[offset + i];
        }
    }

    /// @notice Withdraw ERC721 after deadline has passed
    function withdrawERC721(
        address nftContract,
        uint256 tokenId
    ) external onlyOwner onlyAfterExpiry {
        IERC721(nftContract).safeTransferFrom(
            address(this),
            _msgSender(),
            tokenId
        );
        emit ERC721Reclaimed(nftContract, tokenId);
    }

    /// @notice Withdraw ERC1155 after deadline has passed
    function withdrawERC1155(
        address nftContract,
        uint256 tokenId,
        uint256 amount
    ) external onlyOwner onlyAfterExpiry {
        IERC1155(nftContract).safeTransferFrom(
            address(this),
            _msgSender(),
            tokenId,
            amount,
            bytes("")
        );
        emit ERC1155Reclaimed(nftContract, tokenId, amount);
    }
}

// File: contracts/interfaces/IDistributooor.sol



// SPDX-License-Identifier: BUSL-1.1
pragma solidity 0.8.17;

interface IDistributooor {
    /// @notice Receive a merkle root from a trusted source.
    /// @param srcChainId Chain ID where the Merkle collector lives
    /// @param srcCollector Contract address of Merkle collector
    /// @param blockNumber Block number at which the Merkle root was calculated
    /// @param merkleRoot Merkle root of participants
    /// @param nParticipants Number of participants in the merkle tree
    function receiveParticipantsMerkleRoot(
        uint256 srcChainId,
        address srcCollector,
        uint256 blockNumber,
        bytes32 merkleRoot,
        uint256 nParticipants
    ) external;

    event MerkleRootReceived(
        bytes32 merkleRoot,
        uint256 nParticipants,
        uint256 blockNumber
    );

    event ERC721Received(address nftContract, uint256 tokenId);
    event ERC1155Received(address nftContract, uint256 tokenId, uint256 amount);
    event ERC721Reclaimed(address nftContract, uint256 tokenId);
    event ERC1155Reclaimed(
        address nftContract,
        uint256 tokenId,
        uint256 amount
    );
    event Finalised(
        uint256 raffleId,
        bytes32 merkleRoot,
        uint256 nParticipants,
        uint256 randomness,
        string provenance
    );

    error Unauthorised(address caller);
    error MerkleRootRejected(
        bytes32 merkleRoot,
        uint256 nParticipants,
        uint256 blockNumber
    );
    error InvalidSignature(
        bytes signature,
        address expectedSigner,
        address recoveredSigner
    );
    error InvalidRequestId(uint256 requestId);
    error MerkleRootNotReady(uint256 requestId);
    error AlreadyFinalised(uint256 raffleId);
}

// File: contracts/interfaces/IDistributooorFactory.sol



// SPDX-License-Identifier: BUSL-1.1
pragma solidity 0.8.17;

interface IDistributooorFactory {
    enum CrossChainAction {
        ReceiveMerkleRoot
    }

    struct ReceiveMerkleRootParams {
        /// @notice Original requester of merkle root
        address requester;
        /// @notice Merkle root collector
        address collectooor;
        uint256 blockNumber;
        bytes32 merkleRoot;
        uint256 nodeCount;
    }

    event DistributooorMasterCopyUpdated(
        address oldMasterCopy,
        address newMasterCopy
    );
    event DistributooorDeployed(address distributooor);
    event RaffleChefUpdated(address oldRaffleChef, address newRaffleChef);

    error UnknownConsumer(address consumer);

    /// @notice Request merkle root from an external collectooor
    function requestMerkleRoot(
        uint256 chainId,
        address collectooorFactory,
        address collectooor
    ) external;
}

// File: contracts/interfaces/IRaffleChef.sol



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

interface IRaffleChef {
    event RaffleCreated(uint256 indexed raffleId);
    event RaffleCommitted(uint256 indexed raffleId);

    error RaffleNotRolled(uint256 raffleId);
    error InvalidCommitment(
        uint256 raffleId,
        bytes32 merkleRoot,
        uint256 nParticipants,
        uint256 nWinners,
        uint256 randomness,
        string provenance
    );
    error Unauthorised(address unauthorisedUser);
    error StartingRaffleIdTooLow(uint256 raffleId);
    error InvalidProof(bytes32 leaf, bytes32[] proof);

    /// @dev Descriptive state of a raffle based on its variables that are set/unset
    enum RaffleState {
        /// @dev Default state
        Unknown,
        /// @dev Done
        Committed
    }

    /// @notice Structure of every raffle; presence of certain elements indicate the raffle state
    struct Raffle {
        bytes32 participantsMerkleRoot;
        uint256 nParticipants;
        uint256 nWinners;
        uint256 randomSeed;
        address owner;
        string provenance;
    }

    /// @notice Publish a commitment (the merkle root of the finalised participants list, and
    ///     the number of winners to draw, and the random seed). Only call this function once
    ///     the random seed and list of raffle participants has finished being collected.
    /// @param participantsMerkleRoot Merkle root constructed from finalised participants list
    /// @param nWinners Number of winners to draw
    /// @param provenance IPFS CID of this raffle's provenance including full participants list
    /// @param randomness Random seed for the raffle
    /// @return Raffle ID that can be used to lookup the raffle results, when
    ///     the raffle is finalised.
    function commit(
        bytes32 participantsMerkleRoot,
        uint256 nParticipants,
        uint256 nWinners,
        string calldata provenance,
        uint256 randomness
    ) external returns (uint256);

    /// @notice Verify that an account is in the winners list for a specific raffle
    ///     using a merkle proof and the raffle's previous public commitments. This is
    ///     a view-only function that does not record if a winner has already claimed
    ///     their win; that is left up to the caller to handle.
    /// @param raffleId ID of the raffle to check against
    /// @param leafHash Hash of the leaf value that represents the participant
    /// @param proof Merkle subproof (hashes)
    /// @param originalIndex Original leaf index in merkle tree, part of merkle proof
    /// @return isWinner true if claiming account is indeed a winner
    /// @return permutedIndex winning (shuffled) index
    function verifyRaffleWinner(
        uint256 raffleId,
        bytes32 leafHash,
        bytes32[] calldata proof,
        uint256 originalIndex
    ) external view returns (bool isWinner, uint256 permutedIndex);

    /// @notice Get an existing raffle
    /// @param raffleId ID of raffle to get
    /// @return raffle data, if it exists
    function getRaffle(uint256 raffleId) external view returns (Raffle memory);

    /// @notice Get the current state of raffle, given a `raffleId`
    /// @param raffleId ID of raffle to get
    /// @return See {RaffleState} enum
    function getRaffleState(
        uint256 raffleId
    ) external view returns (RaffleState);
}

// File: contracts/interfaces/IRandomiser.sol



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

interface IRandomiser {
    function getRandomNumber(
        address callbackContract
    ) external returns (uint256 requestId);
}

// File: contracts/interfaces/IRandomiserCallback.sol



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

interface IRandomiserCallback {
    function receiveRandomWords(
        uint256 requestId,
        uint256[] calldata randomWords
    ) external;
}

// File: contracts/interfaces/TypeAndVersion.sol



// SPDX-License-Identifier: MIT
/**
    The MIT License (MIT)

    Copyright (c) 2018 SmartContract ChainLink, Ltd.

    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
    THE SOFTWARE.
*/

pragma solidity ^0.8;

abstract contract TypeAndVersion {
    function typeAndVersion() external pure virtual returns (string memory);
}