Contract Source Code:

// SPDX-License-Identifier: MIT
pragma solidity 0.8.27;

import "../vendor/@openzeppelin/[email protected]/access/Ownable.sol";
import "./interfaces/IHashRegistry.sol";
import "../vendor/@openzeppelin/[email protected]/utils/cryptography/MessageHashUtils.sol";
import "../vendor/@openzeppelin/[email protected]/utils/cryptography/ECDSA.sol";

/// @title A contract where a value for each hash type can be registered using
/// the signatures of the respective signers that are set by the contract owner
/// @notice Hashes are identified by a unique "hash type", which is a `bytes32`
/// type that can be determined based on any arbitrary convention. The contract
/// owner can set a list of signers for each hash type. For a hash value to be
/// registered, its signers must be set by the contract owner, and valid
/// signatures by each signer must be provided. The hash values are bundled
/// with timestamps that act as nonces, meaning that each registration must
/// be with a larger timestamp than the previous. The contract owner can
/// override previously registered hashes.
/// A signer can sign a delegation message that allows the delegate to sign
/// hashes on their behalf across all instances of this contract until the
/// specified time. This delegation is irrevocable by design (as revoking
/// across all instances would be error-prone). To undo an unwanted delegation,
/// the signer must be swapped out by the contract owner until the delegation
/// runs out.
/// @dev This contract can be used in standalone form to be referred to through
/// external calls, or inherited by the contract that will access the
/// registered hashes internally.
/// HashRegistry is intended for use-cases where signatures and delegations
/// need to apply universally across domains, which is why it is blind to the
/// domain (unlike ERC-712). However, the inheriting contract can implement the
/// type hashes to be domain-specific.
contract HashRegistry is Ownable, IHashRegistry {
    struct Hash {
        bytes32 value;
        uint256 timestamp;
    }

    /// @notice Hash type to the last registered value and timestamp
    mapping(bytes32 => Hash) public override hashes;

    /// @notice Hash type to the hash of the array of signer addresses
    mapping(bytes32 => bytes32) public override hashTypeToSignersHash;

    uint256 private constant ECDSA_SIGNATURE_LENGTH = 65;

    // Length of abi.encode(uint256, bytes, bytes), where the bytes types are
    // ECDSA signatures padded to the next largest multiple of 32 bytes, which
    // is 96
    uint256 private constant DELEGATED_SIGNATURE_LENGTH =
        32 + 32 + 32 + (32 + 96) + (32 + 96);

    bytes32 private constant HASHREGISTRY_SIGNATURE_DELEGATION_HASH_TYPE =
        keccak256(abi.encodePacked("HashRegistry signature delegation"));

    /// @param initialOwner Initial owner address
    constructor(address initialOwner) Ownable(initialOwner) {}

    /// @notice Returns the owner address
    /// @return Owner address
    function owner()
        public
        view
        virtual
        override(Ownable, IOwnable)
        returns (address)
    {
        return super.owner();
    }

    /// @notice Called by the owner to renounce the ownership of the contract
    function renounceOwnership() public virtual override(Ownable, IOwnable) {
        return super.renounceOwnership();
    }

    /// @notice Called by the owner to transfer the ownership of the contract
    /// @param newOwner New owner address
    function transferOwnership(
        address newOwner
    ) public virtual override(Ownable, IOwnable) {
        return super.transferOwnership(newOwner);
    }

    /// @notice Called by the contract owner to set signers for a hash type.
    /// The signer addresses must be in ascending order.
    /// @param hashType Hash type
    /// @param signers Signer addresses
    function setSigners(
        bytes32 hashType,
        address[] calldata signers
    ) external override onlyOwner {
        require(hashType != bytes32(0), "Hash type zero");
        uint256 signersCount = signers.length;
        require(signersCount != 0, "Signers empty");
        require(signers[0] != address(0), "First signer address zero");
        for (uint256 ind = 1; ind < signersCount; ind++) {
            require(
                signers[ind] > signers[ind - 1],
                "Signers not in ascending order"
            );
        }
        hashTypeToSignersHash[hashType] = keccak256(abi.encodePacked(signers));
        emit SetSigners(hashType, signers);
    }

    /// @notice Called by the owner to set a hash. Overrides previous
    /// registrations and is allowed to set the value to `bytes32(0)`.
    /// @param hashType Hash type
    /// @param hashValue Hash value
    function setHash(
        bytes32 hashType,
        bytes32 hashValue
    ) external override onlyOwner {
        hashes[hashType] = Hash({value: hashValue, timestamp: block.timestamp});
        emit SetHash(hashType, hashValue, block.timestamp);
    }

    /// @notice Registers the hash value and timestamp for the respective type.
    /// The hash value cannot be zero.
    /// The timestamp must not exceed the block timestamp, yet be larger than
    /// the timestamp of the previous registration.
    /// The signers must have been set for the hash type, and the signatures
    /// must be sorted for the respective signer addresses to be in ascending
    /// order.
    /// Each signature can either be a standalone signature by the respective
    /// signer, or a signature by the signer's delegate, encoded along with
    /// the delegation end timestamp and delegation signature.
    /// @param hashType Hash type
    /// @param hashValue Hash value
    /// @param hashTimestamp Hash timestamp
    /// @param signatures Signatures
    function registerHash(
        bytes32 hashType,
        bytes32 hashValue,
        uint256 hashTimestamp,
        bytes[] calldata signatures
    ) external override {
        require(hashValue != bytes32(0), "Hash value zero");
        require(hashTimestamp <= block.timestamp, "Hash timestamp from future");
        require(
            hashTimestamp > hashes[hashType].timestamp,
            "Hash timestamp not more recent"
        );
        bytes32 signersHash = hashTypeToSignersHash[hashType];
        require(signersHash != bytes32(0), "Signers not set");
        uint256 signaturesCount = signatures.length;
        address[] memory signers = new address[](signaturesCount);
        bytes32 ethSignedMessageHash = MessageHashUtils.toEthSignedMessageHash(
            keccak256(abi.encodePacked(hashType, hashValue, hashTimestamp))
        );
        for (uint256 ind = 0; ind < signaturesCount; ind++) {
            uint256 signatureLength = signatures[ind].length;
            if (signatureLength == ECDSA_SIGNATURE_LENGTH) {
                signers[ind] = ECDSA.recover(
                    ethSignedMessageHash,
                    signatures[ind]
                );
            } else if (signatureLength == DELEGATED_SIGNATURE_LENGTH) {
                (
                    uint256 delegationEndTimestamp,
                    bytes memory delegationSignature,
                    bytes memory hashSignature
                ) = abi.decode(signatures[ind], (uint256, bytes, bytes));
                require(
                    block.timestamp < delegationEndTimestamp,
                    "Delegation ended"
                );
                signers[ind] = ECDSA.recover(
                    MessageHashUtils.toEthSignedMessageHash(
                        keccak256(
                            abi.encodePacked(
                                signatureDelegationHashType(),
                                ECDSA.recover(
                                    ethSignedMessageHash,
                                    hashSignature
                                ),
                                delegationEndTimestamp
                            )
                        )
                    ),
                    delegationSignature
                );
            } else {
                revert("Invalid signature length");
            }
        }
        require(
            signersHash == keccak256(abi.encodePacked(signers)),
            "Signature mismatch"
        );
        hashes[hashType] = Hash({value: hashValue, timestamp: hashTimestamp});
        emit RegisteredHash(hashType, hashValue, hashTimestamp);
    }

    /// @notice Returns the signature delegation hash type used in delegation
    /// signatures
    /// @dev Delegation signatures signed with a signature delegation hash type
    /// will apply universally across all HashRegistry instances that use that
    /// same signature delegation hash type. The inheriting contract can
    /// specify a special signature delegation hash type by overriding this
    /// function.
    /// @return Signature delegation hash type
    function signatureDelegationHashType()
        public
        view
        virtual
        override
        returns (bytes32)
    {
        return HASHREGISTRY_SIGNATURE_DELEGATION_HASH_TYPE;
    }

    /// @notice Returns get the hash value for the type
    /// @param hashType Hash type
    /// @return hashValue Hash value
    function getHashValue(
        bytes32 hashType
    ) external view override returns (bytes32 hashValue) {
        hashValue = hashes[hashType].value;
    }
}

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

import "../../utils/interfaces/ISelfMulticall.sol";

interface IAccessControlRegistryAdminned is ISelfMulticall {
    function accessControlRegistry() external view returns (address);

    function adminRoleDescription() external view returns (string memory);
}

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

import "./IAccessControlRegistryAdminned.sol";

interface IAccessControlRegistryAdminnedWithManager is
    IAccessControlRegistryAdminned
{
    function manager() external view returns (address);

    function adminRole() external view returns (bytes32);
}

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

import "./IOwnable.sol";

interface IHashRegistry is IOwnable {
    event SetSigners(bytes32 indexed hashType, address[] signers);

    event SetHash(
        bytes32 indexed hashType,
        bytes32 hashValue,
        uint256 hashTimestamp
    );

    event RegisteredHash(
        bytes32 indexed hashType,
        bytes32 hashValue,
        uint256 hashTimestamp
    );

    function setSigners(bytes32 hashType, address[] calldata signers) external;

    function setHash(bytes32 hashType, bytes32 hashValue) external;

    function registerHash(
        bytes32 hashType,
        bytes32 hashValue,
        uint256 hashTimestamp,
        bytes[] calldata signatures
    ) external;

    function signatureDelegationHashType() external view returns (bytes32);

    function getHashValue(
        bytes32 hashType
    ) external view returns (bytes32 hashValue);

    function hashes(
        bytes32 hashType
    ) external view returns (bytes32 hashValue, uint256 hashTimestamp);

    function hashTypeToSignersHash(
        bytes32 hashType
    ) external view returns (bytes32 signersHash);
}

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

interface IOwnable {
    function owner() external view returns (address);

    function renounceOwnership() external;

    function transferOwnership(address newOwner) external;
}

// SPDX-License-Identifier: MIT
pragma solidity 0.8.27;

import "../access/HashRegistry.sol";
import "../utils/ExtendedSelfMulticall.sol";
import "./interfaces/IApi3MarketV2.sol";
import "../vendor/@openzeppelin/[email protected]/utils/math/SafeCast.sol";
import "../vendor/@openzeppelin/[email protected]/utils/cryptography/MerkleProof.sol";
import "./interfaces/IApi3ServerV1.sol";
import "./interfaces/IApi3ServerV1OevExtension.sol";
import "./proxies/interfaces/IApi3ReaderProxyV1Factory.sol";
import "./interfaces/IAirseekerRegistry.sol";

/// @title The contract that API3 users interact with using the API3 Market
/// frontend to purchase data feed subscriptions
/// @notice API3 streamlines and protocolizes its integration processes through
/// the API3 Market (https://market.api3.org), which is a data feed
/// subscription marketplace. The Api3MarketV2 contract is the on-chain portion
/// of this system.
/// Api3MarketV2 enables API3 to predetermine the decisions related to its data
/// feed services (such as the curation of data feed sources or subscription
/// prices) and publish them on-chain. This streamlines the intergation flow,
/// as it allows the users to initiate subscriptions immediately, without
/// requiring any two-way communication with API3. Furthermore, this removes
/// the need for API3 to have agents operating in the meatspace gathering order
/// details, quoting prices and reviewing payments, and allows all such
/// operations to be cryptographically secured with a multi-party scheme in an
/// end-to-end manner.
/// @dev The user is strongly recommended to use the API3 Market frontend while
/// interacting with this contract, mostly because doing so successfully
/// requires some amount of knowledge of other API3 contracts. Specifically,
/// Api3MarketV2 requires the data feed for which the subscription is being
/// purchased to be "readied", the correct Merkle proofs to be provided, and
/// enough payment to be made. The API3 Market frontend will fetch the
/// appropriate Merkle proofs, create a multicall transaction that will ready
/// the data feed before making the call to buy the subscription, and compute
/// the amount to be sent that will barely allow the subscription to be
/// purchased. For most users, building such a transaction themselves would be
/// impractical.
contract Api3MarketV2 is HashRegistry, ExtendedSelfMulticall, IApi3MarketV2 {
    enum UpdateParametersComparisonResult {
        EqualToQueued,
        BetterThanQueued,
        WorseThanQueued
    }

    // The update parameters for each subscription is kept in a hash map rather
    // than in full form as an optimization. Refer to AirseekerRegistry for a
    // similar scheme.
    // The subscription queues are kept as linked lists, for which each
    // subscription has a next subscription ID field.
    struct Subscription {
        bytes32 updateParametersHash;
        uint32 endTimestamp;
        uint224 dailyPrice;
        bytes32 nextSubscriptionId;
    }

    /// @notice dAPI management Merkle root hash type
    /// @dev "Hash type" is what HashRegistry uses to address hashes used for
    /// different purposes
    bytes32 public constant override DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE =
        keccak256(abi.encodePacked("dAPI management Merkle root"));

    /// @notice dAPI pricing Merkle root hash type
    bytes32 public constant override DAPI_PRICING_MERKLE_ROOT_HASH_TYPE =
        keccak256(abi.encodePacked("dAPI pricing Merkle root"));

    /// @notice Signed API URL Merkle root hash type
    bytes32 public constant override SIGNED_API_URL_MERKLE_ROOT_HASH_TYPE =
        keccak256(abi.encodePacked("Signed API URL Merkle root"));

    /// @notice Maximum dAPI update age. This contract cannot be used to set a
    /// dAPI name to a data feed that has not been updated in the last
    /// `MAXIMUM_DAPI_UPDATE_AGE`.
    uint256 public constant override MAXIMUM_DAPI_UPDATE_AGE = 1 days;

    /// @notice Api3ServerV1 contract address
    address public immutable override api3ServerV1;

    /// @notice Api3ReaderProxyV1Factory contract address
    address public immutable override api3ReaderProxyV1Factory;

    /// @notice AirseekerRegistry contract address
    address public override airseekerRegistry;

    /// @notice Maximum subscription queue length for a dAPI
    /// @dev Some functionality in this contract requires to iterate through
    /// the entire subscription queue for a dAPI, and the queue length is
    /// limited to prevent this process from being bloated. Considering that
    /// each item in the subscription queue has unique update parameters, the
    /// length of the subscription queue is also limited by the number of
    /// unique update parameters offered in the dAPI pricing Merkle tree. For
    /// reference, at the time this contract is implemented, the API3 Market
    /// offers 4 update parameter options.
    uint256 public immutable override maximumSubscriptionQueueLength;

    /// @notice Subscriptions indexed by their IDs
    mapping(bytes32 => Subscription) public override subscriptions;

    /// @notice dAPI name to current subscription ID, which denotes the start
    /// of the subscription queue for the dAPI
    mapping(bytes32 => bytes32) public override dapiNameToCurrentSubscriptionId;

    // Update parameters hash map
    mapping(bytes32 => bytes) private updateParametersHashToValue;

    // Length of abi.encode(address, bytes32)
    uint256 private constant DATA_FEED_DETAILS_LENGTH_FOR_SINGLE_BEACON =
        32 + 32;

    // Length of abi.encode(uint256, int224, uint256)
    uint256 private constant UPDATE_PARAMETERS_LENGTH = 32 + 32 + 32;

    bytes32 private constant API3MARKETV2_SIGNATURE_DELEGATION_HASH_TYPE =
        keccak256(abi.encodePacked("Api3MarketV2 signature delegation"));

    /// @dev The maximum subscription queue length should be large enough to
    /// not obstruct subscription purchases under usual conditions, and small
    /// enough to keep the queue at an iterable size. For example, if the
    /// number of unique update parameters in the dAPI pricing Merkle trees
    /// that are being used is around 5, a maximum subscription queue length of
    /// 10 would be acceptable for a chain with typical gas costs.
    /// @param owner_ Owner address
    /// @param api3ReaderProxyV1Factory_ Api3ReaderProxyV1Factory contract
    /// address
    /// @param maximumSubscriptionQueueLength_ Maximum subscription queue
    /// length
    constructor(
        address owner_,
        address api3ReaderProxyV1Factory_,
        uint256 maximumSubscriptionQueueLength_
    ) HashRegistry(owner_) {
        require(
            maximumSubscriptionQueueLength_ != 0,
            "Maximum queue length zero"
        );
        api3ReaderProxyV1Factory = api3ReaderProxyV1Factory_;
        api3ServerV1 = IApi3ServerV1OevExtension(
            IApi3ReaderProxyV1Factory(api3ReaderProxyV1Factory_)
                .api3ServerV1OevExtension()
        ).api3ServerV1();
        maximumSubscriptionQueueLength = maximumSubscriptionQueueLength_;
    }

    /// @notice Returns the owner address
    /// @return Owner address
    function owner()
        public
        view
        override(HashRegistry, IOwnable)
        returns (address)
    {
        return super.owner();
    }

    /// @notice Overriden to be disabled
    function renounceOwnership() public pure override(HashRegistry, IOwnable) {
        revert("Ownership cannot be renounced");
    }

    /// @notice Overriden to be disabled
    function transferOwnership(
        address
    ) public pure override(HashRegistry, IOwnable) {
        revert("Ownership cannot be transferred");
    }

    /// @notice Called once by the owner to set the AirseekerRegistry address
    /// @dev There is a circular dependency between an Api3MarketV2 and its
    /// respective AirseekerRegistry. In a previous implementation,
    /// Api3Market deployed its AirseekerRegistry in its constructor, yet the
    /// resulting deployment transaction required too much gas, which ended up
    /// being an issue on some chains. Instead, the current deployment flow is
    /// for Api3MarketV2 to be deployed with a transaction, AirseekerRegistry
    /// to be deployed with another transaction with the Api3MarketV2 address
    /// as an argument, and finally, for the Api3MarketV2 owner to set the
    /// AirseekerRegister address with a third transaction.
    /// Once the AirseekerRegister address is set, it cannot be updated.
    /// @param airseekerRegistry_ AirseekerRegistry address
    function setAirseekerRegistry(
        address airseekerRegistry_
    ) external override onlyOwner {
        require(
            airseekerRegistry_ != address(0),
            "AirseekerRegistry address zero"
        );
        require(
            airseekerRegistry == address(0),
            "AirseekerRegistry already set"
        );
        // The following check does not guarantee that `airseekerRegistry_`
        // belongs to a valid AirseekerRegistry instance. The Api3MarketV2
        // owner is responsible with verifying that it is before calling this
        // function.
        require(
            IAirseekerRegistry(airseekerRegistry_).owner() == address(this),
            "Not AirseekerRegistry owner"
        );
        airseekerRegistry = airseekerRegistry_;
        emit SetAirseekerRegistry(airseekerRegistry_);
    }

    /// @notice Buys subscription and updates the current subscription ID if
    /// necessary. The user is recommended to interact with this contract over
    /// the API3 Market frontend due to its complexity.
    /// @dev The data feed that the dAPI name will be set to after this
    /// function is called must be readied (see `validateDataFeedReadiness()`)
    /// before calling this function.
    /// Enough funds must be sent to put the sponsor wallet balance over its
    /// expected amount after the subscription is bought. Since sponsor wallets
    /// send data feed update transactions, it is not possible to determine
    /// what their balance will be at the time sent transactions are confirmed.
    /// To avoid transactions being reverted as a result of this, consider
    /// sending some extra.
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @param dapiManagementAndDapiPricingMerkleData ABI-encoded dAPI
    /// management and dAPI pricing Merkle roots and proofs
    /// @return subscriptionId Subscription ID
    function buySubscription(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    ) public payable override returns (bytes32 subscriptionId) {
        require(dataFeedId != bytes32(0), "Data feed ID zero");
        require(sponsorWallet != address(0), "Sponsor wallet address zero");
        verifyDapiManagementAndDapiPricingMerkleProofs(
            dapiName,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            dapiManagementAndDapiPricingMerkleData
        );
        subscriptionId = addSubscriptionToQueue(
            dapiName,
            dataFeedId,
            updateParameters,
            duration,
            price
        );
        require(
            sponsorWallet.balance + msg.value >=
                computeExpectedSponsorWalletBalance(dapiName),
            "Insufficient payment"
        );
        emit BoughtSubscription(
            dapiName,
            subscriptionId,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            msg.value
        );
        if (msg.value > 0) {
            (bool success, ) = sponsorWallet.call{value: msg.value}("");
            require(success, "Transfer unsuccessful");
        }
    }

    /// @notice Called by the owner to cancel all subscriptions for a dAPI
    /// that needs to be decommissioned urgently
    /// @dev The root of a new dAPI pricing Merkle tree that excludes the dAPI
    /// should be registered before canceling the subscriptions. Otherwise,
    /// anyone can immediately buy the subscriptions again.
    /// @param dapiName dAPI name
    function cancelSubscriptions(bytes32 dapiName) external override onlyOwner {
        require(
            dapiNameToCurrentSubscriptionId[dapiName] != bytes32(0),
            "Subscription queue empty"
        );
        dapiNameToCurrentSubscriptionId[dapiName] = bytes32(0);
        IAirseekerRegistry(airseekerRegistry).setDapiNameToBeDeactivated(
            dapiName
        );
        emit CanceledSubscriptions(dapiName);
    }

    /// @notice If the current subscription has ended, updates it with the one
    /// that will end next
    /// @dev The fact that there is a current subscription that has ended would
    /// mean that API3 is providing a service that was not paid for. Therefore,
    /// API3 should poll this function for all active dAPI names and call it
    /// whenever it is not going to revert to downgrade the specs.
    /// @param dapiName dAPI name
    function updateCurrentSubscriptionId(bytes32 dapiName) public override {
        bytes32 currentSubscriptionId = dapiNameToCurrentSubscriptionId[
            dapiName
        ];
        require(
            currentSubscriptionId != bytes32(0),
            "Subscription queue empty"
        );
        require(
            subscriptions[currentSubscriptionId].endTimestamp <=
                block.timestamp,
            "Current subscription not ended"
        );
        updateEndedCurrentSubscriptionId(dapiName, currentSubscriptionId);
    }

    /// @notice Updates the dAPI name to match the respective Merkle leaf
    /// @dev Buying a dAPI subscription always updates the dAPI name if
    /// necessary. However, API3 may also publish new Merkle roots between
    /// subscription purchases, in which case API3 should call this function to
    /// bring the chain state up to date. Therefore, API3 should poll this
    /// function for all active dAPI names and call it whenever it will not
    /// revert.
    /// Similar to `buySubscription()`, this function requires the data feed
    /// that the dAPI will be pointed to to be readied.
    /// This function is allowed to be called even when the respective dAPI is
    /// not active, which means that a dAPI name being set does not imply that
    /// the respective data feed is in service. Users should only use dAPIs for
    /// which there is an active subscription with update parameters that
    /// satisfy their needs.
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param dapiManagementMerkleData ABI-encoded dAPI management Merkle root
    /// and proof
    function updateDapiName(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata dapiManagementMerkleData
    ) external override {
        if (dataFeedId != bytes32(0)) {
            require(sponsorWallet != address(0), "Sponsor wallet address zero");
        } else {
            require(
                sponsorWallet == address(0),
                "Sponsor wallet address not zero"
            );
        }
        verifyDapiManagementMerkleProof(
            dapiName,
            dataFeedId,
            sponsorWallet,
            dapiManagementMerkleData
        );
        bytes32 currentDataFeedId = IApi3ServerV1(api3ServerV1)
            .dapiNameHashToDataFeedId(keccak256(abi.encodePacked(dapiName)));
        require(currentDataFeedId != dataFeedId, "Does not update dAPI name");
        if (dataFeedId != bytes32(0)) {
            validateDataFeedReadiness(dataFeedId);
        }
        IApi3ServerV1(api3ServerV1).setDapiName(dapiName, dataFeedId);
    }

    /// @notice Updates the signed API URL of the Airnode to match the
    /// respective Merkle leaf
    /// @dev Unlike the dAPI management and pricing Merkle leaves, the signed
    /// API URL Merkle leaves are not registered by the users as a part of
    /// subscription purchase transactions. API3 should poll this function for
    /// all Airnodes that are used in active dAPIs and call it whenever it will
    /// not revert.
    /// @param airnode Airnode address
    /// @param signedApiUrl Signed API URL
    /// @param signedApiUrlMerkleData ABI-encoded signed API URL Merkle root
    /// and proof
    function updateSignedApiUrl(
        address airnode,
        string calldata signedApiUrl,
        bytes calldata signedApiUrlMerkleData
    ) external override {
        verifySignedApiUrlMerkleProof(
            airnode,
            signedApiUrl,
            signedApiUrlMerkleData
        );
        require(
            keccak256(abi.encodePacked(signedApiUrl)) !=
                keccak256(
                    abi.encodePacked(
                        IAirseekerRegistry(airseekerRegistry)
                            .airnodeToSignedApiUrl(airnode)
                    )
                ),
            "Does not update signed API URL"
        );
        IAirseekerRegistry(airseekerRegistry).setSignedApiUrl(
            airnode,
            signedApiUrl
        );
    }

    /// @notice Multi-calls this contract, followed by a call with value to buy
    /// the subscription
    /// @dev This function is for the API3 Market frontend to call
    /// `eth_estimateGas` on a single transaction that readies a data feed and
    /// buys the respective subscription
    /// @param multicallData Array of calldata of batched calls
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @param dapiManagementAndDapiPricingMerkleData ABI-encoded dAPI
    /// management and dAPI pricing Merkle roots and proofs
    /// @return returndata Array of returndata of batched calls
    /// @return subscriptionId Subscription ID
    function multicallAndBuySubscription(
        bytes[] calldata multicallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        override
        returns (bytes[] memory returndata, bytes32 subscriptionId)
    {
        returndata = this.multicall(multicallData);
        subscriptionId = buySubscription(
            dapiName,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            dapiManagementAndDapiPricingMerkleData
        );
    }

    /// @notice Multi-calls this contract in a way that the transaction does
    /// not revert if any of the batched calls reverts, followed by a call with
    /// value to buy the subscription
    /// @dev This function is for the API3 Market frontend to send a single
    /// transaction that readies a data feed and buys the respective
    /// subscription. `tryMulticall()` is preferred in the purchase transaction
    /// because the readying calls may revert due to race conditions.
    /// @param tryMulticallData Array of calldata of batched calls
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @param dapiManagementAndDapiPricingMerkleData ABI-encoded dAPI
    /// management and dAPI pricing Merkle roots and proofs
    /// @return successes Array of success conditions of batched calls
    /// @return returndata Array of returndata of batched calls
    /// @return subscriptionId Subscription ID
    function tryMulticallAndBuySubscription(
        bytes[] calldata tryMulticallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        override
        returns (
            bool[] memory successes,
            bytes[] memory returndata,
            bytes32 subscriptionId
        )
    {
        (successes, returndata) = this.tryMulticall(tryMulticallData);
        subscriptionId = buySubscription(
            dapiName,
            dataFeedId,
            sponsorWallet,
            updateParameters,
            duration,
            price,
            dapiManagementAndDapiPricingMerkleData
        );
    }

    /// @notice Calls Api3ServerV1 to update the Beacon using data signed by
    /// the Airnode
    /// @dev The user is intended to make a multicall transaction through the
    /// API3 Market frontend to satisfy the required conditions to be able to
    /// buy a subscription and buy the subscription in a single transaction.
    /// The functions to which external calls must be made to to satisfy said
    /// conditions (such as this one) are added to this contract so that they
    /// can be multi-called by the user.
    /// @param airnode Airnode address
    /// @param templateId Template ID
    /// @param timestamp Signature timestamp
    /// @param data Update data (an `int256` encoded in contract ABI)
    /// @param signature Template ID, timestamp and the update data signed by
    /// the Airnode
    /// @return beaconId Updated Beacon ID
    function updateBeaconWithSignedData(
        address airnode,
        bytes32 templateId,
        uint256 timestamp,
        bytes calldata data,
        bytes calldata signature
    ) external override returns (bytes32 beaconId) {
        return
            IApi3ServerV1(api3ServerV1).updateBeaconWithSignedData(
                airnode,
                templateId,
                timestamp,
                data,
                signature
            );
    }

    /// @notice Calls Api3ServerV1 to update the Beacon set using the current
    /// values of its Beacons
    /// @param beaconIds Beacon IDs
    /// @return beaconSetId Updated Beacon set ID
    function updateBeaconSetWithBeacons(
        bytes32[] calldata beaconIds
    ) external override returns (bytes32 beaconSetId) {
        return
            IApi3ServerV1(api3ServerV1).updateBeaconSetWithBeacons(beaconIds);
    }

    /// @notice Calls Api3ReaderProxyV1Factory to deterministically deploy an
    /// Api3ReaderProxyV1
    /// @dev It is recommended for the users to read data feeds through proxies
    /// deployed by Api3ReaderProxyV1Factory, rather than calling the
    /// underlying contracts directly.
    /// Even though proxy deployment is not a condition for purchasing
    /// subscriptions, the interface is implemented here to allow the user to
    /// purchase a dAPI subscription and deploy the respective proxy in the
    /// same transaction with a multicall.
    /// @param dapiName dAPI name
    /// @param dappId dApp ID
    /// @param metadata Metadata associated with the proxy
    /// @return api3ReaderProxyV1 Api3ReaderProxyV1 address
    function deployApi3ReaderProxyV1(
        bytes32 dapiName,
        uint256 dappId,
        bytes calldata metadata
    ) external override returns (address api3ReaderProxyV1) {
        api3ReaderProxyV1 = IApi3ReaderProxyV1Factory(api3ReaderProxyV1Factory)
            .deployApi3ReaderProxyV1(dapiName, dappId, metadata);
    }

    /// @notice Calls AirseekerRegistry to register the data feed
    /// @param dataFeedDetails Data feed details
    /// @return dataFeedId Data feed ID
    function registerDataFeed(
        bytes calldata dataFeedDetails
    ) external override returns (bytes32 dataFeedId) {
        dataFeedId = IAirseekerRegistry(airseekerRegistry).registerDataFeed(
            dataFeedDetails
        );
    }

    /// @notice Computes the expected sponsor wallet balance based on the
    /// current subscription queue
    /// @dev API3 estimates the transaction fee cost of subscriptions, and
    /// prices them accordingly. The subscription fees paid for a dAPI are sent
    /// to the respective sponsor wallet, which will send the update
    /// transactions. In the case that a subscription is overpriced, the extra
    /// funds are automatically rolled over as a discount to the next
    /// subscription bought for the same dAPI. In the case that a subscription
    /// is underpriced, there is a risk of the sponsor wallet running out of
    /// funds, resulting in the subscription specs to not be met. To avoid
    /// this, API3 should poll this function for all active dAPI names, check
    /// the respective sponsor wallet balances, and top up the sponsor wallets
    /// as necessary. The conditions that result in the underpricing will most
    /// likely require an updated dAPI pricing Merkle root to be published.
    /// @param dapiName dAPI name
    /// @return expectedSponsorWalletBalance Expected sponsor wallet balance
    function computeExpectedSponsorWalletBalance(
        bytes32 dapiName
    ) public view override returns (uint256 expectedSponsorWalletBalance) {
        uint32 startTimestamp = SafeCast.toUint32(block.timestamp);
        Subscription storage queuedSubscription;
        for (
            bytes32 queuedSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            queuedSubscriptionId != bytes32(0);
            queuedSubscriptionId = queuedSubscription.nextSubscriptionId
        ) {
            queuedSubscription = subscriptions[queuedSubscriptionId];
            uint32 endTimestamp = queuedSubscription.endTimestamp;
            if (endTimestamp > block.timestamp) {
                expectedSponsorWalletBalance +=
                    ((endTimestamp - startTimestamp) *
                        queuedSubscription.dailyPrice) /
                    1 days;
                startTimestamp = endTimestamp;
            }
        }
    }

    /// @notice Computes the expected sponsor wallet balance after the
    /// respective subscription is added to the queue
    /// @dev This function is intended to be used by the API3 Market frontend
    /// to calculate how much the user should pay to purchase a specific
    /// subscription. As mentioned in the `buySubscription()` docstring, the
    /// user should aim for the sponsor wallet balance to be slightly more than
    /// the required amount in case it sends a transaction in the meantime,
    /// whose gas cost may decrease the sponsor wallet balance unexpectedly.
    /// Unit prices of the queued subscriptions are recorded on a daily basis
    /// and the expected balance is computed from these, which introduces a
    /// rounding error in the order of Weis. This also applies in practice (in
    /// that one can buy a subscription whose price is 1 ETH at 0.999... ETH).
    /// This behavior is accepted due to its effect being negligible.
    /// @param dapiName dAPI name
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    /// @return expectedSponsorWalletBalance Expected sponsor wallet balance
    function computeExpectedSponsorWalletBalanceAfterSubscriptionIsAdded(
        bytes32 dapiName,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price
    ) external view override returns (uint256 expectedSponsorWalletBalance) {
        require(
            updateParameters.length == UPDATE_PARAMETERS_LENGTH,
            "Update parameters length invalid"
        );
        (
            bytes32 subscriptionId,
            uint32 endTimestamp,
            bytes32 previousSubscriptionId,
            bytes32 nextSubscriptionId
        ) = prospectSubscriptionPositionInQueue(
                dapiName,
                updateParameters,
                duration
            );
        uint256 dailyPrice = (price * 1 days) / duration;
        uint32 startTimestamp = SafeCast.toUint32(block.timestamp);
        bytes32 queuedSubscriptionId = previousSubscriptionId == bytes32(0)
            ? subscriptionId
            : dapiNameToCurrentSubscriptionId[dapiName];
        for (; queuedSubscriptionId != bytes32(0); ) {
            if (queuedSubscriptionId == subscriptionId) {
                expectedSponsorWalletBalance +=
                    ((endTimestamp - startTimestamp) * dailyPrice) /
                    1 days;
                startTimestamp = endTimestamp;
                queuedSubscriptionId = nextSubscriptionId;
            } else {
                Subscription storage queuedSubscription = subscriptions[
                    queuedSubscriptionId
                ];
                uint32 queuedSubscriptionEndTimestamp = queuedSubscription
                    .endTimestamp;
                if (queuedSubscriptionEndTimestamp > block.timestamp) {
                    expectedSponsorWalletBalance +=
                        ((queuedSubscriptionEndTimestamp - startTimestamp) *
                            queuedSubscription.dailyPrice) /
                        1 days;
                    startTimestamp = queuedSubscriptionEndTimestamp;
                }
                if (previousSubscriptionId == queuedSubscriptionId) {
                    queuedSubscriptionId = subscriptionId;
                } else {
                    queuedSubscriptionId = queuedSubscription
                        .nextSubscriptionId;
                }
            }
        }
    }

    /// @notice Gets all data about the dAPI that is available
    /// @dev This function is intended to be used by the API3 Market frontend
    /// to get all data related to a specific dAPI. It returns the entire
    /// subscription queue, including the items whose end timestamps are in the
    /// past.
    /// @param dapiName dAPI name
    /// @return dataFeedDetails Data feed details
    /// @return dapiValue dAPI value read from Api3ServerV1
    /// @return dapiTimestamp dAPI timestamp read from Api3ServerV1
    /// @return beaconValues Beacon values read from Api3ServerV1
    /// @return beaconTimestamps Beacon timestamps read from Api3ServerV1
    /// @return updateParameters Update parameters of the subscriptions in the
    /// queue
    /// @return endTimestamps End timestamps of the subscriptions in the queue
    /// @return dailyPrices Daily prices of the subscriptions in the queue
    function getDapiData(
        bytes32 dapiName
    )
        external
        view
        override
        returns (
            bytes memory dataFeedDetails,
            int224 dapiValue,
            uint32 dapiTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps,
            bytes[] memory updateParameters,
            uint32[] memory endTimestamps,
            uint224[] memory dailyPrices
        )
    {
        bytes32 currentDataFeedId = IApi3ServerV1(api3ServerV1)
            .dapiNameHashToDataFeedId(keccak256(abi.encodePacked(dapiName)));
        (
            dataFeedDetails,
            dapiValue,
            dapiTimestamp,
            beaconValues,
            beaconTimestamps
        ) = getDataFeedData(currentDataFeedId);
        uint256 queueLength = 0;
        for (
            bytes32 queuedSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            queuedSubscriptionId != bytes32(0);
            queuedSubscriptionId = subscriptions[queuedSubscriptionId]
                .nextSubscriptionId
        ) {
            queueLength++;
        }
        updateParameters = new bytes[](queueLength);
        endTimestamps = new uint32[](queueLength);
        dailyPrices = new uint224[](queueLength);
        Subscription storage queuedSubscription = subscriptions[
            dapiNameToCurrentSubscriptionId[dapiName]
        ];
        for (uint256 ind = 0; ind < queueLength; ind++) {
            updateParameters[ind] = updateParametersHashToValue[
                queuedSubscription.updateParametersHash
            ];
            endTimestamps[ind] = queuedSubscription.endTimestamp;
            dailyPrices[ind] = queuedSubscription.dailyPrice;
            queuedSubscription = subscriptions[
                queuedSubscription.nextSubscriptionId
            ];
        }
    }

    /// @notice Gets all data about the data feed that is available
    /// @dev This function is intended to be used by the API3 Market frontend
    /// to determine what needs to be done to ready the data feed to purchase
    /// the respective subscription.
    /// In the case that the client wants to use this to fetch the respective
    /// Beacon readings for an unregistered data feed, they can do a static
    /// multicall where the `getDataFeedData()` call is preceded by a
    /// `registerDataFeed()` call.
    /// @param dataFeedId Data feed ID
    /// @return dataFeedDetails Data feed details
    /// @return dataFeedValue Data feed value read from Api3ServerV1
    /// @return dataFeedTimestamp Data feed timestamp read from Api3ServerV1
    /// @return beaconValues Beacon values read from Api3ServerV1
    /// @return beaconTimestamps Beacon timestamps read from Api3ServerV1
    function getDataFeedData(
        bytes32 dataFeedId
    )
        public
        view
        returns (
            bytes memory dataFeedDetails,
            int224 dataFeedValue,
            uint32 dataFeedTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps
        )
    {
        dataFeedDetails = IAirseekerRegistry(airseekerRegistry)
            .dataFeedIdToDetails(dataFeedId);
        (dataFeedValue, dataFeedTimestamp) = IApi3ServerV1(api3ServerV1)
            .dataFeeds(dataFeedId);
        if (
            dataFeedDetails.length == DATA_FEED_DETAILS_LENGTH_FOR_SINGLE_BEACON
        ) {
            beaconValues = new int224[](1);
            beaconTimestamps = new uint32[](1);
            (address airnode, bytes32 templateId) = abi.decode(
                dataFeedDetails,
                (address, bytes32)
            );
            (beaconValues[0], beaconTimestamps[0]) = IApi3ServerV1(api3ServerV1)
                .dataFeeds(deriveBeaconId(airnode, templateId));
        } else if (dataFeedDetails.length != 0) {
            (address[] memory airnodes, bytes32[] memory templateIds) = abi
                .decode(dataFeedDetails, (address[], bytes32[]));
            uint256 beaconCount = airnodes.length;
            beaconValues = new int224[](beaconCount);
            beaconTimestamps = new uint32[](beaconCount);
            for (uint256 ind = 0; ind < beaconCount; ind++) {
                (beaconValues[ind], beaconTimestamps[ind]) = IApi3ServerV1(
                    api3ServerV1
                ).dataFeeds(deriveBeaconId(airnodes[ind], templateIds[ind]));
            }
        }
    }

    /// @notice Subscription ID to update parameters
    /// @param subscriptionId Subscription ID
    /// @return updateParameters Update parameters
    function subscriptionIdToUpdateParameters(
        bytes32 subscriptionId
    ) public view override returns (bytes memory updateParameters) {
        updateParameters = updateParametersHashToValue[
            subscriptions[subscriptionId].updateParametersHash
        ];
    }

    /// @notice Returns the signature delegation hash type used in delegation
    /// signatures
    /// @return Signature delegation hash type
    function signatureDelegationHashType()
        public
        view
        virtual
        override(HashRegistry, IHashRegistry)
        returns (bytes32)
    {
        return API3MARKETV2_SIGNATURE_DELEGATION_HASH_TYPE;
    }

    /// @notice Adds the subscription to the queue if applicable
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @param price Subscription price
    function addSubscriptionToQueue(
        bytes32 dapiName,
        bytes32 dataFeedId,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price
    ) internal returns (bytes32 subscriptionId) {
        uint32 endTimestamp;
        bytes32 previousSubscriptionId;
        bytes32 nextSubscriptionId;
        (
            subscriptionId,
            endTimestamp,
            previousSubscriptionId,
            nextSubscriptionId
        ) = prospectSubscriptionPositionInQueue(
            dapiName,
            updateParameters,
            duration
        );
        bytes32 updateParametersHash = keccak256(updateParameters);
        if (updateParametersHashToValue[updateParametersHash].length == 0) {
            updateParametersHashToValue[
                updateParametersHash
            ] = updateParameters;
        }
        subscriptions[subscriptionId] = Subscription({
            updateParametersHash: updateParametersHash,
            endTimestamp: endTimestamp,
            dailyPrice: SafeCast.toUint224((price * 1 days) / duration),
            nextSubscriptionId: nextSubscriptionId
        });
        if (previousSubscriptionId == bytes32(0)) {
            if (subscriptionId != dapiNameToCurrentSubscriptionId[dapiName]) {
                emit UpdatedCurrentSubscriptionId(dapiName, subscriptionId);
                dapiNameToCurrentSubscriptionId[dapiName] = subscriptionId;
            }
            IAirseekerRegistry(airseekerRegistry).setDapiNameUpdateParameters(
                dapiName,
                updateParameters
            );
            IAirseekerRegistry(airseekerRegistry).setDapiNameToBeActivated(
                dapiName
            );
        } else {
            subscriptions[previousSubscriptionId]
                .nextSubscriptionId = subscriptionId;
            bytes32 currentSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            if (
                subscriptions[currentSubscriptionId].endTimestamp <=
                block.timestamp
            ) {
                updateEndedCurrentSubscriptionId(
                    dapiName,
                    currentSubscriptionId
                );
            }
        }
        validateDataFeedReadiness(dataFeedId);
        if (
            IApi3ServerV1(api3ServerV1).dapiNameHashToDataFeedId(
                keccak256(abi.encodePacked(dapiName))
            ) != dataFeedId
        ) {
            IApi3ServerV1(api3ServerV1).setDapiName(dapiName, dataFeedId);
        }
    }

    /// @notice Updates the current subscription that has ended with the one
    /// that will end next
    /// @param dapiName dAPI name
    /// @param currentSubscriptionId Current subscription ID
    function updateEndedCurrentSubscriptionId(
        bytes32 dapiName,
        bytes32 currentSubscriptionId
    ) private {
        do {
            currentSubscriptionId = subscriptions[currentSubscriptionId]
                .nextSubscriptionId;
        } while (
            currentSubscriptionId != bytes32(0) &&
                subscriptions[currentSubscriptionId].endTimestamp <=
                block.timestamp
        );
        emit UpdatedCurrentSubscriptionId(dapiName, currentSubscriptionId);
        dapiNameToCurrentSubscriptionId[dapiName] = currentSubscriptionId;
        if (currentSubscriptionId == bytes32(0)) {
            IAirseekerRegistry(airseekerRegistry).setDapiNameToBeDeactivated(
                dapiName
            );
        } else {
            IAirseekerRegistry(airseekerRegistry).setDapiNameUpdateParameters(
                dapiName,
                subscriptionIdToUpdateParameters(currentSubscriptionId)
            );
        }
    }

    /// @notice Prospects the subscription position in the queue. It iterates
    /// through the entire subscription queue, which is implemented as a linked
    /// list, and returns the previous and next nodes of the subscription to be
    /// added.
    /// It reverts if no suitable position can be found, which would be because
    /// the addition of the subscription to the queue does not upgrade its
    /// specs unambiguously or the addition of it results in the maximum queue
    /// length to be exceeded.
    /// @param dapiName dAPI name
    /// @param updateParameters Update parameters
    /// @param duration Subscription duration
    /// @return subscriptionId Subscription ID
    /// @return endTimestamp End timestamp
    /// @return previousSubscriptionId Previous subscription ID
    /// @return nextSubscriptionId Next subscription ID
    function prospectSubscriptionPositionInQueue(
        bytes32 dapiName,
        bytes calldata updateParameters,
        uint256 duration
    )
        private
        view
        returns (
            bytes32 subscriptionId,
            uint32 endTimestamp,
            bytes32 previousSubscriptionId,
            bytes32 nextSubscriptionId
        )
    {
        subscriptionId = keccak256(
            abi.encodePacked(dapiName, keccak256(updateParameters))
        );
        endTimestamp = SafeCast.toUint32(block.timestamp + duration);
        (
            uint256 deviationThresholdInPercentage,
            int224 deviationReference,
            uint256 heartbeatInterval
        ) = abi.decode(updateParameters, (uint256, int224, uint256));
        uint256 newQueueLength = 0;
        Subscription storage queuedSubscription;
        for (
            bytes32 queuedSubscriptionId = dapiNameToCurrentSubscriptionId[
                dapiName
            ];
            queuedSubscriptionId != bytes32(0);
            queuedSubscriptionId = queuedSubscription.nextSubscriptionId
        ) {
            queuedSubscription = subscriptions[queuedSubscriptionId];
            UpdateParametersComparisonResult updateParametersComparisonResult = compareUpdateParametersWithQueued(
                    deviationThresholdInPercentage,
                    deviationReference,
                    heartbeatInterval,
                    queuedSubscription.updateParametersHash
                );
            uint32 queuedSubscriptionEndTimestamp = queuedSubscription
                .endTimestamp;
            require(
                updateParametersComparisonResult ==
                    UpdateParametersComparisonResult.BetterThanQueued ||
                    endTimestamp > queuedSubscriptionEndTimestamp,
                "Subscription does not upgrade"
            );
            if (
                updateParametersComparisonResult ==
                UpdateParametersComparisonResult.WorseThanQueued &&
                queuedSubscriptionEndTimestamp > block.timestamp
            ) {
                previousSubscriptionId = queuedSubscriptionId;
                newQueueLength++;
            }
            if (
                updateParametersComparisonResult ==
                UpdateParametersComparisonResult.BetterThanQueued &&
                endTimestamp < queuedSubscriptionEndTimestamp
            ) {
                nextSubscriptionId = queuedSubscriptionId;
                for (
                    ;
                    queuedSubscriptionId != bytes32(0);
                    queuedSubscriptionId = subscriptions[queuedSubscriptionId]
                        .nextSubscriptionId
                ) {
                    newQueueLength++;
                }
                break;
            }
        }
        require(
            newQueueLength < maximumSubscriptionQueueLength,
            "Subscription queue full"
        );
    }

    /// @notice Compares the update parameters with the ones that belong to a
    /// queued subscription
    /// @param deviationThresholdInPercentage Deviation threshold in percentage
    /// @param deviationReference Deviation reference
    /// @param heartbeatInterval Heartbeat interval
    /// @param queuedUpdateParametersHash Queued update parameters hash
    /// @return Update parameters comparison result
    function compareUpdateParametersWithQueued(
        uint256 deviationThresholdInPercentage,
        int224 deviationReference,
        uint256 heartbeatInterval,
        bytes32 queuedUpdateParametersHash
    ) private view returns (UpdateParametersComparisonResult) {
        // The update parameters that belong to a queued subscription are
        // guaranteed to have been stored in the hash map
        (
            uint256 queuedDeviationThresholdInPercentage,
            int224 queuedDeviationReference,
            uint256 queuedHeartbeatInterval
        ) = abi.decode(
                updateParametersHashToValue[queuedUpdateParametersHash],
                (uint256, int224, uint256)
            );
        require(
            deviationReference == queuedDeviationReference,
            "Deviation references not equal"
        );
        if (
            (deviationThresholdInPercentage ==
                queuedDeviationThresholdInPercentage) &&
            (heartbeatInterval == queuedHeartbeatInterval)
        ) {
            return UpdateParametersComparisonResult.EqualToQueued;
        } else if (
            (deviationThresholdInPercentage <=
                queuedDeviationThresholdInPercentage) &&
            (heartbeatInterval <= queuedHeartbeatInterval)
        ) {
            return UpdateParametersComparisonResult.BetterThanQueued;
        } else if (
            (deviationThresholdInPercentage >=
                queuedDeviationThresholdInPercentage) &&
            (heartbeatInterval >= queuedHeartbeatInterval)
        ) {
            return UpdateParametersComparisonResult.WorseThanQueued;
        } else {
            // This is hit when the set of parameters are superior to each
            // other in different aspects, in which case they should not be
            // allowed to be in the same queue
            revert("Update parameters incomparable");
        }
    }

    /// @notice Validates the readiness of the data feed. The data feed must
    /// have been updated on Api3ServerV1 in the last `MAXIMUM_DAPI_UPDATE_AGE`
    /// and registered on AirseekerRegistry.
    /// @param dataFeedId Data feed ID
    function validateDataFeedReadiness(bytes32 dataFeedId) private view {
        (, uint32 timestamp) = IApi3ServerV1(api3ServerV1).dataFeeds(
            dataFeedId
        );
        require(
            block.timestamp <= timestamp + MAXIMUM_DAPI_UPDATE_AGE,
            "Data feed value stale"
        );
        require(
            IAirseekerRegistry(airseekerRegistry).dataFeedIsRegistered(
                dataFeedId
            ),
            "Data feed not registered"
        );
    }

    /// @notice Verifies the dAPI management Merkle proof
    /// @param dapiName dAPI name
    /// @param dataFeedId Data feed ID
    /// @param sponsorWallet Sponsor wallet address
    /// @param dapiManagementMerkleData ABI-encoded dAPI management Merkle root
    /// and proof
    function verifyDapiManagementMerkleProof(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata dapiManagementMerkleData
    ) private view {
        require(dapiName != bytes32(0), "dAPI name zero");
        (
            bytes32 dapiManagementMerkleRoot,
            bytes32[] memory dapiManagementMerkleProof
        ) = abi.decode(dapiManagementMerkleData, (bytes32, bytes32[]));
        require(
            hashes[DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE].value ==
                dapiManagementMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                dapiManagementMerkleProof,
                dapiManagementMerkleRoot,
                keccak256(
                    bytes.concat(
                        keccak256(
                            abi.encode(dapiName, dataFeedId, sponsorWallet)
                        )
                    )
                )
            ),
            "Invalid proof"
        );
    }

    function verifyDapiManagementAndDapiPricingMerkleProofs(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    ) private view {
        require(dapiName != bytes32(0), "dAPI name zero");
        require(
            updateParameters.length == UPDATE_PARAMETERS_LENGTH,
            "Update parameters length invalid"
        );
        require(duration != 0, "Duration zero");
        require(price != 0, "Price zero");
        (
            bytes32 dapiManagementMerkleRoot,
            bytes32[] memory dapiManagementMerkleProof,
            bytes32 dapiPricingMerkleRoot,
            bytes32[] memory dapiPricingMerkleProof
        ) = abi.decode(
                dapiManagementAndDapiPricingMerkleData,
                (bytes32, bytes32[], bytes32, bytes32[])
            );
        require(
            hashes[DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE].value ==
                dapiManagementMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                dapiManagementMerkleProof,
                dapiManagementMerkleRoot,
                keccak256(
                    bytes.concat(
                        keccak256(
                            abi.encode(dapiName, dataFeedId, sponsorWallet)
                        )
                    )
                )
            ),
            "Invalid proof"
        );
        require(
            hashes[DAPI_PRICING_MERKLE_ROOT_HASH_TYPE].value ==
                dapiPricingMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                dapiPricingMerkleProof,
                dapiPricingMerkleRoot,
                keccak256(
                    bytes.concat(
                        keccak256(
                            abi.encode(
                                dapiName,
                                block.chainid,
                                updateParameters,
                                duration,
                                price
                            )
                        )
                    )
                )
            ),
            "Invalid proof"
        );
    }

    /// @notice Verifies the signed API URL Merkle proof
    /// @param airnode Airnode address
    /// @param signedApiUrl Signed API URL
    /// @param signedApiUrlMerkleData ABI-encoded signed API URL Merkle root
    /// and proof
    function verifySignedApiUrlMerkleProof(
        address airnode,
        string calldata signedApiUrl,
        bytes calldata signedApiUrlMerkleData
    ) private view {
        (
            bytes32 signedApiUrlMerkleRoot,
            bytes32[] memory signedApiUrlMerkleProof
        ) = abi.decode(signedApiUrlMerkleData, (bytes32, bytes32[]));
        require(
            hashes[SIGNED_API_URL_MERKLE_ROOT_HASH_TYPE].value ==
                signedApiUrlMerkleRoot,
            "Invalid root"
        );
        require(
            MerkleProof.verify(
                signedApiUrlMerkleProof,
                signedApiUrlMerkleRoot,
                keccak256(
                    bytes.concat(keccak256(abi.encode(airnode, signedApiUrl)))
                )
            ),
            "Invalid proof"
        );
    }

    /// @notice Derives the Beacon ID from the Airnode address and template ID
    /// @param airnode Airnode address
    /// @param templateId Template ID
    /// @return beaconId Beacon ID
    function deriveBeaconId(
        address airnode,
        bytes32 templateId
    ) private pure returns (bytes32 beaconId) {
        beaconId = keccak256(abi.encodePacked(airnode, templateId));
    }
}

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

import "../../access/interfaces/IOwnable.sol";
import "../../utils/interfaces/IExtendedSelfMulticall.sol";

interface IAirseekerRegistry is IOwnable, IExtendedSelfMulticall {
    event ActivatedDataFeedId(bytes32 indexed dataFeedId);

    event ActivatedDapiName(bytes32 indexed dapiName);

    event DeactivatedDataFeedId(bytes32 indexed dataFeedId);

    event DeactivatedDapiName(bytes32 indexed dapiName);

    event UpdatedDataFeedIdUpdateParameters(
        bytes32 indexed dataFeedId,
        bytes updateParameters
    );

    event UpdatedDapiNameUpdateParameters(
        bytes32 indexed dapiName,
        bytes updateParameters
    );

    event UpdatedSignedApiUrl(address indexed airnode, string signedApiUrl);

    event RegisteredDataFeed(bytes32 indexed dataFeedId, bytes dataFeedDetails);

    function setDataFeedIdToBeActivated(bytes32 dataFeedId) external;

    function setDapiNameToBeActivated(bytes32 dapiName) external;

    function setDataFeedIdToBeDeactivated(bytes32 dataFeedId) external;

    function setDapiNameToBeDeactivated(bytes32 dapiName) external;

    function setDataFeedIdUpdateParameters(
        bytes32 dataFeedId,
        bytes calldata updateParameters
    ) external;

    function setDapiNameUpdateParameters(
        bytes32 dapiName,
        bytes calldata updateParameters
    ) external;

    function setSignedApiUrl(
        address airnode,
        string calldata signedApiUrl
    ) external;

    function registerDataFeed(
        bytes calldata dataFeedDetails
    ) external returns (bytes32 dataFeedId);

    function activeDataFeed(
        uint256 index
    )
        external
        view
        returns (
            bytes32 dataFeedId,
            bytes32 dapiName,
            bytes memory dataFeedDetails,
            int224 dataFeedValue,
            uint32 dataFeedTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps,
            bytes memory updateParameters,
            string[] memory signedApiUrls
        );

    function activeDataFeedCount() external view returns (uint256);

    function activeDataFeedIdCount() external view returns (uint256);

    function activeDapiNameCount() external view returns (uint256);

    function dataFeedIdToUpdateParameters(
        bytes32 dataFeedId
    ) external view returns (bytes memory updateParameters);

    function dapiNameToUpdateParameters(
        bytes32 dapiName
    ) external view returns (bytes memory updateParameters);

    function dataFeedIsRegistered(
        bytes32 dataFeedId
    ) external view returns (bool);

    function MAXIMUM_BEACON_COUNT_IN_SET() external view returns (uint256);

    function MAXIMUM_UPDATE_PARAMETERS_LENGTH() external view returns (uint256);

    function MAXIMUM_SIGNED_API_URL_LENGTH() external view returns (uint256);

    function api3ServerV1() external view returns (address);

    function airnodeToSignedApiUrl(
        address airnode
    ) external view returns (string memory signedApiUrl);

    function dataFeedIdToDetails(
        bytes32 dataFeedId
    ) external view returns (bytes memory dataFeedDetails);
}

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

import "../../access/interfaces/IHashRegistry.sol";
import "../../utils/interfaces/IExtendedSelfMulticall.sol";

interface IApi3MarketV2 is IHashRegistry, IExtendedSelfMulticall {
    event SetAirseekerRegistry(address airseekerRegistry);

    event BoughtSubscription(
        bytes32 indexed dapiName,
        bytes32 indexed subscriptionId,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes updateParameters,
        uint256 duration,
        uint256 price,
        uint256 paymentAmount
    );

    event CanceledSubscriptions(bytes32 indexed dapiName);

    event UpdatedCurrentSubscriptionId(
        bytes32 indexed dapiName,
        bytes32 indexed subscriptionId
    );

    function setAirseekerRegistry(address airseekerRegistry_) external;

    function buySubscription(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    ) external payable returns (bytes32 subscriptionId);

    function cancelSubscriptions(bytes32 dapiName) external;

    function updateCurrentSubscriptionId(bytes32 dapiName) external;

    function updateDapiName(
        bytes32 dapiName,
        bytes32 dataFeedId,
        address sponsorWallet,
        bytes calldata dapiManagementMerkleData
    ) external;

    function updateSignedApiUrl(
        address airnode,
        string calldata signedApiUrl,
        bytes calldata signedApiUrlMerkleData
    ) external;

    function multicallAndBuySubscription(
        bytes[] calldata multicallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        returns (bytes[] memory returndata, bytes32 subscriptionId);

    function tryMulticallAndBuySubscription(
        bytes[] calldata tryMulticallData,
        bytes32 dapiName,
        bytes32 dataFeedId,
        address payable sponsorWallet,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price,
        bytes calldata dapiManagementAndDapiPricingMerkleData
    )
        external
        payable
        returns (
            bool[] memory successes,
            bytes[] memory returndata,
            bytes32 subscriptionId
        );

    function updateBeaconWithSignedData(
        address airnode,
        bytes32 templateId,
        uint256 timestamp,
        bytes calldata data,
        bytes calldata signature
    ) external returns (bytes32 beaconId);

    function updateBeaconSetWithBeacons(
        bytes32[] calldata beaconIds
    ) external returns (bytes32 beaconSetId);

    function deployApi3ReaderProxyV1(
        bytes32 dapiName,
        uint256 dappId,
        bytes calldata metadata
    ) external returns (address api3ReaderProxyV1);

    function registerDataFeed(
        bytes calldata dataFeedDetails
    ) external returns (bytes32 dataFeedId);

    function computeExpectedSponsorWalletBalance(
        bytes32 dapiName
    ) external view returns (uint256 expectedSponsorWalletBalance);

    function computeExpectedSponsorWalletBalanceAfterSubscriptionIsAdded(
        bytes32 dapiName,
        bytes calldata updateParameters,
        uint256 duration,
        uint256 price
    ) external view returns (uint256 expectedSponsorWalletBalance);

    function getDapiData(
        bytes32 dapiName
    )
        external
        view
        returns (
            bytes memory dataFeedDetails,
            int224 dapiValue,
            uint32 dapiTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps,
            bytes[] memory updateParameters,
            uint32[] memory endTimestamps,
            uint224[] memory dailyPrices
        );

    function getDataFeedData(
        bytes32 dataFeedId
    )
        external
        view
        returns (
            bytes memory dataFeedDetails,
            int224 dataFeedValue,
            uint32 dataFeedTimestamp,
            int224[] memory beaconValues,
            uint32[] memory beaconTimestamps
        );

    function subscriptionIdToUpdateParameters(
        bytes32 subscriptionId
    ) external view returns (bytes memory updateParameters);

    function DAPI_MANAGEMENT_MERKLE_ROOT_HASH_TYPE()
        external
        view
        returns (bytes32);

    function DAPI_PRICING_MERKLE_ROOT_HASH_TYPE()
        external
        view
        returns (bytes32);

    function SIGNED_API_URL_MERKLE_ROOT_HASH_TYPE()
        external
        view
        returns (bytes32);

    function MAXIMUM_DAPI_UPDATE_AGE() external view returns (uint256);

    function api3ServerV1() external view returns (address);

    function api3ReaderProxyV1Factory() external view returns (address);

    function airseekerRegistry() external view returns (address);

    function maximumSubscriptionQueueLength() external view returns (uint256);

    function subscriptions(
        bytes32 subscriptionId
    )
        external
        view
        returns (
            bytes32 updateParametersHash,
            uint32 endTimestamp,
            uint224 dailyPrice,
            bytes32 nextSubscriptionId
        );

    function dapiNameToCurrentSubscriptionId(
        bytes32 dapiName
    ) external view returns (bytes32 currentSubscriptionId);
}

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

import "./IOevDapiServer.sol";
import "./IBeaconUpdatesWithSignedData.sol";

interface IApi3ServerV1 is IOevDapiServer, IBeaconUpdatesWithSignedData {
    function readDataFeedWithId(
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);

    function readDataFeedWithDapiNameHash(
        bytes32 dapiNameHash
    ) external view returns (int224 value, uint32 timestamp);

    function readDataFeedWithIdAsOevProxy(
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);

    function readDataFeedWithDapiNameHashAsOevProxy(
        bytes32 dapiNameHash
    ) external view returns (int224 value, uint32 timestamp);

    function dataFeeds(
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);

    function oevProxyToIdToDataFeed(
        address proxy,
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);
}

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

import "../../access/interfaces/IAccessControlRegistryAdminnedWithManager.sol";
import "../interfaces/IDataFeedServer.sol";

interface IApi3ServerV1OevExtension is
    IAccessControlRegistryAdminnedWithManager,
    IDataFeedServer
{
    event Withdrew(address recipient, uint256 amount, address sender);

    event PaidOevBid(
        uint256 indexed dappId,
        address indexed updater,
        uint256 bidAmount,
        uint256 signedDataTimestampCutoff,
        address auctioneer
    );

    event UpdatedDappOevDataFeed(
        uint256 indexed dappId,
        address indexed updater,
        bytes32 dataFeedId,
        int224 updatedValue,
        uint32 updatedTimestamp
    );

    function withdraw(address recipient, uint256 amount) external;

    function payOevBid(
        uint256 dappId,
        uint256 bidAmount,
        uint32 signedDataTimestampCutoff,
        bytes calldata signature,
        bytes calldata data
    ) external;

    function updateDappOevDataFeed(
        uint256 dappId,
        bytes[] calldata signedData
    )
        external
        returns (
            bytes32 baseDataFeedId,
            int224 updatedValue,
            uint32 updatedTimestamp
        );

    function simulateDappOevDataFeedUpdate(
        uint256 dappId,
        bytes[] calldata signedData
    )
        external
        returns (
            bytes32 baseDataFeedId,
            int224 updatedValue,
            uint32 updatedTimestamp
        );

    function simulateExternalCall(
        address target,
        bytes calldata data
    ) external returns (bytes memory);

    function oevDataFeed(
        uint256 dappId,
        bytes32 dataFeedId
    ) external view returns (int224 value, uint32 timestamp);

    // solhint-disable-next-line func-name-mixedcase
    function WITHDRAWER_ROLE_DESCRIPTION()
        external
        view
        returns (string memory);

    // solhint-disable-next-line func-name-mixedcase
    function AUCTIONEER_ROLE_DESCRIPTION()
        external
        view
        returns (string memory);

    function withdrawerRole() external view returns (bytes32);

    function auctioneerRole() external view returns (bytes32);

    function api3ServerV1() external view returns (address);

    function dappIdToLastPaidBid(
        uint256 dappId
    ) external view returns (address updater, uint32 endTimestamp);
}

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

import "./IDataFeedServer.sol";

interface IBeaconUpdatesWithSignedData is IDataFeedServer {
    function updateBeaconWithSignedData(
        address airnode,
        bytes32 templateId,
        uint256 timestamp,
        bytes calldata data,
        bytes calldata signature
    ) external returns (bytes32 beaconId);
}

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

import "../../access/interfaces/IAccessControlRegistryAdminnedWithManager.sol";
import "./IDataFeedServer.sol";

interface IDapiServer is
    IAccessControlRegistryAdminnedWithManager,
    IDataFeedServer
{
    event SetDapiName(
        bytes32 indexed dataFeedId,
        bytes32 indexed dapiName,
        address sender
    );

    function setDapiName(bytes32 dapiName, bytes32 dataFeedId) external;

    function dapiNameToDataFeedId(
        bytes32 dapiName
    ) external view returns (bytes32);

    // solhint-disable-next-line func-name-mixedcase
    function DAPI_NAME_SETTER_ROLE_DESCRIPTION()
        external
        view
        returns (string memory);

    function dapiNameSetterRole() external view returns (bytes32);

    function dapiNameHashToDataFeedId(
        bytes32 dapiNameHash
    ) external view returns (bytes32 dataFeedId);
}

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

import "../../utils/interfaces/IExtendedSelfMulticall.sol";

interface IDataFeedServer is IExtendedSelfMulticall {
    event UpdatedBeaconWithSignedData(
        bytes32 indexed beaconId,
        int224 value,
        uint32 timestamp
    );

    event UpdatedBeaconSetWithBeacons(
        bytes32 indexed beaconSetId,
        int224 value,
        uint32 timestamp
    );

    function updateBeaconSetWithBeacons(
        bytes32[] memory beaconIds
    ) external returns (bytes32 beaconSetId);
}

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

import "./IOevDataFeedServer.sol";
import "./IDapiServer.sol";

interface IOevDapiServer is IOevDataFeedServer, IDapiServer {}

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

import "./IDataFeedServer.sol";

interface IOevDataFeedServer is IDataFeedServer {
    event UpdatedOevProxyBeaconWithSignedData(
        bytes32 indexed beaconId,
        address indexed proxy,
        bytes32 indexed updateId,
        int224 value,
        uint32 timestamp
    );

    event UpdatedOevProxyBeaconSetWithSignedData(
        bytes32 indexed beaconSetId,
        address indexed proxy,
        bytes32 indexed updateId,
        int224 value,
        uint32 timestamp
    );

    event Withdrew(
        address indexed oevProxy,
        address oevBeneficiary,
        uint256 amount
    );

    function updateOevProxyDataFeedWithSignedData(
        address oevProxy,
        bytes32 dataFeedId,
        bytes32 updateId,
        uint256 timestamp,
        bytes calldata data,
        bytes[] calldata packedOevUpdateSignatures
    ) external payable;

    function withdraw(address oevProxy) external;

    function oevProxyToBalance(
        address oevProxy
    ) external view returns (uint256 balance);
}

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

interface IApi3ReaderProxyV1Factory {
    event DeployedApi3ReaderProxyV1(
        address indexed proxy,
        bytes32 dapiName,
        uint256 dappId,
        bytes metadata
    );

    function deployApi3ReaderProxyV1(
        bytes32 dapiName,
        uint256 dappId,
        bytes calldata metadata
    ) external returns (address proxy);

    function computeApi3ReaderProxyV1Address(
        bytes32 dapiName,
        uint256 dappId,
        bytes calldata metadata
    ) external view returns (address proxy);

    function api3ServerV1OevExtension() external returns (address);
}

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

import "./SelfMulticall.sol";
import "./interfaces/IExtendedSelfMulticall.sol";

/// @title Contract that extends SelfMulticall to fetch some of the global
/// variables
/// @notice Available global variables are limited to the ones that Airnode
/// tends to need
contract ExtendedSelfMulticall is SelfMulticall, IExtendedSelfMulticall {
    /// @notice Returns the chain ID
    /// @return Chain ID
    function getChainId() external view override returns (uint256) {
        return block.chainid;
    }

    /// @notice Returns the account balance
    /// @param account Account address
    /// @return Account balance
    function getBalance(
        address account
    ) external view override returns (uint256) {
        return account.balance;
    }

    /// @notice Returns if the account contains bytecode
    /// @dev An account not containing any bytecode does not indicate that it
    /// is an EOA or it will not contain any bytecode in the future.
    /// Contract construction and `SELFDESTRUCT` updates the bytecode at the
    /// end of the transaction.
    /// @return If the account contains bytecode
    function containsBytecode(
        address account
    ) external view override returns (bool) {
        return account.code.length > 0;
    }

    /// @notice Returns the current block number
    /// @return Current block number
    function getBlockNumber() external view override returns (uint256) {
        return block.number;
    }

    /// @notice Returns the current block timestamp
    /// @return Current block timestamp
    function getBlockTimestamp() external view override returns (uint256) {
        return block.timestamp;
    }

    /// @notice Returns the current block basefee
    /// @return Current block basefee
    function getBlockBasefee() external view override returns (uint256) {
        return block.basefee;
    }
}

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

import "./ISelfMulticall.sol";

interface IExtendedSelfMulticall is ISelfMulticall {
    function getChainId() external view returns (uint256);

    function getBalance(address account) external view returns (uint256);

    function containsBytecode(address account) external view returns (bool);

    function getBlockNumber() external view returns (uint256);

    function getBlockTimestamp() external view returns (uint256);

    function getBlockBasefee() external view returns (uint256);
}

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

interface ISelfMulticall {
    function multicall(
        bytes[] calldata data
    ) external returns (bytes[] memory returndata);

    function tryMulticall(
        bytes[] calldata data
    ) external returns (bool[] memory successes, bytes[] memory returndata);
}

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

import "./interfaces/ISelfMulticall.sol";

/// @title Contract that enables calls to the inheriting contract to be batched
/// @notice Implements two ways of batching, one requires none of the calls to
/// revert and the other tolerates individual calls reverting
/// @dev This implementation uses delegatecall for individual function calls.
/// Since delegatecall is a message call, it can only be made to functions that
/// are externally visible. This means that a contract cannot multicall its own
/// functions that use internal/private visibility modifiers.
/// Refer to OpenZeppelin's Multicall.sol for a similar implementation.
contract SelfMulticall is ISelfMulticall {
    /// @notice Batches calls to the inheriting contract and reverts as soon as
    /// one of the batched calls reverts
    /// @param data Array of calldata of batched calls
    /// @return returndata Array of returndata of batched calls
    function multicall(
        bytes[] calldata data
    ) external override returns (bytes[] memory returndata) {
        uint256 callCount = data.length;
        returndata = new bytes[](callCount);
        for (uint256 ind = 0; ind < callCount; ) {
            bool success;
            // solhint-disable-next-line avoid-low-level-calls
            (success, returndata[ind]) = address(this).delegatecall(data[ind]);
            if (!success) {
                bytes memory returndataWithRevertData = returndata[ind];
                if (returndataWithRevertData.length > 0) {
                    // Adapted from OpenZeppelin's Address.sol
                    // solhint-disable-next-line no-inline-assembly
                    assembly {
                        let returndata_size := mload(returndataWithRevertData)
                        revert(
                            add(32, returndataWithRevertData),
                            returndata_size
                        )
                    }
                } else {
                    revert("Multicall: No revert string");
                }
            }
            unchecked {
                ind++;
            }
        }
    }

    /// @notice Batches calls to the inheriting contract but does not revert if
    /// any of the batched calls reverts
    /// @param data Array of calldata of batched calls
    /// @return successes Array of success conditions of batched calls
    /// @return returndata Array of returndata of batched calls
    function tryMulticall(
        bytes[] calldata data
    )
        external
        override
        returns (bool[] memory successes, bytes[] memory returndata)
    {
        uint256 callCount = data.length;
        successes = new bool[](callCount);
        returndata = new bytes[](callCount);
        for (uint256 ind = 0; ind < callCount; ) {
            // solhint-disable-next-line avoid-low-level-calls
            (successes[ind], returndata[ind]) = address(this).delegatecall(
                data[ind]
            );
            unchecked {
                ind++;
            }
        }
    }
}

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

pragma solidity ^0.8.20;

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

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

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

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

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

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

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

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

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

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

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

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

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

pragma solidity ^0.8.20;

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

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

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

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

pragma solidity ^0.8.20;

/**
 * @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
    }

    /**
     * @dev The signature derives the `address(0)`.
     */
    error ECDSAInvalidSignature();

    /**
     * @dev The signature has an invalid length.
     */
    error ECDSAInvalidSignatureLength(uint256 length);

    /**
     * @dev The signature has an S value that is in the upper half order.
     */
    error ECDSAInvalidSignatureS(bytes32 s);

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with `signature` or an error. This will not
     * return address(0) without also returning an error description. Errors are documented using an enum (error type)
     * and a bytes32 providing additional information about the error.
     *
     * If no error is returned, then the address can be used for verification purposes.
     *
     * The `ecrecover` EVM precompile 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 {MessageHashUtils-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]
     */
    function tryRecover(bytes32 hash, bytes memory signature) internal pure returns (address, RecoverError, bytes32) {
        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, bytes32(signature.length));
        }
    }

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with
     * `signature`. This address can then be used for verification purposes.
     *
     * The `ecrecover` EVM precompile 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 {MessageHashUtils-toEthSignedMessageHash} on it.
     */
    function recover(bytes32 hash, bytes memory signature) internal pure returns (address) {
        (address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, signature);
        _throwError(error, errorArg);
        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]
     */
    function tryRecover(bytes32 hash, bytes32 r, bytes32 vs) internal pure returns (address, RecoverError, bytes32) {
        unchecked {
            bytes32 s = vs & bytes32(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff);
            // We do not check for an overflow here since the shift operation results in 0 or 1.
            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.
     */
    function recover(bytes32 hash, bytes32 r, bytes32 vs) internal pure returns (address) {
        (address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, r, vs);
        _throwError(error, errorArg);
        return recovered;
    }

    /**
     * @dev Overload of {ECDSA-tryRecover} that receives the `v`,
     * `r` and `s` signature fields separately.
     */
    function tryRecover(
        bytes32 hash,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) internal pure returns (address, RecoverError, bytes32) {
        // 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, s);
        }

        // 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, bytes32(0));
        }

        return (signer, RecoverError.NoError, bytes32(0));
    }

    /**
     * @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, bytes32 errorArg) = tryRecover(hash, v, r, s);
        _throwError(error, errorArg);
        return recovered;
    }

    /**
     * @dev Optionally reverts with the corresponding custom error according to the `error` argument provided.
     */
    function _throwError(RecoverError error, bytes32 errorArg) private pure {
        if (error == RecoverError.NoError) {
            return; // no error: do nothing
        } else if (error == RecoverError.InvalidSignature) {
            revert ECDSAInvalidSignature();
        } else if (error == RecoverError.InvalidSignatureLength) {
            revert ECDSAInvalidSignatureLength(uint256(errorArg));
        } else if (error == RecoverError.InvalidSignatureS) {
            revert ECDSAInvalidSignatureS(errorArg);
        }
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/cryptography/MerkleProof.sol)

pragma solidity ^0.8.20;

/**
 * @dev These functions deal with verification of Merkle Tree proofs.
 *
 * The tree and the proofs can be generated using our
 * https://github.com/OpenZeppelin/merkle-tree[JavaScript library].
 * You will find a quickstart guide in the readme.
 *
 * WARNING: You should avoid using leaf values that are 64 bytes long prior to
 * hashing, or use a hash function other than keccak256 for hashing leaves.
 * This is because the concatenation of a sorted pair of internal nodes in
 * the Merkle tree could be reinterpreted as a leaf value.
 * OpenZeppelin's JavaScript library generates Merkle trees that are safe
 * against this attack out of the box.
 */
library MerkleProof {
    /**
     *@dev The multiproof provided is not valid.
     */
    error MerkleProofInvalidMultiproof();

    /**
     * @dev Returns true if a `leaf` can be proved to be a part of a Merkle tree
     * defined by `root`. For this, a `proof` must be provided, containing
     * sibling hashes on the branch from the leaf to the root of the tree. Each
     * pair of leaves and each pair of pre-images are assumed to be sorted.
     */
    function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
        return processProof(proof, leaf) == root;
    }

    /**
     * @dev Calldata version of {verify}
     */
    function verifyCalldata(bytes32[] calldata proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
        return processProofCalldata(proof, leaf) == root;
    }

    /**
     * @dev Returns the rebuilt hash obtained by traversing a Merkle tree up
     * from `leaf` using `proof`. A `proof` is valid if and only if the rebuilt
     * hash matches the root of the tree. When processing the proof, the pairs
     * of leafs & pre-images are assumed to be sorted.
     */
    function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    /**
     * @dev Calldata version of {processProof}
     */
    function processProofCalldata(bytes32[] calldata proof, bytes32 leaf) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    /**
     * @dev Returns true if the `leaves` can be simultaneously proven to be a part of a Merkle tree defined by
     * `root`, according to `proof` and `proofFlags` as described in {processMultiProof}.
     *
     * CAUTION: Not all Merkle trees admit multiproofs. See {processMultiProof} for details.
     */
    function multiProofVerify(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        bytes32 root,
        bytes32[] memory leaves
    ) internal pure returns (bool) {
        return processMultiProof(proof, proofFlags, leaves) == root;
    }

    /**
     * @dev Calldata version of {multiProofVerify}
     *
     * CAUTION: Not all Merkle trees admit multiproofs. See {processMultiProof} for details.
     */
    function multiProofVerifyCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        bytes32 root,
        bytes32[] memory leaves
    ) internal pure returns (bool) {
        return processMultiProofCalldata(proof, proofFlags, leaves) == root;
    }

    /**
     * @dev Returns the root of a tree reconstructed from `leaves` and sibling nodes in `proof`. The reconstruction
     * proceeds by incrementally reconstructing all inner nodes by combining a leaf/inner node with either another
     * leaf/inner node or a proof sibling node, depending on whether each `proofFlags` item is true or false
     * respectively.
     *
     * CAUTION: Not all Merkle trees admit multiproofs. To use multiproofs, it is sufficient to ensure that: 1) the tree
     * is complete (but not necessarily perfect), 2) the leaves to be proven are in the opposite order they are in the
     * tree (i.e., as seen from right to left starting at the deepest layer and continuing at the next layer).
     */
    function processMultiProof(
        bytes32[] memory proof,
        bool[] memory proofFlags,
        bytes32[] memory leaves
    ) internal pure returns (bytes32 merkleRoot) {
        // This function rebuilds the root hash by traversing the tree up from the leaves. The root is rebuilt by
        // consuming and producing values on a queue. The queue starts with the `leaves` array, then goes onto the
        // `hashes` array. At the end of the process, the last hash in the `hashes` array should contain the root of
        // the Merkle tree.
        uint256 leavesLen = leaves.length;
        uint256 proofLen = proof.length;
        uint256 totalHashes = proofFlags.length;

        // Check proof validity.
        if (leavesLen + proofLen != totalHashes + 1) {
            revert MerkleProofInvalidMultiproof();
        }

        // The xxxPos values are "pointers" to the next value to consume in each array. All accesses are done using
        // `xxx[xxxPos++]`, which return the current value and increment the pointer, thus mimicking a queue's "pop".
        bytes32[] memory hashes = new bytes32[](totalHashes);
        uint256 leafPos = 0;
        uint256 hashPos = 0;
        uint256 proofPos = 0;
        // At each step, we compute the next hash using two values:
        // - a value from the "main queue". If not all leaves have been consumed, we get the next leaf, otherwise we
        //   get the next hash.
        // - depending on the flag, either another value from the "main queue" (merging branches) or an element from the
        //   `proof` array.
        for (uint256 i = 0; i < totalHashes; i++) {
            bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
            bytes32 b = proofFlags[i]
                ? (leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++])
                : proof[proofPos++];
            hashes[i] = _hashPair(a, b);
        }

        if (totalHashes > 0) {
            if (proofPos != proofLen) {
                revert MerkleProofInvalidMultiproof();
            }
            unchecked {
                return hashes[totalHashes - 1];
            }
        } else if (leavesLen > 0) {
            return leaves[0];
        } else {
            return proof[0];
        }
    }

    /**
     * @dev Calldata version of {processMultiProof}.
     *
     * CAUTION: Not all Merkle trees admit multiproofs. See {processMultiProof} for details.
     */
    function processMultiProofCalldata(
        bytes32[] calldata proof,
        bool[] calldata proofFlags,
        bytes32[] memory leaves
    ) internal pure returns (bytes32 merkleRoot) {
        // This function rebuilds the root hash by traversing the tree up from the leaves. The root is rebuilt by
        // consuming and producing values on a queue. The queue starts with the `leaves` array, then goes onto the
        // `hashes` array. At the end of the process, the last hash in the `hashes` array should contain the root of
        // the Merkle tree.
        uint256 leavesLen = leaves.length;
        uint256 proofLen = proof.length;
        uint256 totalHashes = proofFlags.length;

        // Check proof validity.
        if (leavesLen + proofLen != totalHashes + 1) {
            revert MerkleProofInvalidMultiproof();
        }

        // The xxxPos values are "pointers" to the next value to consume in each array. All accesses are done using
        // `xxx[xxxPos++]`, which return the current value and increment the pointer, thus mimicking a queue's "pop".
        bytes32[] memory hashes = new bytes32[](totalHashes);
        uint256 leafPos = 0;
        uint256 hashPos = 0;
        uint256 proofPos = 0;
        // At each step, we compute the next hash using two values:
        // - a value from the "main queue". If not all leaves have been consumed, we get the next leaf, otherwise we
        //   get the next hash.
        // - depending on the flag, either another value from the "main queue" (merging branches) or an element from the
        //   `proof` array.
        for (uint256 i = 0; i < totalHashes; i++) {
            bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
            bytes32 b = proofFlags[i]
                ? (leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++])
                : proof[proofPos++];
            hashes[i] = _hashPair(a, b);
        }

        if (totalHashes > 0) {
            if (proofPos != proofLen) {
                revert MerkleProofInvalidMultiproof();
            }
            unchecked {
                return hashes[totalHashes - 1];
            }
        } else if (leavesLen > 0) {
            return leaves[0];
        } else {
            return proof[0];
        }
    }

    /**
     * @dev Sorts the pair (a, b) and hashes the result.
     */
    function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
        return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
    }

    /**
     * @dev Implementation of keccak256(abi.encode(a, b)) that doesn't allocate or expand memory.
     */
    function _efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32 value) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x00, a)
            mstore(0x20, b)
            value := keccak256(0x00, 0x40)
        }
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/cryptography/MessageHashUtils.sol)

pragma solidity ^0.8.20;

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

/**
 * @dev Signature message hash utilities for producing digests to be consumed by {ECDSA} recovery or signing.
 *
 * The library provides methods for generating a hash of a message that conforms to the
 * https://eips.ethereum.org/EIPS/eip-191[EIP 191] and https://eips.ethereum.org/EIPS/eip-712[EIP 712]
 * specifications.
 */
library MessageHashUtils {
    /**
     * @dev Returns the keccak256 digest of an EIP-191 signed data with version
     * `0x45` (`personal_sign` messages).
     *
     * The digest is calculated by prefixing a bytes32 `messageHash` with
     * `"\x19Ethereum Signed Message:\n32"` and hashing the result. It corresponds with the
     * hash signed when using the https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`] JSON-RPC method.
     *
     * NOTE: The `messageHash` parameter is intended to be the result of hashing a raw message with
     * keccak256, although any bytes32 value can be safely used because the final digest will
     * be re-hashed.
     *
     * See {ECDSA-recover}.
     */
    function toEthSignedMessageHash(bytes32 messageHash) internal pure returns (bytes32 digest) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x00, "\x19Ethereum Signed Message:\n32") // 32 is the bytes-length of messageHash
            mstore(0x1c, messageHash) // 0x1c (28) is the length of the prefix
            digest := keccak256(0x00, 0x3c) // 0x3c is the length of the prefix (0x1c) + messageHash (0x20)
        }
    }

    /**
     * @dev Returns the keccak256 digest of an EIP-191 signed data with version
     * `0x45` (`personal_sign` messages).
     *
     * The digest is calculated by prefixing an arbitrary `message` with
     * `"\x19Ethereum Signed Message:\n" + len(message)` and hashing the result. It corresponds with the
     * hash signed when using the https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`] JSON-RPC method.
     *
     * See {ECDSA-recover}.
     */
    function toEthSignedMessageHash(bytes memory message) internal pure returns (bytes32) {
        return
            keccak256(bytes.concat("\x19Ethereum Signed Message:\n", bytes(Strings.toString(message.length)), message));
    }

    /**
     * @dev Returns the keccak256 digest of an EIP-191 signed data with version
     * `0x00` (data with intended validator).
     *
     * The digest is calculated by prefixing an arbitrary `data` with `"\x19\x00"` and the intended
     * `validator` address. Then hashing the result.
     *
     * See {ECDSA-recover}.
     */
    function toDataWithIntendedValidatorHash(address validator, bytes memory data) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked(hex"19_00", validator, data));
    }

    /**
     * @dev Returns the keccak256 digest of an EIP-712 typed data (EIP-191 version `0x01`).
     *
     * The digest is calculated from a `domainSeparator` and a `structHash`, by prefixing them with
     * `\x19\x01` and hashing the result. It corresponds to the hash signed by the
     * https://eips.ethereum.org/EIPS/eip-712[`eth_signTypedData`] JSON-RPC method as part of EIP-712.
     *
     * See {ECDSA-recover}.
     */
    function toTypedDataHash(bytes32 domainSeparator, bytes32 structHash) internal pure returns (bytes32 digest) {
        /// @solidity memory-safe-assembly
        assembly {
            let ptr := mload(0x40)
            mstore(ptr, hex"19_01")
            mstore(add(ptr, 0x02), domainSeparator)
            mstore(add(ptr, 0x22), structHash)
            digest := keccak256(ptr, 0x42)
        }
    }
}

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

pragma solidity ^0.8.20;

/**
 * @dev Standard math utilities missing in the Solidity language.
 */
library Math {
    /**
     * @dev Muldiv operation overflow.
     */
    error MathOverflowedMulDiv();

    enum Rounding {
        Floor, // Toward negative infinity
        Ceil, // Toward positive infinity
        Trunc, // Toward zero
        Expand // Away from zero
    }

    /**
     * @dev Returns the addition of two unsigned integers, with an overflow flag.
     */
    function tryAdd(uint256 a, uint256 b) internal pure returns (bool, uint256) {
        unchecked {
            uint256 c = a + b;
            if (c < a) return (false, 0);
            return (true, c);
        }
    }

    /**
     * @dev Returns the subtraction of two unsigned integers, with an overflow flag.
     */
    function trySub(uint256 a, uint256 b) internal pure returns (bool, uint256) {
        unchecked {
            if (b > a) return (false, 0);
            return (true, a - b);
        }
    }

    /**
     * @dev Returns the multiplication of two unsigned integers, with an overflow flag.
     */
    function tryMul(uint256 a, uint256 b) internal pure returns (bool, uint256) {
        unchecked {
            // Gas optimization: this is cheaper than requiring 'a' not being zero, but the
            // benefit is lost if 'b' is also tested.
            // See: https://github.com/OpenZeppelin/openzeppelin-contracts/pull/522
            if (a == 0) return (true, 0);
            uint256 c = a * b;
            if (c / a != b) return (false, 0);
            return (true, c);
        }
    }

    /**
     * @dev Returns the division of two unsigned integers, with a division by zero flag.
     */
    function tryDiv(uint256 a, uint256 b) internal pure returns (bool, uint256) {
        unchecked {
            if (b == 0) return (false, 0);
            return (true, a / b);
        }
    }

    /**
     * @dev Returns the remainder of dividing two unsigned integers, with a division by zero flag.
     */
    function tryMod(uint256 a, uint256 b) internal pure returns (bool, uint256) {
        unchecked {
            if (b == 0) return (false, 0);
            return (true, a % b);
        }
    }

    /**
     * @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 towards infinity instead
     * of rounding towards zero.
     */
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        if (b == 0) {
            // Guarantee the same behavior as in a regular Solidity division.
            return a / b;
        }

        // (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 = x * y; // Least significant 256 bits of the product
            uint256 prod1; // Most significant 256 bits of the product
            assembly {
                let mm := mulmod(x, y, not(0))
                prod1 := sub(sub(mm, prod0), lt(mm, prod0))
            }

            // Handle non-overflow cases, 256 by 256 division.
            if (prod1 == 0) {
                // Solidity will revert if denominator == 0, unlike the div opcode on its own.
                // The surrounding unchecked block does not change this fact.
                // See https://docs.soliditylang.org/en/latest/control-structures.html#checked-or-unchecked-arithmetic.
                return prod0 / denominator;
            }

            // Make sure the result is less than 2^256. Also prevents denominator == 0.
            if (denominator <= prod1) {
                revert MathOverflowedMulDiv();
            }

            ///////////////////////////////////////////////
            // 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.

            uint256 twos = denominator & (0 - denominator);
            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 (unsignedRoundsUp(rounding) && 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
     * towards zero.
     *
     * 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 + (unsignedRoundsUp(rounding) && result * result < a ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 2 of a positive value rounded towards zero.
     * 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 + (unsignedRoundsUp(rounding) && 1 << result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 10 of a positive value rounded towards zero.
     * 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 + (unsignedRoundsUp(rounding) && 10 ** result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 256 of a positive value rounded towards zero.
     * 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 256, 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 + (unsignedRoundsUp(rounding) && 1 << (result << 3) < value ? 1 : 0);
        }
    }

    /**
     * @dev Returns whether a provided rounding mode is considered rounding up for unsigned integers.
     */
    function unsignedRoundsUp(Rounding rounding) internal pure returns (bool) {
        return uint8(rounding) % 2 == 1;
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/math/SafeCast.sol)
// This file was procedurally generated from scripts/generate/templates/SafeCast.js.

pragma solidity ^0.8.20;

/**
 * @dev Wrappers over Solidity's uintXX/intXX casting operators with added overflow
 * checks.
 *
 * Downcasting from uint256/int256 in Solidity does not revert on overflow. This can
 * easily result in undesired exploitation or bugs, since developers usually
 * assume that overflows raise errors. `SafeCast` restores this intuition by
 * reverting the transaction when such an operation overflows.
 *
 * Using this library instead of the unchecked operations eliminates an entire
 * class of bugs, so it's recommended to use it always.
 */
library SafeCast {
    /**
     * @dev Value doesn't fit in an uint of `bits` size.
     */
    error SafeCastOverflowedUintDowncast(uint8 bits, uint256 value);

    /**
     * @dev An int value doesn't fit in an uint of `bits` size.
     */
    error SafeCastOverflowedIntToUint(int256 value);

    /**
     * @dev Value doesn't fit in an int of `bits` size.
     */
    error SafeCastOverflowedIntDowncast(uint8 bits, int256 value);

    /**
     * @dev An uint value doesn't fit in an int of `bits` size.
     */
    error SafeCastOverflowedUintToInt(uint256 value);

    /**
     * @dev Returns the downcasted uint248 from uint256, reverting on
     * overflow (when the input is greater than largest uint248).
     *
     * Counterpart to Solidity's `uint248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     */
    function toUint248(uint256 value) internal pure returns (uint248) {
        if (value > type(uint248).max) {
            revert SafeCastOverflowedUintDowncast(248, value);
        }
        return uint248(value);
    }

    /**
     * @dev Returns the downcasted uint240 from uint256, reverting on
     * overflow (when the input is greater than largest uint240).
     *
     * Counterpart to Solidity's `uint240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     */
    function toUint240(uint256 value) internal pure returns (uint240) {
        if (value > type(uint240).max) {
            revert SafeCastOverflowedUintDowncast(240, value);
        }
        return uint240(value);
    }

    /**
     * @dev Returns the downcasted uint232 from uint256, reverting on
     * overflow (when the input is greater than largest uint232).
     *
     * Counterpart to Solidity's `uint232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     */
    function toUint232(uint256 value) internal pure returns (uint232) {
        if (value > type(uint232).max) {
            revert SafeCastOverflowedUintDowncast(232, value);
        }
        return uint232(value);
    }

    /**
     * @dev Returns the downcasted uint224 from uint256, reverting on
     * overflow (when the input is greater than largest uint224).
     *
     * Counterpart to Solidity's `uint224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     */
    function toUint224(uint256 value) internal pure returns (uint224) {
        if (value > type(uint224).max) {
            revert SafeCastOverflowedUintDowncast(224, value);
        }
        return uint224(value);
    }

    /**
     * @dev Returns the downcasted uint216 from uint256, reverting on
     * overflow (when the input is greater than largest uint216).
     *
     * Counterpart to Solidity's `uint216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     */
    function toUint216(uint256 value) internal pure returns (uint216) {
        if (value > type(uint216).max) {
            revert SafeCastOverflowedUintDowncast(216, value);
        }
        return uint216(value);
    }

    /**
     * @dev Returns the downcasted uint208 from uint256, reverting on
     * overflow (when the input is greater than largest uint208).
     *
     * Counterpart to Solidity's `uint208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     */
    function toUint208(uint256 value) internal pure returns (uint208) {
        if (value > type(uint208).max) {
            revert SafeCastOverflowedUintDowncast(208, value);
        }
        return uint208(value);
    }

    /**
     * @dev Returns the downcasted uint200 from uint256, reverting on
     * overflow (when the input is greater than largest uint200).
     *
     * Counterpart to Solidity's `uint200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     */
    function toUint200(uint256 value) internal pure returns (uint200) {
        if (value > type(uint200).max) {
            revert SafeCastOverflowedUintDowncast(200, value);
        }
        return uint200(value);
    }

    /**
     * @dev Returns the downcasted uint192 from uint256, reverting on
     * overflow (when the input is greater than largest uint192).
     *
     * Counterpart to Solidity's `uint192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     */
    function toUint192(uint256 value) internal pure returns (uint192) {
        if (value > type(uint192).max) {
            revert SafeCastOverflowedUintDowncast(192, value);
        }
        return uint192(value);
    }

    /**
     * @dev Returns the downcasted uint184 from uint256, reverting on
     * overflow (when the input is greater than largest uint184).
     *
     * Counterpart to Solidity's `uint184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     */
    function toUint184(uint256 value) internal pure returns (uint184) {
        if (value > type(uint184).max) {
            revert SafeCastOverflowedUintDowncast(184, value);
        }
        return uint184(value);
    }

    /**
     * @dev Returns the downcasted uint176 from uint256, reverting on
     * overflow (when the input is greater than largest uint176).
     *
     * Counterpart to Solidity's `uint176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     */
    function toUint176(uint256 value) internal pure returns (uint176) {
        if (value > type(uint176).max) {
            revert SafeCastOverflowedUintDowncast(176, value);
        }
        return uint176(value);
    }

    /**
     * @dev Returns the downcasted uint168 from uint256, reverting on
     * overflow (when the input is greater than largest uint168).
     *
     * Counterpart to Solidity's `uint168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     */
    function toUint168(uint256 value) internal pure returns (uint168) {
        if (value > type(uint168).max) {
            revert SafeCastOverflowedUintDowncast(168, value);
        }
        return uint168(value);
    }

    /**
     * @dev Returns the downcasted uint160 from uint256, reverting on
     * overflow (when the input is greater than largest uint160).
     *
     * Counterpart to Solidity's `uint160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     */
    function toUint160(uint256 value) internal pure returns (uint160) {
        if (value > type(uint160).max) {
            revert SafeCastOverflowedUintDowncast(160, value);
        }
        return uint160(value);
    }

    /**
     * @dev Returns the downcasted uint152 from uint256, reverting on
     * overflow (when the input is greater than largest uint152).
     *
     * Counterpart to Solidity's `uint152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     */
    function toUint152(uint256 value) internal pure returns (uint152) {
        if (value > type(uint152).max) {
            revert SafeCastOverflowedUintDowncast(152, value);
        }
        return uint152(value);
    }

    /**
     * @dev Returns the downcasted uint144 from uint256, reverting on
     * overflow (when the input is greater than largest uint144).
     *
     * Counterpart to Solidity's `uint144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     */
    function toUint144(uint256 value) internal pure returns (uint144) {
        if (value > type(uint144).max) {
            revert SafeCastOverflowedUintDowncast(144, value);
        }
        return uint144(value);
    }

    /**
     * @dev Returns the downcasted uint136 from uint256, reverting on
     * overflow (when the input is greater than largest uint136).
     *
     * Counterpart to Solidity's `uint136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     */
    function toUint136(uint256 value) internal pure returns (uint136) {
        if (value > type(uint136).max) {
            revert SafeCastOverflowedUintDowncast(136, value);
        }
        return uint136(value);
    }

    /**
     * @dev Returns the downcasted uint128 from uint256, reverting on
     * overflow (when the input is greater than largest uint128).
     *
     * Counterpart to Solidity's `uint128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     */
    function toUint128(uint256 value) internal pure returns (uint128) {
        if (value > type(uint128).max) {
            revert SafeCastOverflowedUintDowncast(128, value);
        }
        return uint128(value);
    }

    /**
     * @dev Returns the downcasted uint120 from uint256, reverting on
     * overflow (when the input is greater than largest uint120).
     *
     * Counterpart to Solidity's `uint120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     */
    function toUint120(uint256 value) internal pure returns (uint120) {
        if (value > type(uint120).max) {
            revert SafeCastOverflowedUintDowncast(120, value);
        }
        return uint120(value);
    }

    /**
     * @dev Returns the downcasted uint112 from uint256, reverting on
     * overflow (when the input is greater than largest uint112).
     *
     * Counterpart to Solidity's `uint112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     */
    function toUint112(uint256 value) internal pure returns (uint112) {
        if (value > type(uint112).max) {
            revert SafeCastOverflowedUintDowncast(112, value);
        }
        return uint112(value);
    }

    /**
     * @dev Returns the downcasted uint104 from uint256, reverting on
     * overflow (when the input is greater than largest uint104).
     *
     * Counterpart to Solidity's `uint104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     */
    function toUint104(uint256 value) internal pure returns (uint104) {
        if (value > type(uint104).max) {
            revert SafeCastOverflowedUintDowncast(104, value);
        }
        return uint104(value);
    }

    /**
     * @dev Returns the downcasted uint96 from uint256, reverting on
     * overflow (when the input is greater than largest uint96).
     *
     * Counterpart to Solidity's `uint96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     */
    function toUint96(uint256 value) internal pure returns (uint96) {
        if (value > type(uint96).max) {
            revert SafeCastOverflowedUintDowncast(96, value);
        }
        return uint96(value);
    }

    /**
     * @dev Returns the downcasted uint88 from uint256, reverting on
     * overflow (when the input is greater than largest uint88).
     *
     * Counterpart to Solidity's `uint88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     */
    function toUint88(uint256 value) internal pure returns (uint88) {
        if (value > type(uint88).max) {
            revert SafeCastOverflowedUintDowncast(88, value);
        }
        return uint88(value);
    }

    /**
     * @dev Returns the downcasted uint80 from uint256, reverting on
     * overflow (when the input is greater than largest uint80).
     *
     * Counterpart to Solidity's `uint80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     */
    function toUint80(uint256 value) internal pure returns (uint80) {
        if (value > type(uint80).max) {
            revert SafeCastOverflowedUintDowncast(80, value);
        }
        return uint80(value);
    }

    /**
     * @dev Returns the downcasted uint72 from uint256, reverting on
     * overflow (when the input is greater than largest uint72).
     *
     * Counterpart to Solidity's `uint72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     */
    function toUint72(uint256 value) internal pure returns (uint72) {
        if (value > type(uint72).max) {
            revert SafeCastOverflowedUintDowncast(72, value);
        }
        return uint72(value);
    }

    /**
     * @dev Returns the downcasted uint64 from uint256, reverting on
     * overflow (when the input is greater than largest uint64).
     *
     * Counterpart to Solidity's `uint64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     */
    function toUint64(uint256 value) internal pure returns (uint64) {
        if (value > type(uint64).max) {
            revert SafeCastOverflowedUintDowncast(64, value);
        }
        return uint64(value);
    }

    /**
     * @dev Returns the downcasted uint56 from uint256, reverting on
     * overflow (when the input is greater than largest uint56).
     *
     * Counterpart to Solidity's `uint56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     */
    function toUint56(uint256 value) internal pure returns (uint56) {
        if (value > type(uint56).max) {
            revert SafeCastOverflowedUintDowncast(56, value);
        }
        return uint56(value);
    }

    /**
     * @dev Returns the downcasted uint48 from uint256, reverting on
     * overflow (when the input is greater than largest uint48).
     *
     * Counterpart to Solidity's `uint48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     */
    function toUint48(uint256 value) internal pure returns (uint48) {
        if (value > type(uint48).max) {
            revert SafeCastOverflowedUintDowncast(48, value);
        }
        return uint48(value);
    }

    /**
     * @dev Returns the downcasted uint40 from uint256, reverting on
     * overflow (when the input is greater than largest uint40).
     *
     * Counterpart to Solidity's `uint40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     */
    function toUint40(uint256 value) internal pure returns (uint40) {
        if (value > type(uint40).max) {
            revert SafeCastOverflowedUintDowncast(40, value);
        }
        return uint40(value);
    }

    /**
     * @dev Returns the downcasted uint32 from uint256, reverting on
     * overflow (when the input is greater than largest uint32).
     *
     * Counterpart to Solidity's `uint32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     */
    function toUint32(uint256 value) internal pure returns (uint32) {
        if (value > type(uint32).max) {
            revert SafeCastOverflowedUintDowncast(32, value);
        }
        return uint32(value);
    }

    /**
     * @dev Returns the downcasted uint24 from uint256, reverting on
     * overflow (when the input is greater than largest uint24).
     *
     * Counterpart to Solidity's `uint24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     */
    function toUint24(uint256 value) internal pure returns (uint24) {
        if (value > type(uint24).max) {
            revert SafeCastOverflowedUintDowncast(24, value);
        }
        return uint24(value);
    }

    /**
     * @dev Returns the downcasted uint16 from uint256, reverting on
     * overflow (when the input is greater than largest uint16).
     *
     * Counterpart to Solidity's `uint16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     */
    function toUint16(uint256 value) internal pure returns (uint16) {
        if (value > type(uint16).max) {
            revert SafeCastOverflowedUintDowncast(16, value);
        }
        return uint16(value);
    }

    /**
     * @dev Returns the downcasted uint8 from uint256, reverting on
     * overflow (when the input is greater than largest uint8).
     *
     * Counterpart to Solidity's `uint8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     */
    function toUint8(uint256 value) internal pure returns (uint8) {
        if (value > type(uint8).max) {
            revert SafeCastOverflowedUintDowncast(8, value);
        }
        return uint8(value);
    }

    /**
     * @dev Converts a signed int256 into an unsigned uint256.
     *
     * Requirements:
     *
     * - input must be greater than or equal to 0.
     */
    function toUint256(int256 value) internal pure returns (uint256) {
        if (value < 0) {
            revert SafeCastOverflowedIntToUint(value);
        }
        return uint256(value);
    }

    /**
     * @dev Returns the downcasted int248 from int256, reverting on
     * overflow (when the input is less than smallest int248 or
     * greater than largest int248).
     *
     * Counterpart to Solidity's `int248` operator.
     *
     * Requirements:
     *
     * - input must fit into 248 bits
     */
    function toInt248(int256 value) internal pure returns (int248 downcasted) {
        downcasted = int248(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(248, value);
        }
    }

    /**
     * @dev Returns the downcasted int240 from int256, reverting on
     * overflow (when the input is less than smallest int240 or
     * greater than largest int240).
     *
     * Counterpart to Solidity's `int240` operator.
     *
     * Requirements:
     *
     * - input must fit into 240 bits
     */
    function toInt240(int256 value) internal pure returns (int240 downcasted) {
        downcasted = int240(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(240, value);
        }
    }

    /**
     * @dev Returns the downcasted int232 from int256, reverting on
     * overflow (when the input is less than smallest int232 or
     * greater than largest int232).
     *
     * Counterpart to Solidity's `int232` operator.
     *
     * Requirements:
     *
     * - input must fit into 232 bits
     */
    function toInt232(int256 value) internal pure returns (int232 downcasted) {
        downcasted = int232(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(232, value);
        }
    }

    /**
     * @dev Returns the downcasted int224 from int256, reverting on
     * overflow (when the input is less than smallest int224 or
     * greater than largest int224).
     *
     * Counterpart to Solidity's `int224` operator.
     *
     * Requirements:
     *
     * - input must fit into 224 bits
     */
    function toInt224(int256 value) internal pure returns (int224 downcasted) {
        downcasted = int224(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(224, value);
        }
    }

    /**
     * @dev Returns the downcasted int216 from int256, reverting on
     * overflow (when the input is less than smallest int216 or
     * greater than largest int216).
     *
     * Counterpart to Solidity's `int216` operator.
     *
     * Requirements:
     *
     * - input must fit into 216 bits
     */
    function toInt216(int256 value) internal pure returns (int216 downcasted) {
        downcasted = int216(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(216, value);
        }
    }

    /**
     * @dev Returns the downcasted int208 from int256, reverting on
     * overflow (when the input is less than smallest int208 or
     * greater than largest int208).
     *
     * Counterpart to Solidity's `int208` operator.
     *
     * Requirements:
     *
     * - input must fit into 208 bits
     */
    function toInt208(int256 value) internal pure returns (int208 downcasted) {
        downcasted = int208(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(208, value);
        }
    }

    /**
     * @dev Returns the downcasted int200 from int256, reverting on
     * overflow (when the input is less than smallest int200 or
     * greater than largest int200).
     *
     * Counterpart to Solidity's `int200` operator.
     *
     * Requirements:
     *
     * - input must fit into 200 bits
     */
    function toInt200(int256 value) internal pure returns (int200 downcasted) {
        downcasted = int200(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(200, value);
        }
    }

    /**
     * @dev Returns the downcasted int192 from int256, reverting on
     * overflow (when the input is less than smallest int192 or
     * greater than largest int192).
     *
     * Counterpart to Solidity's `int192` operator.
     *
     * Requirements:
     *
     * - input must fit into 192 bits
     */
    function toInt192(int256 value) internal pure returns (int192 downcasted) {
        downcasted = int192(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(192, value);
        }
    }

    /**
     * @dev Returns the downcasted int184 from int256, reverting on
     * overflow (when the input is less than smallest int184 or
     * greater than largest int184).
     *
     * Counterpart to Solidity's `int184` operator.
     *
     * Requirements:
     *
     * - input must fit into 184 bits
     */
    function toInt184(int256 value) internal pure returns (int184 downcasted) {
        downcasted = int184(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(184, value);
        }
    }

    /**
     * @dev Returns the downcasted int176 from int256, reverting on
     * overflow (when the input is less than smallest int176 or
     * greater than largest int176).
     *
     * Counterpart to Solidity's `int176` operator.
     *
     * Requirements:
     *
     * - input must fit into 176 bits
     */
    function toInt176(int256 value) internal pure returns (int176 downcasted) {
        downcasted = int176(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(176, value);
        }
    }

    /**
     * @dev Returns the downcasted int168 from int256, reverting on
     * overflow (when the input is less than smallest int168 or
     * greater than largest int168).
     *
     * Counterpart to Solidity's `int168` operator.
     *
     * Requirements:
     *
     * - input must fit into 168 bits
     */
    function toInt168(int256 value) internal pure returns (int168 downcasted) {
        downcasted = int168(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(168, value);
        }
    }

    /**
     * @dev Returns the downcasted int160 from int256, reverting on
     * overflow (when the input is less than smallest int160 or
     * greater than largest int160).
     *
     * Counterpart to Solidity's `int160` operator.
     *
     * Requirements:
     *
     * - input must fit into 160 bits
     */
    function toInt160(int256 value) internal pure returns (int160 downcasted) {
        downcasted = int160(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(160, value);
        }
    }

    /**
     * @dev Returns the downcasted int152 from int256, reverting on
     * overflow (when the input is less than smallest int152 or
     * greater than largest int152).
     *
     * Counterpart to Solidity's `int152` operator.
     *
     * Requirements:
     *
     * - input must fit into 152 bits
     */
    function toInt152(int256 value) internal pure returns (int152 downcasted) {
        downcasted = int152(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(152, value);
        }
    }

    /**
     * @dev Returns the downcasted int144 from int256, reverting on
     * overflow (when the input is less than smallest int144 or
     * greater than largest int144).
     *
     * Counterpart to Solidity's `int144` operator.
     *
     * Requirements:
     *
     * - input must fit into 144 bits
     */
    function toInt144(int256 value) internal pure returns (int144 downcasted) {
        downcasted = int144(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(144, value);
        }
    }

    /**
     * @dev Returns the downcasted int136 from int256, reverting on
     * overflow (when the input is less than smallest int136 or
     * greater than largest int136).
     *
     * Counterpart to Solidity's `int136` operator.
     *
     * Requirements:
     *
     * - input must fit into 136 bits
     */
    function toInt136(int256 value) internal pure returns (int136 downcasted) {
        downcasted = int136(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(136, value);
        }
    }

    /**
     * @dev Returns the downcasted int128 from int256, reverting on
     * overflow (when the input is less than smallest int128 or
     * greater than largest int128).
     *
     * Counterpart to Solidity's `int128` operator.
     *
     * Requirements:
     *
     * - input must fit into 128 bits
     */
    function toInt128(int256 value) internal pure returns (int128 downcasted) {
        downcasted = int128(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(128, value);
        }
    }

    /**
     * @dev Returns the downcasted int120 from int256, reverting on
     * overflow (when the input is less than smallest int120 or
     * greater than largest int120).
     *
     * Counterpart to Solidity's `int120` operator.
     *
     * Requirements:
     *
     * - input must fit into 120 bits
     */
    function toInt120(int256 value) internal pure returns (int120 downcasted) {
        downcasted = int120(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(120, value);
        }
    }

    /**
     * @dev Returns the downcasted int112 from int256, reverting on
     * overflow (when the input is less than smallest int112 or
     * greater than largest int112).
     *
     * Counterpart to Solidity's `int112` operator.
     *
     * Requirements:
     *
     * - input must fit into 112 bits
     */
    function toInt112(int256 value) internal pure returns (int112 downcasted) {
        downcasted = int112(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(112, value);
        }
    }

    /**
     * @dev Returns the downcasted int104 from int256, reverting on
     * overflow (when the input is less than smallest int104 or
     * greater than largest int104).
     *
     * Counterpart to Solidity's `int104` operator.
     *
     * Requirements:
     *
     * - input must fit into 104 bits
     */
    function toInt104(int256 value) internal pure returns (int104 downcasted) {
        downcasted = int104(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(104, value);
        }
    }

    /**
     * @dev Returns the downcasted int96 from int256, reverting on
     * overflow (when the input is less than smallest int96 or
     * greater than largest int96).
     *
     * Counterpart to Solidity's `int96` operator.
     *
     * Requirements:
     *
     * - input must fit into 96 bits
     */
    function toInt96(int256 value) internal pure returns (int96 downcasted) {
        downcasted = int96(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(96, value);
        }
    }

    /**
     * @dev Returns the downcasted int88 from int256, reverting on
     * overflow (when the input is less than smallest int88 or
     * greater than largest int88).
     *
     * Counterpart to Solidity's `int88` operator.
     *
     * Requirements:
     *
     * - input must fit into 88 bits
     */
    function toInt88(int256 value) internal pure returns (int88 downcasted) {
        downcasted = int88(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(88, value);
        }
    }

    /**
     * @dev Returns the downcasted int80 from int256, reverting on
     * overflow (when the input is less than smallest int80 or
     * greater than largest int80).
     *
     * Counterpart to Solidity's `int80` operator.
     *
     * Requirements:
     *
     * - input must fit into 80 bits
     */
    function toInt80(int256 value) internal pure returns (int80 downcasted) {
        downcasted = int80(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(80, value);
        }
    }

    /**
     * @dev Returns the downcasted int72 from int256, reverting on
     * overflow (when the input is less than smallest int72 or
     * greater than largest int72).
     *
     * Counterpart to Solidity's `int72` operator.
     *
     * Requirements:
     *
     * - input must fit into 72 bits
     */
    function toInt72(int256 value) internal pure returns (int72 downcasted) {
        downcasted = int72(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(72, value);
        }
    }

    /**
     * @dev Returns the downcasted int64 from int256, reverting on
     * overflow (when the input is less than smallest int64 or
     * greater than largest int64).
     *
     * Counterpart to Solidity's `int64` operator.
     *
     * Requirements:
     *
     * - input must fit into 64 bits
     */
    function toInt64(int256 value) internal pure returns (int64 downcasted) {
        downcasted = int64(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(64, value);
        }
    }

    /**
     * @dev Returns the downcasted int56 from int256, reverting on
     * overflow (when the input is less than smallest int56 or
     * greater than largest int56).
     *
     * Counterpart to Solidity's `int56` operator.
     *
     * Requirements:
     *
     * - input must fit into 56 bits
     */
    function toInt56(int256 value) internal pure returns (int56 downcasted) {
        downcasted = int56(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(56, value);
        }
    }

    /**
     * @dev Returns the downcasted int48 from int256, reverting on
     * overflow (when the input is less than smallest int48 or
     * greater than largest int48).
     *
     * Counterpart to Solidity's `int48` operator.
     *
     * Requirements:
     *
     * - input must fit into 48 bits
     */
    function toInt48(int256 value) internal pure returns (int48 downcasted) {
        downcasted = int48(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(48, value);
        }
    }

    /**
     * @dev Returns the downcasted int40 from int256, reverting on
     * overflow (when the input is less than smallest int40 or
     * greater than largest int40).
     *
     * Counterpart to Solidity's `int40` operator.
     *
     * Requirements:
     *
     * - input must fit into 40 bits
     */
    function toInt40(int256 value) internal pure returns (int40 downcasted) {
        downcasted = int40(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(40, value);
        }
    }

    /**
     * @dev Returns the downcasted int32 from int256, reverting on
     * overflow (when the input is less than smallest int32 or
     * greater than largest int32).
     *
     * Counterpart to Solidity's `int32` operator.
     *
     * Requirements:
     *
     * - input must fit into 32 bits
     */
    function toInt32(int256 value) internal pure returns (int32 downcasted) {
        downcasted = int32(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(32, value);
        }
    }

    /**
     * @dev Returns the downcasted int24 from int256, reverting on
     * overflow (when the input is less than smallest int24 or
     * greater than largest int24).
     *
     * Counterpart to Solidity's `int24` operator.
     *
     * Requirements:
     *
     * - input must fit into 24 bits
     */
    function toInt24(int256 value) internal pure returns (int24 downcasted) {
        downcasted = int24(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(24, value);
        }
    }

    /**
     * @dev Returns the downcasted int16 from int256, reverting on
     * overflow (when the input is less than smallest int16 or
     * greater than largest int16).
     *
     * Counterpart to Solidity's `int16` operator.
     *
     * Requirements:
     *
     * - input must fit into 16 bits
     */
    function toInt16(int256 value) internal pure returns (int16 downcasted) {
        downcasted = int16(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(16, value);
        }
    }

    /**
     * @dev Returns the downcasted int8 from int256, reverting on
     * overflow (when the input is less than smallest int8 or
     * greater than largest int8).
     *
     * Counterpart to Solidity's `int8` operator.
     *
     * Requirements:
     *
     * - input must fit into 8 bits
     */
    function toInt8(int256 value) internal pure returns (int8 downcasted) {
        downcasted = int8(value);
        if (downcasted != value) {
            revert SafeCastOverflowedIntDowncast(8, value);
        }
    }

    /**
     * @dev Converts an unsigned uint256 into a signed int256.
     *
     * Requirements:
     *
     * - input must be less than or equal to maxInt256.
     */
    function toInt256(uint256 value) internal pure returns (int256) {
        // Note: Unsafe cast below is okay because `type(int256).max` is guaranteed to be positive
        if (value > uint256(type(int256).max)) {
            revert SafeCastOverflowedUintToInt(value);
        }
        return int256(value);
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (utils/math/SignedMath.sol)

pragma solidity ^0.8.20;

/**
 * @dev Standard signed math utilities missing in the Solidity language.
 */
library SignedMath {
    /**
     * @dev Returns the largest of two signed numbers.
     */
    function max(int256 a, int256 b) internal pure returns (int256) {
        return a > b ? a : b;
    }

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

    /**
     * @dev Returns the average of two signed numbers without overflow.
     * The result is rounded towards zero.
     */
    function average(int256 a, int256 b) internal pure returns (int256) {
        // Formula from the book "Hacker's Delight"
        int256 x = (a & b) + ((a ^ b) >> 1);
        return x + (int256(uint256(x) >> 255) & (a ^ b));
    }

    /**
     * @dev Returns the absolute unsigned value of a signed value.
     */
    function abs(int256 n) internal pure returns (uint256) {
        unchecked {
            // must be unchecked in order to support `n = type(int256).min`
            return uint256(n >= 0 ? n : -n);
        }
    }
}

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

pragma solidity ^0.8.20;

import {Math} from "./math/Math.sol";
import {SignedMath} from "./math/SignedMath.sol";

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

    /**
     * @dev The `value` string doesn't fit in the specified `length`.
     */
    error StringsInsufficientHexLength(uint256 value, uint256 length);

    /**
     * @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), HEX_DIGITS))
                }
                value /= 10;
                if (value == 0) break;
            }
            return buffer;
        }
    }

    /**
     * @dev Converts a `int256` to its ASCII `string` decimal representation.
     */
    function toStringSigned(int256 value) internal pure returns (string memory) {
        return string.concat(value < 0 ? "-" : "", toString(SignedMath.abs(value)));
    }

    /**
     * @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) {
        uint256 localValue = value;
        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] = HEX_DIGITS[localValue & 0xf];
            localValue >>= 4;
        }
        if (localValue != 0) {
            revert StringsInsufficientHexLength(value, length);
        }
        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);
    }

    /**
     * @dev Returns true if the two strings are equal.
     */
    function equal(string memory a, string memory b) internal pure returns (bool) {
        return bytes(a).length == bytes(b).length && keccak256(bytes(a)) == keccak256(bytes(b));
    }
}