// File: BurnItDAO.sol



// SPDX-License-Identifier: UNLICENSED

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

pragma solidity ^0.8.21;

import {ERC721PsiBurnable, ERC721Psi} from "./ERC721Psi/extension/ERC721PsiBurnable.sol";

import {Ownable} from "@openzeppelin/contracts/access/Ownable.sol";
import {ReentrancyGuard} from "@openzeppelin/contracts/utils/ReentrancyGuard.sol";
import {PullPayment} from "./OpenZeppelin4/PullPayment.sol";

import {LibPRNG} from "solady/src/utils/LibPRNG.sol";
import {LibString} from "solady/src/utils/LibString.sol";

import {LibBitSet, ILibBitSet64Filter} from "./LibBitSet.sol";
import {LibShared} from "./LibShared.sol";
import {LibConfig} from "./LibConfig.sol";
import {LibGame, GameStatus} from "./LibGame.sol";
import {LibWinners} from "./LibWinners.sol";
import {LibRefundable} from "./LibRefundable.sol";
import {TimeLock} from "./TimeLock.sol";
import {LibUser} from "./LibUser.sol";
import "./Constants.sol";

contract BurnItDAO is
ERC721PsiBurnable,
PullPayment,
Ownable,
ReentrancyGuard,
TimeLock,
ILibBitSet64Filter
{
    using LibPRNG for LibPRNG.PRNG;
    using LibBitSet for LibBitSet.Set;
    using LibConfig for LibConfig.Config;
    using LibGame for LibGame.Game;
    using LibUser for LibUser.User;
    using LibWinners for LibWinners.Winners;
    using LibRefundable for LibRefundable.MintData;
    using LibShared for uint256;
    using LibConfig for uint256;
    using LibGame for uint256;
    using LibShared for uint32;
    using LibString for uint256;
    using LibString for uint8;

    uint32 private constant MINT_START_LOCK = 180 days;
    uint32 private constant MINT_LAST_LOCK = 30 days;
    uint8 private constant MINT_INDEX = 0;
    string private constant URI_SLASH = "/";

    LibConfig.Config public config;
    string public baseURI;

    LibGame.Game private _game;
    LibWinners.Winners private _winners;
    LibRefundable.MintData private _mints;
    mapping(address => LibUser.User) private _users;
    uint256 private _claimSeed;

    event Commit(address indexed from, uint32 indexed gameRound);
    event Reveal(address indexed from, uint32 indexed gameRound);
    event Claim(address indexed from, uint32 indexed gameRound, uint256 indexed tokenId);

    error ErrorDoNotSendDirectEth();
    error ErrorMintExpired();
    error ErrorMintTxAmount();
    error ErrorMintTxPrice();
    error ErrorMintResetting();
    error ErrorMintNotActive();
    error ErrorMintMaxTokens();
    error ErrorMintMaxWallet();
    error ErrorCommitInvalidUser();
    error ErrorGameNotRunning();
    error ErrorClaimInvalidOwner();
    error ErrorClaimUnavailable();
    error ErrorClaimMaxWallet();
    error ErrorClaimRoundClosed();
    error ErrorClaimInvalidUser();
    error ErrorClaimPermissionDenied();
    error ErrorClaimInvalidToken(uint256 tokenId);
    error ErrorClaimInvalidBurn(uint256 tokenId);
    error ErrorNonRefundable();
    error ErrorMintComplete();
    error ErrorInvalidToken();
    error ErrorTransferDenied();
    error ErrorTransferInvalidUser();
    error ErrorTransferInvalidBalance();
    error ErrorInvalidTokenURI();

    constructor(
        string memory _name,
        string memory _symbol,
        uint256 _tokenPrice,
        uint16 _maxTokens,
        uint16 _maxWallet,
        uint16 _maxTx,
        uint8 _teamSplit,
        address payable _teamAddress,
        address payable _drawAddress,
        string memory _tokenURI
    )
    ERC721Psi(_name, _symbol)
    Ownable(msg.sender)
    PullPayment()
    TimeLock(MINT_START_LOCK, MINT_LAST_LOCK)
    {
        config.initConfig(
            _tokenPrice,
            _maxTokens,
            _maxWallet,
            _maxTx,
            _teamSplit,
            _teamAddress,
            _drawAddress);
        _setBaseURI(_tokenURI);
        _game.initGame(_nextTokenId());
        _claimSeed = uint256(uint160(msg.sender));
    }

    function setWallets(
        address payable _teamAddress,
        address payable _drawAddress
    ) external nonReentrant onlyOwner {
        config.setAddresses(_teamAddress, _drawAddress);
    }

    function setBaseURI(
        string memory newURI
    ) external onlyOwner {
        _setBaseURI(newURI);
    }

    fallback() external {
        revert ErrorDoNotSendDirectEth();
    }

    function mint(
        uint16 quantity
    ) external payable nonReentrant {
        uint256 configData = config.data;
        uint256 gameData = _game.data;
        uint32 gameRound = gameData.getGameRound();
        GameStatus status = _game.getStatus(gameData);
        if (quantity > configData.maxTx()) revert ErrorMintTxAmount();
        if (msg.value < config.tokenPrice * quantity) revert ErrorMintTxPrice();
        if (block.timestamp <= _game.virtualResetEndTime(status)) revert ErrorMintResetting();
        if (_isGameExpired(status)) revert ErrorMintExpired();
        if (gameData.gameState() != GAME_STATE_OFFLINE && status > GameStatus.RUNNING) {
            if (gameData.resetEndTime() == 0) {
                _finalizeGame(gameRound);
            }
            gameRound = _game.resetGame(_nextTokenId());
        } else if (status != GameStatus.MINTING) revert ErrorMintNotActive();
        unchecked {
            LibUser.User storage user = _users[msg.sender];
            uint256 userData = user.initUser(msg.sender, gameRound);
            if (userData.getLiveCount() + quantity > configData.maxWallet()) revert ErrorMintMaxWallet();
            LibBitSet.Set storage gameTokens = _game.tokens[MINT_INDEX];
            uint16 total = uint16(gameTokens.length()) + quantity;
            uint16 maxTokens = configData.maxTokens();
            if (total > maxTokens) revert ErrorMintMaxTokens();
            gameTokens.addBatch(_nextTokenId(), quantity);
            user.data = userData.addLiveCount(quantity);
            _mint(msg.sender, quantity);
            uint256 teamAmount = (msg.value * configData.teamSplit()) / 100;
            uint256 userAmount = msg.value - teamAmount;
            _game.prizePool += userAmount;
            _mints.addRefundableAmount(gameRound >> OFFSET_GAME_NUMBER, msg.sender, userAmount);
            _asyncTransfer(configData.teamAddress(), teamAmount);
            if (total == maxTokens) {
                _game.startGame();
                resetTimeLock();
            }
        }
        timeLock();
    }

    function commit(
        bytes32 hash
    ) external nonReentrant {
        uint256 gameData = _game.data;
        uint32 gameRound = gameData.getGameRound();
        LibUser.User storage user = _users[msg.sender];
        if (user.isInvalid(gameRound)) {
            revert ErrorClaimInvalidUser();
        }
        GameStatus status = _game.getStatus();
        if (status != GameStatus.PENDING && status != GameStatus.RUNNING) {
            revert ErrorGameNotRunning();
        }
        if (status == GameStatus.PENDING) {
            if (gameData.pauseEndTime() != 0) {
                unchecked { gameRound++; }
            }
            _game.startRound(gameRound);
            status = GameStatus.RUNNING;
        }
        user.commit(gameRound, status, hash);
        emit Commit(msg.sender, gameRound);
    }

    function reveal(
        bytes memory secret
    ) external nonReentrant {
        uint32 gameRound = _game.data.getGameRound();
        _users[msg.sender].reveal(gameRound, _game.getStatus(), secret);
        _randomSeed(bytes32(secret));
        emit Reveal(msg.sender, gameRound);
    }

    function claim(
        uint256 tokenId
    ) external nonReentrant {
        LibUser.User storage user = _users[msg.sender];
        LibUser.User memory claimUser = user;
        uint256 claimData    = claimUser.data;
        uint256 gameData     = _game.data;
        uint32 gameRound     = gameData.getGameRound();
        uint256 roundEndTime = gameData.roundEndTime();
        LibBitSet.Set storage liveTokens = _game.tokens[gameRound.liveIndex()];
        uint256 liveCount    = liveTokens.length();
        if (ownerOf(tokenId) != msg.sender) revert ErrorClaimInvalidOwner();
        if (liveCount <= 1) revert ErrorClaimUnavailable();
        if (claimData.getSafeCount() >= config.maxWallet()) revert ErrorClaimMaxWallet();
        if (roundEndTime <= block.timestamp) revert ErrorClaimRoundClosed();
        if (claimData.getGameRound() != gameRound) revert ErrorClaimInvalidUser();
        if (claimUser.lastCommit <= REVEAL_THRESHOLD) revert ErrorClaimPermissionDenied();
        if (!liveTokens.remove(tokenId)) revert ErrorClaimInvalidToken(tokenId);
        uint256 safeCount = _game.tokens[gameRound.safeIndex()].add(tokenId);
        claimData = claimData.subLiveCount(1);
        claimData = claimData.addSafeCount(1);
        unchecked {
            liveCount -= 1;
            uint256 burnId = liveTokens.removeAt(_randomN(tokenId, liveCount));
            if (burnId == LibBitSet.NOT_FOUND) revert ErrorClaimInvalidBurn(burnId);
            address burnAddress = ownerOf(burnId);
            _burn(burnId);
            liveCount -= 1;
            gameData += 1;
            if (burnAddress != msg.sender) {
                uint256 burnData = _users[burnAddress].initUser(burnAddress, gameRound);
                _users[burnAddress].data = burnData.subLiveCount(1) + 1;
            } else {
                claimData = claimData.subLiveCount(1) + 1;
            }
            emit Claim(msg.sender, gameRound, tokenId);
            if (claimData.getSafeCount() != safeCount) {
                gameData = gameData.setMultiUser();
            }
            if (liveCount <= 1) {
                gameData = gameData.clearRoundEndTime();
            }
            if ((liveCount > 1) || (gameData.isMultiUser() && (safeCount > 1))) {
                uint256 pauseTime = LibShared.max(safeCount << TOKEN_DELAY_PAUSE, MIN_PAUSE_TIME);
                gameData = gameData.setPauseEndTime(LibShared.max(gameData.roundEndTime(), block.timestamp) + pauseTime);
            }
            else {
                gameData = gameData.clearPauseEndTime() | gameData.setResetEndTime(block.timestamp + MIN_RESET_TIME);
                uint256 prize = _game.prizePool;
                _winners.recordWinner(tokenId, prize, gameRound, msg.sender);
                _asyncTransfer(msg.sender, prize);
                emit LibGame.GameOver(gameRound, msg.sender);
            }
        }
        user.data = claimData;
        _game.data = gameData;
    }

    function finalize(
    ) external nonReentrant {
        _finalizeGame(_game.data.getGameRound());
    }

    function refund(
        uint32 gameNumber,
        address payable owner
    ) external nonReentrant {
        uint256 amount = _mints.removeRefundableAmount(gameNumber, owner);
        if (amount == 0) revert ErrorNonRefundable();
        _asyncTransfer(owner, amount);
    }

    function cancel(
    ) external nonReentrant timeLocked {
        if (_game.getStatus() != GameStatus.MINTING) revert ErrorMintNotActive();
        if ( _game.liveTokenCount() >= config.maxTokens()) revert ErrorMintComplete();
        _mints.cancelMint(_game.data.getGameNumber(), _game.prizePool);
        _game.cancelGame(_nextTokenId());
        resetTimeLock();
    }

    function getRefundAmount(
        uint256 gameNumber,
        address owner
    ) external view returns (uint256) {
        return _mints.getRefundableAmount(gameNumber, owner);
    }

    function canCancelGame(
    ) external view returns (uint256) {
        if (_game.getStatus() != GameStatus.MINTING) return TimeLock.MAX_LOCK;
        return timeLockLeft();
    }

    function cancelledGames(
    ) external view returns (uint256[] memory) {
        return _mints.cancelledMints();
    }

    function totalCancelledGames(
    ) external view returns (uint256) {
        return _mints.totalCancelledMints();
    }

    function cancelledGameAtIndex(
        uint256 index
    ) external view returns (uint256) {
        return _mints.cancelledMintAtIndex(index);
    }

    function isGameFinalized(
    ) external view returns (bool) {
        (, bool finalized) = _isGameFinalized(_game.data.getGameRound());
        return finalized;
    }

    function isGameExpired(
    ) external view returns (bool) {
        return _isGameExpired(_game.getStatus());
    }

    function getGameInfo(
    ) external view returns (uint256) {
        return _game.gameInfo();
    }

    function getUserInfo(
        address userAddress
    ) external view returns (uint256) {
        return _users[userAddress].getUserInfo(_game);
    }

    function getTokenStatus(
        uint256 tokenId
    ) external view returns (uint8) {
        uint8 status = _getVirtualTokenStatus(tokenId);
        if (status == TOKEN_STATUS_SECURE && _game.data.hasPauseExpired()) {
            status = TOKEN_STATUS_ACTIVE;
        } else if ((status & TOKEN_STATUS_BURNED) != 0) {
            status = TOKEN_STATUS_BURNED;
        } else if ((status & TOKEN_STATUS_WINNER) != 0) {
            status = TOKEN_STATUS_WINNER;
        }
        return status;
    }

    function isTokenOwner(
        address owner,
        uint256 idx
    ) external view override returns (bool) {
        return ownerOf(idx) == owner;
    }

    function liveTokenOfOwner(
        address owner
    ) external view returns (uint256) {
        uint256 data = _users[owner].data;
        uint32 gameRound = _game.data.getGameRound();
        if ((gameRound != data.getGameRound()) || (data.getLiveCount() == 0))
            return LibBitSet.NOT_FOUND;
        return _game.tokens[gameRound.liveIndex()].findFirstOfOwner(owner, this);
    }

    function totalWinners(
    ) external view returns (uint256) {
        uint256 total = _winners.totalWinners();
        (uint256 tokenId, bool finalized) = _isGameFinalized(_game.data.getGameRound());
        if (finalized || tokenId == LibBitSet.NOT_FOUND) return total;
        return total + 1;
    }

    function getWinnerAtIndex(
        uint256 index
    ) external view returns (LibWinners.Winner memory) {
        if (index == _winners.totalWinners()) {
            return _virtualWinner(_game.data.getGameRound());
        }
        return _winners.getWinnerAt(index);
    }

    function getWinner(
        uint32 gameNumber
    ) external view returns (LibWinners.Winner memory) {
        uint32 gameRound = _game.data.getGameRound();
        uint32 currentGame = gameRound >> OFFSET_GAME_NUMBER;
        if (gameNumber > currentGame) {
            gameNumber = currentGame;
        }
        LibWinners.Winner memory winner = _winners.getWinner(gameNumber);
        if (winner.data != 0 || gameNumber != currentGame) {
            return winner;
        }
        return _virtualWinner(gameRound);
    }

    function tokenURI(
        uint256 tokenId
    ) public view override returns (string memory) {
        if (!_exists(tokenId)) {
            revert ErrorInvalidToken();
        }
        uint8 slug = _getVirtualTokenStatus(tokenId);
        if (slug == TOKEN_STATUS_BANNED || ((slug & TOKEN_STATUS_BURNED) != 0)) {
            slug = TOKEN_STATUS_BURNED;
        }
        if (slug == TOKEN_STATUS_SECURE && _game.data.hasPauseExpired()) {
            slug = TOKEN_STATUS_ACTIVE;
        }
        if ((slug & TOKEN_STATUS_WINNER) != 0) {
            slug = TOKEN_STATUS_WINNER;
            tokenId = _winners.getWinnerId(tokenId);
        } else {
            tokenId %= config.maxTokens();
        }
        return string(abi.encodePacked(
            baseURI, slug.toString(), URI_SLASH, tokenId.toString()
        ));
    }

    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public payable override {
        if (!_approveTransfer(from, to, tokenId)) return;
        super._transfer(from, to, tokenId);
    }

    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes memory _data
    ) public payable override {
        if (!_approveTransfer(from, to, tokenId)) return;
        super._safeTransfer(from, to, tokenId, _data);
    }

    function _finalizeGame(
        uint32 gameRound
    ) internal returns (bool) {
        (uint256 tokenId, bool finalized) = _isGameFinalized(gameRound);
        if (finalized) return false;
        address winnerAddress = tokenId >= FORFEIT_TOKEN_ID ?
            config.drawAddress : ownerOf(tokenId);
        uint256 prize = _game.prizePool;
        _winners.recordWinner(tokenId, prize, gameRound, winnerAddress);
        _asyncTransfer(winnerAddress, prize);
        emit LibGame.GameOver(gameRound, winnerAddress);
        return true;
    }

    function _isGameFinalized(
        uint32 gameRound
    ) internal view returns (uint256, bool) {
        uint256 tokenId = _game.isGameOver(gameRound);
        return (tokenId, tokenId == LibBitSet.NOT_FOUND || _winners.hasWinner(tokenId));
    }

    function _isGameExpired(
        GameStatus status
    ) internal view returns (bool) {
        return (status == GameStatus.MINTING) && timeLockExpired();
    }

    function _getVirtualTokenStatus(
        uint256 tokenId
    ) internal view returns (uint8) {
        if (_winners.hasWinner(tokenId)) return TOKEN_STATUS_WINNER;
        uint8 status = _game.getTokenStatus(tokenId);
        if ((status & (TOKEN_STATUS_ACTIVE | TOKEN_STATUS_SECURE)) != 0) {
            uint256 winnerId = _game.isGameOver(_game.data.getGameRound());
            if (winnerId != LibBitSet.NOT_FOUND) {
                return status | (winnerId == tokenId ? TOKEN_STATUS_WINNER : TOKEN_STATUS_BURNED);
            }
        }
        return status;
    }

    function _approveTransfer(
        address from,
        address to,
        uint256 tokenId
    ) internal returns (bool) {
        if (from == to) revert ErrorTransferDenied();
        if (to == address(0)) revert TransferToZeroAddress();
        if (!_isApprovedOrOwner(msg.sender, tokenId)) revert TransferFromIncorrectOwner();
        uint8 tokenStatus = _getVirtualTokenStatus(tokenId);
        if (tokenStatus == TOKEN_STATUS_BANNED || ((tokenStatus & TOKEN_STATUS_BURNED) != 0)) {
            _burn(tokenId);
            return false;
        }
        if ((tokenStatus & TOKEN_STATUS_WINNER) != 0) return true;
        if ( _game.getStatus() == GameStatus.RUNNING) revert ErrorTransferDenied();
        uint32 gameRound = _game.data.getGameRound();
        LibUser.User storage fromUser = _users[from];
        if (fromUser.isInvalid(gameRound)) revert ErrorTransferInvalidUser();
        uint256 fromData = fromUser.initUser(from, gameRound);
        if ((tokenStatus & (TOKEN_STATUS_ACTIVE | TOKEN_STATUS_QUEUED)) != 0) {
            if (fromData.getLiveCount() == 0) revert ErrorTransferInvalidBalance();
            fromData = fromData.subLiveCount(1);
        } else if ((tokenStatus & TOKEN_STATUS_SECURE) != 0) {
            if (fromData.getSafeCount() == 0) revert ErrorTransferInvalidBalance();
            fromData = fromData.subSafeCount(1);
        }
        fromUser.data = fromData;
        LibUser.User storage toUser = _users[to];
        uint256 toData = toUser.initUser(to, gameRound);
        if ((tokenStatus & (TOKEN_STATUS_ACTIVE | TOKEN_STATUS_QUEUED)) != 0) {
            toData = toData.addLiveCount(1);
        } else if ((tokenStatus & TOKEN_STATUS_SECURE) != 0) {
            toData = toData.addSafeCount(1);
        }
        toUser.data = toData;
        return true;
    }

    function _setBaseURI(
        string memory newURI
    ) private {
        if (bytes(newURI).length < 10) revert ErrorInvalidTokenURI();
        baseURI = newURI;
    }

    function _virtualUserOf(
        address owner
    ) private view returns (LibUser.User storage, uint32) {
        LibUser.User storage user = _users[owner];
        uint32 gameRound =_game.data.getGameRound();
        return (user, user.isExpired(gameRound) ? 0 : gameRound);
    }

    function _virtualWinner(
        uint32 gameRound
    ) private view returns (LibWinners.Winner memory) {
        LibWinners.Winner memory winner;
        uint256 tokenId = _game.isGameOver(gameRound);
        if (tokenId == LibBitSet.NOT_FOUND) return winner;
        bool draw = tokenId >= FORFEIT_TOKEN_ID;
        address winAddress = draw ? config.drawAddress : ownerOf(tokenId);
        gameRound ^= (gameRound & uint32(LibShared.MASK_ROUND));
        winner.data = _winners.packWinnerData(gameRound, winAddress);
        winner.tokenId = draw ? 0 : tokenId;
        winner.prize = _game.prizePool;
        return winner;
    }

    function _randomSeed(
        bytes32 seed
    ) private {
        unchecked {
            uint256 blockIndex = uint256(seed) % (block.number < 255 ? block.number - 1 : 255) + 1;
            _claimSeed = uint256(keccak256(abi.encodePacked(
                _claimSeed, block.prevrandao, msg.sender, block.timestamp, seed,
                tx.gasprice, blockhash(block.number - blockIndex))));
        }
    }

    function _randomN(
        uint256 nonce,
        uint256 max
    ) private view returns (uint256 result) {
        return LibPRNG.PRNG({state: uint256(keccak256(
            abi.encodePacked(nonce, block.prevrandao, msg.sender, block.timestamp, _claimSeed)
        ))}).uniform(max);
    }
}

// File: Constants.sol



// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.21;

uint256 constant WEI = 100000000000000;
uint256 constant DATA_OFFSET_SAFE_COUNT = 16;
uint256 constant DATA_OFFSET_LIVE_COUNT = 32;
uint256 constant DATA_OFFSET_GAME_ROUND = 224;
uint256 constant DATA_OFFSET_ROUND_COUNT = 224;
uint256 constant DATA_OFFSET_GAME_NUMBER = 232;
uint256 constant MAX_TOKEN_ID = type(uint56).max;
uint256 constant FORFEIT_TOKEN_ID = 1e6;
uint256 constant REVEAL_THRESHOLD = 0xFFFFFFFF;
uint32 constant MIN_ROUND_TIME = 60 minutes;
uint32 constant MIN_PAUSE_TIME = 60 minutes;
uint32 constant MIN_RESET_TIME = 24 hours;
uint256 constant GAME_STATE_OFFLINE = 0x0;
uint256 constant GAME_STATE_STARTED = 0x1;
uint256 constant GAME_STATE_VIRTUAL = 0x2;
uint16 constant TOKEN_DELAY_ROUND = 4;
uint16 constant TOKEN_DELAY_PAUSE = 5;
uint16 constant MIN_TOKENS = 2;
uint16 constant MAX_TOKENS = 2**14;
uint32 constant OFFSET_GAME_NUMBER = 8;
uint8 constant MAX_TEAM_SPLIT = 50;
uint8 constant TOKEN_STATUS_BANNED = 0x00;
uint8 constant TOKEN_STATUS_BURNED = 0x02;
uint8 constant TOKEN_STATUS_QUEUED = 0x04;
uint8 constant TOKEN_STATUS_ACTIVE = 0x08;
uint8 constant TOKEN_STATUS_SECURE = 0x10;
uint8 constant TOKEN_STATUS_WINNER = 0x20;


// File: LibUser.sol



// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.21;

import {LibShared} from "./LibShared.sol";
import {LibGame, GameStatus} from "./LibGame.sol";
import "./Constants.sol";

enum UserStatus {
    EXPIRED,
    STALE,
    VALID
}

library LibUser {
    using LibGame for LibGame.Game;
    using LibShared for uint256;
    using LibGame for uint256;
    using LibShared for uint32;

    uint256 private constant INFO_OFFSET_IS_PLAYING = 0;
    uint256 private constant INFO_OFFSET_PERMISSION = 1;
    uint256 private constant INFO_OFFSET_BURN_COUNT = 8;
    uint256 private constant INFO_OFFSET_SAFE_COUNT = 24;
    uint256 private constant INFO_OFFSET_LIVE_COUNT = 40;
    uint256 private constant COMMIT_WINDOW = 120;
    uint256 private constant OFFSET_COMMIT = 32;
    uint256 private constant USER_OFFSET_OWNER_ADDR = 64;
    uint8 private constant PERM_DENIED = 0x0;
    uint8 private constant PERM_COMMIT = 0x1;
    uint8 private constant PERM_REVEAL = 0x2;
    uint8 private constant PERM_CLAIMS = 0x4;

    struct User {
        uint256 data;
        uint256 lastCommit;
    }

    error ErrorCommitPrevious();
    error ErrorCommitDenied();
    error ErrorRevealLength();
    error ErrorRevealDenied();
    error ErrorRevealMismatch();

    function isInvalid(User storage self,
        uint32 gameRound
    ) internal view returns (bool) {
        uint256 data = self.data;
        unchecked {
            return (
                (data == 0) ||
                (gameRound - data.getGameRound() >= 2) ||
                (data.getLiveCount() == 0 && data.getSafeCount() == 0)
            );
        }
    }

    function initUser(User storage self,
        address addy,
        uint32 gameRound
    ) internal returns (uint256) {
        return _initUser(self, addy, gameRound);
    }

    function isExpired(User storage self,
        uint32 gameRound
    ) internal view returns (bool) {
        return _isExpired(self, gameRound);
    }

    function commit(User storage self,
        uint32 gameRound,
        GameStatus status,
        bytes32 hash
    ) internal {
        _commit(self, gameRound, status, hash);
    }

    function reveal(User storage self,
        uint32 gameRound,
        GameStatus status,
        bytes memory secret
    ) internal {
        _reveal(self, gameRound, status, secret);
    }

    function getUserInfo(User storage self,
        LibGame.Game storage game
    ) internal view returns (uint256) {
        return _getUserInfo(self, game);
    }

    function _initUser(User storage self,
        address addr,
        uint32 gameRound
    ) private returns (uint256) {
        uint256 data = self.data;
        uint32 prevGameRound = data.getGameRound();
        unchecked {
            uint32 nextGameRound = prevGameRound + 1;
            if (data == 0 || gameRound - prevGameRound >= 2) {
                data = uint256(uint160(addr)) << USER_OFFSET_OWNER_ADDR;
                self.lastCommit = 0;
            } else if (nextGameRound == gameRound) {
                data = data.addBurnCount(data.getLiveCount());
                data = data.setLiveCount(data.getSafeCount());
                data = data.clearSafeCount();
                self.lastCommit = 0;
            }
        }
        data = data.setGameRound(gameRound);
        self.data = data;
        return data;
    }

    function _isExpired(User storage self, uint32 gameRound) private view returns (bool) {
        return gameRound - self.data.getGameRound() >= 2;
    }

    function _commit(User storage self,
        uint32 gameRound,
        GameStatus status,
        bytes32 hash
    ) private {
        _initUser(self, address(0), gameRound);
        if (self.lastCommit != 0) revert ErrorCommitPrevious();
        if ((_getPermissions(self, status, gameRound) != PERM_COMMIT)) revert ErrorCommitDenied();
        self.lastCommit = (uint256(hash) << OFFSET_COMMIT) | (block.number + COMMIT_WINDOW);
    }

    function _reveal(User storage self,
        uint32 gameRound,
        GameStatus status,
        bytes memory secret
    ) private {
        if (secret.length != 4) revert ErrorRevealLength();
        if (_getPermissions(self, status, gameRound) != PERM_REVEAL) revert ErrorRevealDenied();
        bytes32 hash = keccak256(secret);
        self.lastCommit = uint256(hash) << OFFSET_COMMIT;
        if (self.lastCommit != (self.lastCommit & ~uint256(0xFFFFFFFF))) revert ErrorRevealMismatch();
        return;
    }

    function _getStatus(User storage self,
        uint32 gameRound
    ) private view returns (UserStatus) {
        uint256 lastGameRound = self.data.getGameRound();
        if (lastGameRound == gameRound) return UserStatus.VALID;
        unchecked {
            if (lastGameRound + 1 == gameRound) return UserStatus.STALE;
        }
        return UserStatus.EXPIRED;
    }

    function _getPermissions(User storage self,
        GameStatus status,
        uint32 gameRound
    ) private view returns (uint8) {
        uint256 data = self.data;
        uint32 lastGameRound =  data.getGameRound();
        uint16 count = data.getLiveCount();
        if ((status == GameStatus.PENDING || status == GameStatus.RUNNING) && (lastGameRound + 1 == gameRound)) {
            count = data.getSafeCount();
        }
        if ((status != GameStatus.PENDING && status != GameStatus.RUNNING) ||
            (gameRound - lastGameRound >= 2) || (count == 0)) {
            return PERM_DENIED;
        }
        uint256 lastCommit = self.lastCommit;
        if (lastCommit == 0) return PERM_COMMIT;
        uint32 blockNumber = uint32(lastCommit);
        if ((blockNumber == 0) && (lastGameRound + 1 == gameRound) &&
            (lastCommit > REVEAL_THRESHOLD)) {
            return PERM_COMMIT;
        }
        if (lastCommit <= REVEAL_THRESHOLD) return PERM_DENIED;
        return (blockNumber > 1 && block.number <= blockNumber) ? PERM_REVEAL : PERM_CLAIMS;
    }

    function _getUserInfo(User storage self,
        LibGame.Game storage game
    ) private view returns (uint256) {
        uint256 userData = self.data;
        uint32 lastGameRound = userData.getGameRound();
        if (lastGameRound == 0) return 0;
        uint256 gameData = game.data;
        uint256 resetEndTime = gameData.resetEndTime();
        uint32 gameRound = gameData.getGameRound();
        uint16 liveCount = userData.getLiveCount();
        uint16 safeCount = userData.getSafeCount();
        uint16 burnCount = userData.getBurnCount();
        GameStatus status = game.getStatus();
        if (status > GameStatus.RUNNING) {
            if (resetEndTime == 0) {
                resetEndTime = game.virtualResetEndTime(status);
            }
            if (resetEndTime != 0 && block.timestamp > resetEndTime) {
                gameRound = game.nextGameRound();
            }
        }
        unchecked {
            uint256 isPlayer = (userData.getGameNumber() == gameData.getGameNumber() &&
                (liveCount | safeCount | burnCount) != 0) ? 1 : 0;
            if (((status == GameStatus.PAUSING || status == GameStatus.PENDING) && (gameData.pauseEndTime() != 0))) {
                gameRound++;
            }
            uint256 perms = _getPermissions(self, status, gameRound);
            if (gameRound - lastGameRound >= 2) {
                burnCount += (liveCount + safeCount);
                liveCount = safeCount = 0;
            }
            else if ((lastGameRound + 1 == gameRound) || (status > GameStatus.RUNNING)) {
                burnCount += liveCount;
                liveCount  = 0;
                if (status == GameStatus.PENDING || status == GameStatus.RUNNING) {
                    (liveCount, safeCount) = (safeCount, 0);
                } else if (status > GameStatus.RUNNING) {
                    burnCount += safeCount;
                    safeCount  = 0;
                }
            }
            return
                (isPlayer           << INFO_OFFSET_IS_PLAYING) |
                (perms              << INFO_OFFSET_PERMISSION) |
                (uint256(burnCount) << INFO_OFFSET_BURN_COUNT) |
                (uint256(safeCount) << INFO_OFFSET_SAFE_COUNT) |
                (uint256(liveCount) << INFO_OFFSET_LIVE_COUNT);
        }
    }
}

// File: TimeLock.sol



// SPDX-License-Identifier: MIT

pragma solidity ^0.8.21;

/**
 * @title TimeLock
 * @dev This contract provides a time lock mechanism. Functions with the `timeLocked` modifier
 * can only be called after either `startTime` or `lastTime` has expired.
 */
contract TimeLock {

    uint256 public constant MAX_LOCK = type(uint256).max;

    uint256 public startTime;
    uint256 public lastTime;
    uint256 public startLock;
    uint256 public lastLock;

    error ErrorTimeLocked(uint256 remaining);

    /**
     * @dev Initializes the contract setting the `startLock` and `lastLock` state variables.
     * @param _startLock The max time after `startTime` when function can be called.
     * @param _lastLock The max time after `lastTime` when function can be called.
     */
    constructor(uint256 _startLock, uint256 _lastLock) {
        startLock = _startLock;
        lastLock = _lastLock;
    }

    /**
     * @dev Modifier to make a function callable only after the lock has expired.
     */
    modifier timeLocked() {
        uint256 t = timeLockLeft();
        if (t > 0) revert ErrorTimeLocked(t);
        _;
    }

    /**
     * @dev Set the last time and initialize start time if not set.
     */
    function timeLock() internal {
        if (timeLockExpired()) return;
        lastTime = block.timestamp;
        if (startTime == 0) startTime = lastTime;
    }

    /**
     * @dev Reset the start and last time to zero.
     */
    function resetTimeLock() internal {
        startTime = lastTime = 0;
    }

    /**
     * @dev Check if the time lock is active (not expired).
     * @return Time remaining if lock is active, false otherwise.
     */
    function timeLockLeft() internal view returns (uint256) {
        if (startTime == 0) return MAX_LOCK;
        uint256 cancelTime = _cancelTime(startLock, lastLock);
        return (block.timestamp < cancelTime) ? cancelTime - block.timestamp : 0;
    }

    /**
     * @dev Check if the time is expired past the start time lock.
     * @return True if time is expired past start time lock, false otherwise.
     */
    function timeLockExpired() internal view returns (bool) {
        return startTime > 0 && block.timestamp > (startTime + startLock);
    }

    /**
     * @dev Calculate the time at which the lock will cancel.
     * This is an assembly-optimized version of comparing startTime + startLock with lastTime + lastLock.
     * @return The time at which the lock will cancel.
     */
    function _cancelTime(uint256 _startLock, uint256 _lastLock) private view returns (uint256) {
        uint256 result;
        assembly {
            let s := add(sload(startTime.slot), _startLock)
            let l := add(sload(lastTime.slot), _lastLock)
            result := or(mul(lt(s, l), s), mul(iszero(lt(s, l)), l))
        }
        return result;
    }
}

// File: LibRefundable.sol



// SPDX-License-Identifier: MIT

pragma solidity ^0.8.21;

/// @title LibRefundable - Library for handling cancellable mint operations.
library LibRefundable {

    /// @dev Struct to hold data for mints.
    struct MintData {
        mapping(bytes32 => uint256) _mintAmounts;
        uint256[] _cancelledMints;
    }

    /// @dev Custom error for mints that are not cancelled.
    error ErrorMintNonRefundable();

    /// @dev Cancels a mint.
    /// @param self The storage reference to a MintData.
    /// @param mintId The ID of the mint.
    function cancelMint(MintData storage self, uint256 mintId, uint256 total) internal {
        self._mintAmounts[_mintKey(mintId, address(0))] = total;
        self._cancelledMints.push(mintId);
    }

    /// @dev Returns all cancelled mints.
    /// @param self The storage reference to a MintData.
    function cancelledMints(MintData storage self) internal view returns (uint256[] memory) {
        return self._cancelledMints;
    }

    /// @dev Returns the total number of cancelled mints.
    /// @param self The storage reference to a MintData.
    function totalCancelledMints(MintData storage self) internal view returns (uint256) {
        return self._cancelledMints.length;
    }

    /// @dev Returns a cancelled mint at a specific index.
    /// @param self The storage reference to a MintData.
    /// @param index The index of the cancelled mint.
    function cancelledMintAtIndex(MintData storage self, uint256 index) internal view returns (uint256) {
        return index < self._cancelledMints.length ? self._cancelledMints[index] : 0;
    }

    /// @dev Records the amount of a mint.
    /// @param self The storage reference to a MintData.
    /// @param mintId The ID of the mint.
    /// @param owner The address of the owner.
    /// @param amount The amount to record.
    function addRefundableAmount(MintData storage self, uint256 mintId, address owner, uint256 amount) internal {
        self._mintAmounts[_mintKey(mintId, owner)] += amount;
    }

    /// @dev Retrieves the refundable amount of a mint.
    /// @param self The storage reference to a MintData.
    /// @param mintId The ID of the mint.
    /// @param owner The address of the owner.
    /// @return The refundable amount for the mint.
    function getRefundableAmount(MintData storage self, uint256 mintId, address owner) internal view returns (uint256) {
        return self._mintAmounts[_mintKey(mintId, owner)];
    }

    /// @dev Refunds the amount of a mint.
    /// @param self The storage reference to a MintData.
    /// @param mintId The ID of the mint.
    /// @param owner The address of the owner.
    function removeRefundableAmount(MintData storage self, uint256 mintId, address owner) internal returns (uint256) {
        bytes32 cancelKey = _mintKey(mintId, address(0));
        bytes32 key = _mintKey(mintId, owner);
        if (self._mintAmounts[cancelKey] == 0) {
            revert ErrorMintNonRefundable();
        }
        uint256 refund = self._mintAmounts[key];
        delete self._mintAmounts[key];
        self._mintAmounts[cancelKey] -= refund;
        if (self._mintAmounts[cancelKey] == 0) {
            delete self._mintAmounts[cancelKey];
        }
        return refund;
    }

    /// @dev Generates a key for mint.
    /// @param mintId The ID of the mint.
    /// @param owner The address of the owner.
    function _mintKey(uint256 mintId, address owner) private pure returns (bytes32) {
        return keccak256(abi.encodePacked(mintId, owner));
    }
}

// File: LibWinners.sol



// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.21;

import {EnumerableMap} from "@openzeppelin/contracts/utils/structs/EnumerableMap.sol";
import {LibShared} from "./LibShared.sol";
import "./Constants.sol";

library LibWinners {
    using EnumerableMap for EnumerableMap.UintToUintMap;
    using LibShared for uint32;

    uint256 private constant WINNER_OFFSET_ADDRESS = 96;
    uint32 private constant WINNER_MASK_ID = 0xFFFFFFFF;
    uint8 private constant WINNER_OFFSET_ID = 32;

    struct Winner {
        uint256 data;
        uint256 tokenId;
        uint256 prize;
    }

    struct Winners {
        mapping(uint256 => Winner) _winningData;
        EnumerableMap.UintToUintMap _gameWinners;
    }

    function recordWinner(Winners storage self,
        uint256 tokenId,
        uint256 prize,
        uint32 gameRound,
        address winnerAddress
    ) internal {
        _recordWinner(self, tokenId, prize, gameRound, winnerAddress);
    }

    function hasWinner(Winners storage self,
        uint256 tokenId
    ) internal view returns (bool) {
        return self._winningData[tokenId].data != 0;
    }

    function totalWinners(Winners storage self
    ) internal view returns (uint256) {
        return self._gameWinners.length();
    }

    function getWinnerAt(Winners storage self,
        uint256 index
    ) internal view returns (Winner memory) {
        (, uint256 tokenId) = self._gameWinners.at(index);
        return self._winningData[tokenId];
    }

    function getWinner(Winners storage self,
        uint32 gameNumber
    ) internal view returns (Winner memory) {
        return _getWinner(self, gameNumber);
    }

    function getWinnerId(Winners storage self,
        uint256 tokenId
    ) internal view returns (uint32) {
        return uint32((self._winningData[tokenId].data >> WINNER_OFFSET_ID) & WINNER_MASK_ID);
    }

    function packWinnerData(Winners storage self,
        uint32 gameRound,
        address winnerAddress
    ) internal view returns (uint256) {
        return
            (uint256(uint160(winnerAddress)) << WINNER_OFFSET_ADDRESS) |
            (self._gameWinners.length() << WINNER_OFFSET_ID) |
            uint256(gameRound);
    }

    function _recordWinner(Winners storage self,
        uint256 tokenId,
        uint256 prize,
        uint32 gameRound,
        address winnerAddress
    ) private {
        self._gameWinners.set(gameRound >> OFFSET_GAME_NUMBER, tokenId);
        self._winningData[tokenId] = Winner({
            data: packWinnerData(self, gameRound, winnerAddress),
            tokenId: tokenId,
            prize: prize
        });
    }

    function _getWinner(Winners storage self,
        uint32 gameNumber
    ) private view returns (Winner memory) {
        Winner memory winner;
        (bool isFound, uint256 tokenId) = self._gameWinners.tryGet(gameNumber);
        if (!isFound) return winner;
        winner = self._winningData[tokenId];
        if (tokenId >= FORFEIT_TOKEN_ID) winner.tokenId = 0;
        return winner;
    }
}

// File: LibGame.sol



// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.21;

import {LibBitSet} from "./LibBitSet.sol";
import {LibShared} from "./LibShared.sol";
import "./Constants.sol";

enum GameStatus {
    MINTING,
    PAUSING,
    PENDING,
    RUNNING,
    FORFEIT,
    WINNERS
}

library LibGame {
    using LibBitSet for LibBitSet.Set;
    using LibShared for uint256;
    using LibShared for uint32;

    uint256 private constant GAME_OFFSET_RESET_TIME = 112;
    uint256 private constant GAME_OFFSET_PAUSE_TIME = 144;
    uint256 private constant GAME_OFFSET_ROUND_TIME = 176;
    uint256 private constant GAME_OFFSET_MULTI_USER = 208;
    uint256 private constant GAME_OFFSET_GAME_STATE = 216;
    uint256 private constant INFO_OFFSET_GAME_STATE = 0;
    uint256 private constant INFO_OFFSET_BLOCK_TIME = 8;
    uint256 private constant INFO_OFFSET_RESET_TIME = 40;
    uint256 private constant INFO_OFFSET_PAUSE_TIME = 72;
    uint256 private constant INFO_OFFSET_ROUND_TIME = 104;
    uint256 private constant INFO_OFFSET_PRIZE_POOL = 136;
    uint256 private constant INFO_OFFSET_GAMESTATUS = 168;
    uint256 private constant INFO_OFFSET_BURN_COUNT = 176;
    uint256 private constant INFO_OFFSET_SAFE_COUNT = 192;
    uint256 private constant INFO_OFFSET_LIVE_COUNT = 208;
    uint256 private constant INFO_OFFSET_GAME_ROUND = 224;
    uint256 private constant MASK_MULTI = 0xFF;
    uint256 private constant MASK_STATE = 0xFF;
    uint256 private constant MASK_BURNED = 0xFFFF;
    uint256 private constant MASK_TIMESTAMP = 0xFFFFFFFF;
    uint256 private constant MASK_PENDING = 0xFFFFFFFFFFFFFFFFFFFFFFFF;

    struct Game {
        uint256 data;
        uint256 prizePool;
        LibBitSet.Set[2] tokens;
    }

    event GameStart(uint32 indexed gameRound);
    event GameOver(uint32 indexed gameRound, address winner);
    event GameCancelled(uint32 indexed gameRound, uint256 mintCount);
    event RoundStart(uint32 indexed gameRound);

    function nextGameRound(Game storage self
    ) internal view returns (uint32) {
       return _nextGameRound(self.data);
    }

    function initGame(Game storage self,
        uint256 startTokenId
    ) internal returns (uint32) {
        return _initGame(self, self.data, startTokenId);
    }

    function startGame(Game storage self
    ) internal {
        _startGame(self);
    }

    function startRound(Game storage self,
        uint32 gameRound
    ) internal {
        _startRound(self, gameRound);
    }

    function resetGame(Game storage self,
        uint256 startTokenId
    ) internal returns (uint32) {
        return _resetGame(self, self.data, startTokenId);
    }

    function cancelGame(Game storage self,
        uint256 startTokenId
    ) internal {
        uint256 data = self.data;
        emit GameCancelled(data.getGameRound(), data.getLiveCount());
        _resetGame(self, data, startTokenId);
    }

    function getStatus(Game storage self
    )  internal view returns (GameStatus) {
        return _getStatus(self, self.data);
    }

    function getStatus(Game storage self,
        uint256 data
    )  internal view returns (GameStatus) {
        return _getStatus(self, data);
    }

    function isGameOver(Game storage self,
        uint32 gameRound
    ) internal view returns (uint256) {
        return _isGameOver(self, gameRound);
    }

    function liveTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _liveTokenCount(self, self.data);
    }

    function virtualLiveTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _virtualLiveTokenCount(self, self.data);
    }

    function virtualSafeTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _virtualSafeTokenCount(self, self.data);
    }

    function virtualBurnTokenCount(Game storage self
    ) internal view returns (uint16) {
        return _virtualBurnTokenCount(self, self.data);
    }

    function getTokenStatus(Game storage self,
        uint256 tokenId
    ) internal view returns (uint8) {
        return _getTokenStatus(self, tokenId);
    }

    function virtualResetEndTime(Game storage self,
        GameStatus status
    ) internal view returns (uint32) {
        return _virtualResetEndTime(self.data, status);
    }

    function gameInfo(Game storage self
    ) internal view returns (uint256) {
       return _gameInfo(self);
    }

    function _nextGameRound(
        uint256 data
    ) private pure returns (uint32) {
        unchecked {
            return (data.getGameRound() + (uint32(1) << OFFSET_GAME_NUMBER)) | 1;
        }
    }

    function _initGame(Game storage self,
        uint256 data,
        uint256 startTokenId
    ) private returns (uint32)  {
        uint256 gameRound = _nextGameRound(data);
        self.data = gameRound << DATA_OFFSET_GAME_ROUND;
        self.tokens[0].offset = self.tokens[1].offset = startTokenId;
        return uint32(gameRound);
    }

    function _startGame(Game storage self
    ) private {
        uint256 data = self.data;
        data = _clearEndTimes(data) | (GAME_STATE_STARTED << GAME_OFFSET_GAME_STATE);
        self.data = data;
        emit GameStart(data.getGameRound());
    }

    function _startRound(Game storage self,
        uint32 gameRound
    ) private {
        uint256 data = self.data;
        if (block.timestamp <= roundEndTime(data)) return;
        unchecked {
            LibBitSet.Set[2] storage tokens = self.tokens;
            if (data.getGameRound() != gameRound) {
                uint8 prevIndex = data.getLiveIndex();
                data = data.addBurnCount(uint16(tokens[prevIndex].length()));
                delete tokens[prevIndex];
                tokens[prevIndex].offset = tokens[1 - prevIndex].offset;
                data = data.setGameRound(gameRound);
            }
            data = _clearMultiUser(data);
            self.data = setRoundEndTime(data, block.timestamp +
                LibShared.max(tokens[gameRound.liveIndex()].length() << TOKEN_DELAY_ROUND, MIN_ROUND_TIME));
            emit RoundStart(gameRound);
        }
    }

    function _resetGame(Game storage self,
        uint256 data,
        uint256 startTokenId
    ) private returns (uint32) {
        self.prizePool = 0;
        delete self.tokens;
        self.tokens[0].offset = self.tokens[1].offset = startTokenId;
        return _initGame(self, data.clearRound(), startTokenId);
    }

    function _getStatus(Game storage self,
        uint256 data
    ) private view returns (GameStatus) {
        uint256 pauseTime = pauseEndTime(data);
        uint256 resetTime = resetEndTime(data);
        if (block.timestamp > pauseTime && (resetTime > 0 && block.timestamp <= resetTime)) {
            return GameStatus.WINNERS;
        }
        if (gameState(data) == GAME_STATE_OFFLINE) {
            return GameStatus.MINTING;
        }
        if (_isPending(data)) {
            return GameStatus.PENDING;
        }
        uint256 roundTime = roundEndTime(data);
        if (roundTime != 0 && block.timestamp <= roundTime && self.tokens[data.getLiveIndex()].length() > 1) {
            return GameStatus.RUNNING;
        }
        if (isMultiUser(data)) {
            if ((roundTime == 0 || block.timestamp > roundTime) && (pauseTime > 0 && block.timestamp <= pauseTime)) {
                return GameStatus.PAUSING;
            }
            return (pauseTime > 0 && block.timestamp > pauseTime && roundTime < pauseTime) ?
                GameStatus.PENDING : GameStatus.RUNNING;
        }
        return self.tokens[data.getSafeIndex()].length() == 0 ?
            GameStatus.FORFEIT : GameStatus.WINNERS;
    }

    function _liveTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        return uint16(self.tokens[data.getLiveIndex()].length());
    }

    function _safeTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        return uint16(self.tokens[data.getSafeIndex()].length());
    }

    function _virtualLiveTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        if ((gameState(data) == GAME_STATE_OFFLINE) ||
            (block.timestamp <= roundEndTime(data)) ||
            _isPending(data)) {
            return _liveTokenCount(self, data);
        }
        return 0;
    }

    function _virtualSafeTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        if (gameState(data) == GAME_STATE_OFFLINE) {
            return 0;
        }
        return _safeTokenCount(self, data);
    }

    function _virtualBurnTokenCount(Game storage self,
        uint256 data
    ) private view returns (uint16) {
        uint16 burnCount = data.getBurnCount();
        if ((gameState(data) == GAME_STATE_STARTED) &&
            (block.timestamp > roundEndTime(data)) &&
            !_isPending(data)) {
            burnCount += _liveTokenCount(self, data);
        }
        return burnCount;
    }

    function _getTokenStatus(Game storage self,
        uint256 tokenId
    ) private view returns (uint8) {
        if (tokenId < self.tokens[0].offset) return TOKEN_STATUS_BANNED;
        uint256 data = self.data;
        if (gameState(data) == GAME_STATE_OFFLINE) return TOKEN_STATUS_QUEUED;
        if (_virtualLiveTokenCount(self, data) > 1 && self.tokens[data.getLiveIndex()].contains(tokenId)) {
            return TOKEN_STATUS_ACTIVE;
        }
        return (self.tokens[data.getSafeIndex()].contains(tokenId)) ? TOKEN_STATUS_SECURE : TOKEN_STATUS_BURNED;
    }

    function _isGameOver(Game storage self,
        uint32 gameRound
    ) private view returns (uint256) {
        GameStatus status = _getStatus(self, self.data);
        if (status < GameStatus.FORFEIT) return LibBitSet.NOT_FOUND;
        if (status == GameStatus.FORFEIT) return FORFEIT_TOKEN_ID + (gameRound >> OFFSET_GAME_NUMBER);
        return self.tokens[gameRound.safeIndex()].findFirst();
    }

    function _virtualResetEndTime(
        uint256 data,
        GameStatus status
    ) private pure returns (uint32) {
        uint32 resetTime = resetEndTime(data);
        if (status > GameStatus.RUNNING && resetTime == 0) {
            return roundEndTime(data) + MIN_RESET_TIME;
        }
        return resetTime;
    }

    function _gameInfo(Game storage self
    ) private view returns (uint256) {
        uint256 data = self.data;
        GameStatus status = _getStatus(self, data);
        uint256 prizePool = self.prizePool / WEI;
        uint32 gameRound = data.getGameRound();
        uint256 state = gameState(data);
        uint32 roundTime = roundEndTime(data);
        uint32 pauseTime = pauseEndTime(data);
        uint32 resetTime = resetEndTime(data);
        uint16 liveCount = _virtualLiveTokenCount(self, data);
        uint16 safeCount = _virtualSafeTokenCount(self, data);
        uint16 burnCount = _virtualBurnTokenCount(self, data);
        if (status == GameStatus.RUNNING) {
            pauseTime = resetTime = 0;
        }
        if ((status == GameStatus.PAUSING || status == GameStatus.PENDING) && pauseTime != 0) {
            unchecked { gameRound++; }
            (liveCount, safeCount) = (safeCount, 0);
            roundTime = resetTime = 0;
            if (block.timestamp > pauseTime) {
                pauseTime = 0;
            }
        }
        if (status == GameStatus.PENDING) {
            roundTime = pauseTime = resetTime = 0;
        }
        if (status > GameStatus.RUNNING) {
            roundTime = pauseTime = 0;
            if (resetTime == 0) {
                resetTime = _virtualResetEndTime(data, status);
                state = GAME_STATE_VIRTUAL;
            }
            if (resetTime != 0 && block.timestamp > resetTime) {
                status = GameStatus.MINTING;
                gameRound = _nextGameRound(data);
                prizePool = roundTime = pauseTime = liveCount = safeCount = burnCount = 0;
            }
        }
        uint256 info = (state << INFO_OFFSET_GAME_STATE);
        info |=
            (uint256(block.timestamp) << INFO_OFFSET_BLOCK_TIME) |
            (uint256(resetTime) << INFO_OFFSET_RESET_TIME) |
            (uint256(pauseTime) << INFO_OFFSET_PAUSE_TIME) |
            (uint256(roundTime) << INFO_OFFSET_ROUND_TIME) |
            (prizePool << INFO_OFFSET_PRIZE_POOL) |
            (uint256(status) << INFO_OFFSET_GAMESTATUS);
        info |=
            (uint256(burnCount) << INFO_OFFSET_BURN_COUNT) |
            (uint256(safeCount) << INFO_OFFSET_SAFE_COUNT) |
            (uint256(liveCount) << INFO_OFFSET_LIVE_COUNT) |
            (uint256(gameRound) << INFO_OFFSET_GAME_ROUND);
        return info;
    }

    function gameState(uint256 data) internal pure returns (uint8) {
        return uint8((data >> GAME_OFFSET_GAME_STATE) & MASK_STATE);
    }

    function setMultiUser(uint256 data) internal pure returns (uint256) {
        return _clearMultiUser(data) | (1 << GAME_OFFSET_MULTI_USER);
    }

    function isMultiUser(uint256 data) internal pure returns (bool) {
        return uint8((data >> GAME_OFFSET_MULTI_USER) & MASK_MULTI) == 1;
    }

    function hasPauseExpired(uint256 data) internal view returns (bool) {
        uint32 pauseTime = pauseEndTime(data);
        return (pauseTime > 0 && block.timestamp > pauseTime && roundEndTime(data) < pauseTime);
    }

    function roundEndTime(uint256 data) internal pure returns (uint32) {
        return uint32((data >> GAME_OFFSET_ROUND_TIME) & MASK_TIMESTAMP);
    }

    function setRoundEndTime(uint256 data, uint256 time) internal pure returns (uint256) {
        return clearRoundEndTime(data) | (time << GAME_OFFSET_ROUND_TIME);
    }

    function clearRoundEndTime(uint256 data) internal pure returns (uint256) {
        return (data & ~(MASK_TIMESTAMP << GAME_OFFSET_ROUND_TIME));
    }

    function pauseEndTime(uint256 data) internal pure returns (uint32) {
        return uint32((data >> GAME_OFFSET_PAUSE_TIME) & MASK_TIMESTAMP);
    }

    function setPauseEndTime(uint256 data, uint256 time) internal pure returns (uint256) {
        return clearPauseEndTime(data) | (time << GAME_OFFSET_PAUSE_TIME);
    }

    function clearPauseEndTime(uint256 data) internal pure returns (uint256) {
        return (data & ~(MASK_TIMESTAMP << GAME_OFFSET_PAUSE_TIME));
    }

    function resetEndTime(uint256 data) internal pure returns (uint32) {
        return uint32((data >> GAME_OFFSET_RESET_TIME) & MASK_TIMESTAMP);
    }

    function setResetEndTime(uint256 data, uint256 time) internal pure returns (uint256) {
        return clearPauseEndTime(data) | (time << GAME_OFFSET_RESET_TIME);
    }

    function clearResetEndTime(uint256 data) internal pure returns (uint256) {
        return (data & ~(MASK_TIMESTAMP << GAME_OFFSET_RESET_TIME));
    }

    function _clearMultiUser(uint256 data) private pure returns (uint256) {
        return (data & ~(MASK_MULTI << GAME_OFFSET_MULTI_USER));
    }

    function _clearEndTimes(uint256 data) private pure returns (uint256) {
        return (data & ~(MASK_PENDING << GAME_OFFSET_RESET_TIME));
    }

    function _isPending(uint256 data) private pure returns (bool) {
        return ((data >> GAME_OFFSET_RESET_TIME) & MASK_PENDING) == 0;
    }
}

// File: LibConfig.sol



// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.21;

import {LibShared} from "./LibShared.sol";
import "./Constants.sol";

library LibConfig {

    uint256 private constant CONFIG_OFFSET_MAX_TOKENS = 0;
    uint256 private constant CONFIG_OFFSET_MAX_WALLET = 16;
    uint256 private constant CONFIG_OFFSET_MAX_TX = 32;
    uint256 private constant CONFIG_OFFSET_FREE = 48;
    uint256 private constant CONFIG_OFFSET_TEAM_SPLIT = 88;
    uint256 private constant CONFIG_OFFSET_TEAM_ADDRESS = 96;
    uint256 private constant MASK_MAX_TX = 0xFFFF;
    uint256 private constant MASK_MAX_WALLET = 0xFFFF;
    uint256 private constant MASK_MAX_TOKENS = 0xFFFF;
    uint256 private constant MASK_TEAM_SPLIT = 0xFF;

    struct Config {
        uint256 tokenPrice;
        uint256 data;
        address drawAddress;
    }

    error ErrorMaxTokens();
    error ErrorTokenPrice();
    error ErrorMaxWallet();
    error ErrorMaxTx();
    error ErrorTeamAddress();
    error ErrorDrawAddress();
    error ErrorTeamSplit();

    function initConfig(Config storage self,
        uint256 _tokenPrice,
        uint16 _maxTokens,
        uint16 _maxWallet,
        uint16 _maxTx,
        uint8 _teamSplit,
        address _teamAddress,
        address _drawAddress
    ) internal {
        if (_tokenPrice == 0) revert ErrorTokenPrice();
        if ((_maxTokens < MIN_TOKENS) || (_maxTokens > MAX_TOKENS)) revert ErrorMaxTokens();
        if ((_maxWallet == 0) || (_maxWallet > _maxTokens)) revert ErrorMaxWallet();
        if ((_maxTx == 0) || (_maxTx > _maxWallet)) revert ErrorMaxTx();
        if (_teamSplit > MAX_TEAM_SPLIT) revert ErrorTeamSplit();
        if (_teamAddress == address(0)) revert ErrorTeamAddress();
        if (_drawAddress == address(0)) revert ErrorDrawAddress();
        self.tokenPrice = _tokenPrice;
        self.data |=
            (uint256(_maxTokens)            << CONFIG_OFFSET_MAX_TOKENS) |
            (uint256(_maxWallet)            << CONFIG_OFFSET_MAX_WALLET) |
            (uint256(_maxTx)                << CONFIG_OFFSET_MAX_TX)     |
            (uint256(_teamSplit)            << CONFIG_OFFSET_TEAM_SPLIT) |
            (uint256(uint160(_teamAddress)) << CONFIG_OFFSET_TEAM_ADDRESS);
        self.drawAddress = _drawAddress;
    }

    function setAddresses(Config storage self,
        address _teamAddress,
        address _drawAddress
    ) internal {
        if (_teamAddress == address(0)) revert ErrorTeamAddress();
        if (_drawAddress == address(0)) revert ErrorDrawAddress();
        self.data |= uint256(uint160(_teamAddress)) << CONFIG_OFFSET_TEAM_ADDRESS;
        self.drawAddress = _drawAddress;
    }

    function teamAddress(Config storage self
    ) internal view returns (address) {
        return teamAddress(self.data);
    }

    function teamSplit(Config storage self
    ) internal view returns (uint8) {
        return teamSplit(self.data);
    }

    function maxTx(Config storage self
    ) internal view returns (uint16) {
        return maxTx(self.data);
    }

    function maxWallet(Config storage self
    ) internal view returns (uint16) {
        return maxWallet(self.data);
    }

    function maxTokens(Config storage self
    ) internal view returns (uint16) {
        return maxTokens(self.data);
    }

    function teamAddress(uint256 data) internal pure returns (address) {
        return address(uint160(data >> CONFIG_OFFSET_TEAM_ADDRESS));
    }

    function teamSplit(uint256 data) internal pure returns (uint8) {
        return uint8((data >> CONFIG_OFFSET_TEAM_SPLIT) & MASK_TEAM_SPLIT);
    }

    function maxTx(uint256 data) internal pure returns (uint16) {
        return uint16((data >> CONFIG_OFFSET_MAX_TX) & MASK_MAX_TX);
    }

    function maxWallet(uint256 data) internal pure returns (uint16) {
        return uint16((data >> CONFIG_OFFSET_MAX_WALLET) & MASK_MAX_WALLET);
    }

    function maxTokens(uint256 data) internal pure returns (uint16) {
        return uint16((data >> CONFIG_OFFSET_MAX_TOKENS) & MASK_MAX_TOKENS);
    }
}

// File: LibShared.sol



// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.21;

import "./Constants.sol";

library LibShared {

    uint256 internal constant MASK_GAME_ROUND = 0xFFFFFFFF;
    uint256 internal constant MASK_GAME_NUMBER = 0xFFFFFF;
    uint256 internal constant MASK_COUNT = 0xFFFF;
    uint256 internal constant MASK_ROUND = 0xFF;

    function liveIndex(uint32 n) internal pure returns (uint8) {
        return uint8((n + 1) & 1);
    }

    function safeIndex(uint32 n) internal pure returns (uint8) {
        return uint8(n & 1);
    }

    function getLiveIndex(uint256 data) internal pure returns (uint8) {
        return liveIndex(uint32((data >> DATA_OFFSET_ROUND_COUNT) & MASK_ROUND));
    }

    function getSafeIndex(uint256 data) internal pure returns (uint8) {
        return safeIndex(uint32((data >> DATA_OFFSET_ROUND_COUNT) & MASK_ROUND));
    }

    function getGameNumber(uint256 data) internal pure returns (uint32) {
        return uint32((data >> DATA_OFFSET_GAME_NUMBER) & MASK_GAME_NUMBER);
    }

    function getGameRound(uint256 data) internal pure returns (uint32) {
        return uint32((data >> DATA_OFFSET_GAME_ROUND) & MASK_GAME_ROUND);
    }

    function setGameRound(uint256 data, uint32 gameRound) internal pure returns (uint256) {
        return (data & ~(MASK_GAME_ROUND << DATA_OFFSET_GAME_ROUND)) |
            (uint256(gameRound) << DATA_OFFSET_GAME_ROUND);
    }

    function clearRound(uint256 data) internal pure returns (uint256) {
        return (data & ~(MASK_ROUND << DATA_OFFSET_ROUND_COUNT));
    }

    function getLiveCount(uint256 data) internal pure returns (uint16) {
        return uint16((data >> DATA_OFFSET_LIVE_COUNT) & MASK_COUNT);
    }

    function addLiveCount(uint256 data, uint16 count) internal pure returns (uint256) {
        unchecked {
            return data + (uint256(count) << DATA_OFFSET_LIVE_COUNT);
        }
    }

    function subLiveCount(uint256 data, uint16 count) internal pure returns (uint256) {
        unchecked {
            return data - (uint256(count) << DATA_OFFSET_LIVE_COUNT);
        }
    }

    function setLiveCount(uint256 data, uint16 count) internal pure returns (uint256) {
        return clearLiveCount(data) | (uint256(count) << DATA_OFFSET_LIVE_COUNT);
    }

    function clearLiveCount(uint256 data) internal pure returns (uint256) {
        return data & ~(MASK_COUNT << DATA_OFFSET_LIVE_COUNT);
    }

    function getSafeCount(uint256 data) internal pure returns (uint16) {
        return uint16((data >> DATA_OFFSET_SAFE_COUNT) & MASK_COUNT);
    }

    function addSafeCount(uint256 data, uint16 count) internal pure returns (uint256) {
        unchecked {
            return data + (uint256(count) << DATA_OFFSET_SAFE_COUNT);
        }
    }

    function subSafeCount(uint256 data, uint16 count) internal pure returns (uint256) {
        unchecked {
            return data - (uint256(count) << DATA_OFFSET_SAFE_COUNT);
        }
    }

    function setSafeCount(uint256 data, uint16 count) internal pure returns (uint256) {
        return clearSafeCount(data) | (uint256(count) << DATA_OFFSET_SAFE_COUNT);
    }

    function clearSafeCount(uint256 data) internal pure returns (uint256) {
        return data & ~(MASK_COUNT << DATA_OFFSET_SAFE_COUNT);
    }

    function getBurnCount(uint256 data) internal pure returns (uint16) {
        return uint16(data);
    }

    function addBurnCount(uint256 data, uint16 count) internal pure returns (uint256) {
        unchecked {
            return data + count;
        }
    }

    function setBurnCount(uint256 data, uint16 count) internal pure returns (uint256) {
        return clearBurnCount(data) | uint256(count);
    }

    function clearBurnCount(uint256 data) internal pure returns (uint256) {
        return data & ~MASK_COUNT;
    }

    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a : b;
    }
}

// File: LibBitSet.sol



// SPDX-License-Identifier: MIT

pragma solidity ^0.8.21;

import {LibBit} from "solady/src/utils/LibBit.sol";

interface ILibBitSet64Filter {
    function isTokenOwner(address owner, uint256 idx) external view returns (bool);
}

library LibBitSet {

    uint256 public constant NOT_FOUND = type(uint256).max;
    uint256 private constant MAX_MASK = type(uint256).max;
    uint256 private constant MAX_INDEX = 16383;
    uint256 private constant MAX_LENGTH = 64;
    uint16 public constant MAX_POP_COUNT = 256;
    uint16 private constant MASK_SET_COUNT = 0xFFFF;
    uint8 private constant MAX_BIT_COUNT = 255;
    uint8 private constant MASK_BIT_COUNT = 0xFF;
    uint8 private constant INDEX_SHIFT = 8;
    uint8 private constant INDEX_MASK = 0xFF;
    uint8 private constant INDEX_NOT_FOUND = 0xFF;
    uint8 private constant OFFSET_BUCKET_FLAGS = 192;

    struct Set {
        uint256 offset;
        uint256 count;
        uint256[2] popCounts;
        uint256[64] map;
    }

    function add(Set storage self,
        uint256 tokenId
    ) internal returns (uint256) {
        uint256 count = self.count;
        unchecked {
            tokenId -= self.offset;
            if (tokenId > MAX_INDEX) return uint16(count);
            uint8 bucket = uint8(tokenId >> INDEX_SHIFT);
            uint256 bitIndex = tokenId & INDEX_MASK;
            uint256 mask = 1 << bitIndex;
            uint256 bitmap = self.map[bucket];
            if ((bitmap & mask) == 0) {
                bitmap |= mask;
                self.map[bucket] = bitmap;
                if (bitmap != MAX_MASK) {
                    _addPopCount(self, bucket, 1);
                }
                count = ((count & ~(1 << (bucket + OFFSET_BUCKET_FLAGS))) ^
                    (((~(bitmap + 1) & bitmap) >> MAX_BIT_COUNT) << (bucket + OFFSET_BUCKET_FLAGS))) + 1;
                self.count = count;
            }
        }
        return uint16(count);
    }

    function addBatch(Set storage self,
        uint256 startId,
        uint256 amount
    ) internal {
        unchecked {
            startId -= self.offset;
            if (startId > MAX_INDEX) return;
            uint256[2] memory popCounts = self.popCounts;
            uint256 mask = 0;
            uint256 delta = 0;
            uint256 count = self.count + amount;
            uint8 bits = 0;
            uint8 bucket = uint8(startId >> INDEX_SHIFT);
            uint8 shift = uint8(startId & INDEX_MASK);
            while (amount > 0) {
                delta = MAX_POP_COUNT - shift;
                if (amount >= delta) {
                    mask = MAX_MASK << shift;
                    bits = MAX_BIT_COUNT - shift;
                    count |= (1 << (bucket + OFFSET_BUCKET_FLAGS));
                    amount -= delta;
                    shift = 0;
                } else {
                    mask = ((1 << amount) - 1) << shift;
                    bits = uint8(amount);
                    count &= ~(1 << (bucket + OFFSET_BUCKET_FLAGS));
                    amount = 0;
                }
                _addPopCounts(popCounts, bucket, bits);
                self.map[bucket] |= mask;
                bucket++;
            }
            self.popCounts = popCounts;
            self.count = count;
        }
    }

    function remove(Set storage self,
        uint256 tokenId
    ) internal returns (bool) {
        unchecked {
            tokenId -= self.offset;
            uint8 bucket = uint8(tokenId >> INDEX_SHIFT);
            if (bucket >= MAX_LENGTH) return false;
            uint256 bitmap = self.map[bucket];
            uint256 mask = 1 << (tokenId & INDEX_MASK);
            if ((bitmap & mask) == 0) return false;
            uint256 count = self.count;
            uint256 offset = bucket + OFFSET_BUCKET_FLAGS;
            if (((count >> offset) & 1) == 0) {
                _subPopCount(self, bucket, 1);
            }
            self.count = (count - 1) & ~(1 << offset);
            self.map[bucket] = bitmap & ~mask;
            return true;
        }
    }

    function removeAt(Set storage self,
        uint256 index
    ) internal returns (uint256) {
        uint256 count = self.count;
        if (index >= uint16(count)) return NOT_FOUND;
        uint256[2] memory popCounts = self.popCounts;
        (uint256 bucket, uint16 remaining) = _positionOfIndex(count, popCounts, uint16(index));
        if (bucket == INDEX_NOT_FOUND) return NOT_FOUND;
        uint256 bit;
        uint256 pos;
        uint256 offset;
        uint256 bitmap = self.map[bucket];
        unchecked {
            while (bitmap != 0) {
                bit = bitmap & (~bitmap + 1);
                pos = LibBit.fls(bit);
                if (remaining == 0) {
                    offset = bucket + OFFSET_BUCKET_FLAGS;
                    if (((count >> offset) & 1) == 0) {
                        _subPopCounts(popCounts, uint8(bucket), 1);
                        self.popCounts = popCounts;
                    }
                    self.count = (count - 1) & ~(1 << offset);
                    self.map[bucket] ^= bit;
                    return ((bucket << INDEX_SHIFT) | pos) + self.offset;
                }
                remaining--;
                bitmap ^= bit;
            }
        }
        return NOT_FOUND;
    }

    function contains(Set storage self,
        uint256 tokenId
    ) internal view returns (bool isSet) {
        unchecked {
            tokenId -= self.offset;
            uint256 bucket = tokenId >> INDEX_SHIFT;
            if (bucket >= MAX_LENGTH) return false;
            uint256 bit = (self.map[bucket] >> (tokenId & INDEX_MASK)) & 1;
            /// @solidity memory-safe-assembly
            assembly {
                isSet := bit
            }
        }
    }

    function at(Set storage self,
        uint256 index
    ) internal view returns (uint256) {
        if (index >= uint16(self.count)) return NOT_FOUND;
        uint256 len = 0;
        uint256 bitmap;
        uint256 bitsCount;
        uint256 remaining;
        uint256 bucket;
        uint256 bit;
        uint256 pos;
        unchecked {
            for (bucket = 0; bucket < MAX_LENGTH; ++bucket) {
                bitmap = self.map[bucket];
                bitsCount = LibBit.popCount(bitmap);
                if (len + bitsCount > index) {
                    remaining = index - len;
                    while (bitmap != 0) {
                        bit = bitmap & (~bitmap + 1);
                        pos = LibBit.fls(bit);
                        if (remaining == 0) {
                            return ((bucket << INDEX_SHIFT) | pos) + self.offset;
                        }
                        remaining--;
                        bitmap ^= bit;
                    }
                }
                len += bitsCount;
            }
        }
        return NOT_FOUND;
    }

    function findFirst(Set storage self
    ) internal view returns (uint256) {
        if (self.count == 0) return NOT_FOUND;
        uint256 bitmap;
        uint256 lsb;
        unchecked {
            for (uint256 bucket = 0; bucket < MAX_LENGTH; bucket++) {
                bitmap = self.map[bucket];
                if (bitmap != 0) {
                    lsb = LibBit.ffs(bitmap);
                    return (bucket << INDEX_SHIFT | lsb) + self.offset;
                }
            }
        }
        return NOT_FOUND;
    }

    function findFirstOfOwner(Set storage self,
        address owner,
        ILibBitSet64Filter filter
    ) internal view returns (uint256) {
        uint256 count = self.count;
        if (count == 0) return NOT_FOUND;
        unchecked {
            uint256 offset = self.offset;
            uint256 bitmap;
            uint256 tokenId;
            uint256 pos;
            for (uint256 bucket = 0; bucket < MAX_LENGTH; bucket++) {
                bitmap = self.map[bucket];
                while (bitmap != 0) {
                    pos = LibBit.ffs(bitmap);
                    tokenId = ((bucket << INDEX_SHIFT) | pos) + offset;
                    if (filter.isTokenOwner(owner, tokenId)) return tokenId;
                    bitmap &= ~(1 << pos);
                }
            }
        }
        return NOT_FOUND;
    }

    function findNearest(Set storage self,
        uint256 index
    ) internal view returns (uint256) {
        if (self.count == 0) return NOT_FOUND;
        unchecked {
            index -= self.offset;
            uint256 bucket = index >> INDEX_SHIFT;
            uint256 bitIndex = index & INDEX_MASK;
            uint256 bitmap = bucket < MAX_LENGTH ? self.map[bucket] : 0;
            if ((bitmap >> bitIndex) & 1 == 1) {
                return index + self.offset;
            }
            for (uint256 i = bucket; i < MAX_LENGTH; i++) {
                bitmap = self.map[i];
                if (bitmap != 0) {
                    return (i << INDEX_SHIFT) | LibBit.fls(bitmap) + self.offset;
                }
            }
        }
        return NOT_FOUND;
    }

    function findLast(Set storage self) internal view returns (uint256) {
        if (self.count == 0) return NOT_FOUND;
        for (uint256 bucket = MAX_LENGTH; bucket > 0; bucket--) {
            if (self.map[bucket - 1] != 0) {
                uint256 bitIndex = LibBit.fls(self.map[bucket - 1]);
                return ((bucket - 1) << INDEX_SHIFT) + bitIndex + self.offset;
            }
        }
        return 0;
    }

    function mapRange(Set storage self
    ) internal view returns (uint256 start, uint256 len) {
        unchecked {
            for (uint256 i = 0; i < MAX_LENGTH; i++) {
                if (self.map[i] != 0) {
                    start = (i << INDEX_SHIFT) + LibBit.ffs(self.map[i]);
                    break;
                }
            }
            for (uint256 i = MAX_LENGTH; i > 0; i--) {
                if (self.map[i - 1] != 0) {
                    len = ((i - 1) << INDEX_SHIFT) + LibBit.fls(self.map[i - 1]);
                    break;
                }
            }
            len += 1;
        }
        return (start, len);
    }

    function getRange(Set storage self,
        uint256 start,
        uint256 stop
    ) internal view returns (uint256[] memory) {
        unchecked {
            uint256 count = uint16(self.count);
            stop = (stop > count) ? count : stop;
            uint256 startBucket = (start - self.offset) >> INDEX_SHIFT;
            uint256 endBucket = (stop - self.offset) >> INDEX_SHIFT;
            uint256 arraySize = stop - start + 1;
            uint256[] memory result = new uint256[](arraySize);
            uint256 resultIndex = 0;
            uint256 bucketBits;
            for (uint256 i = startBucket; i <= endBucket && i < MAX_LENGTH; ++i) {
                bucketBits = self.map[i];
                if (bucketBits == 0) continue;
                for (uint256 j = 0; j < MAX_POP_COUNT; ++j) {
                    uint256 bitIndex = (i << INDEX_SHIFT) + j + self.offset;
                    if (bitIndex < start) continue;
                    if (bitIndex > stop) break;

                    if ((bucketBits & (1 << j)) != 0) {
                        result[resultIndex++] = bitIndex;
                    }
                }
            }
            if (resultIndex < arraySize) {
                assembly {
                    mstore(result, resultIndex)
                }
            }
            return result;
        }
    }

    function rangeLength(Set storage self
    ) internal view returns (uint256) {
        unchecked {
            uint256 bitmap;
            for (uint256 bucket = (MAX_LENGTH - 1); bucket >= 0; bucket--) {
                bitmap = self.map[bucket];
                if (bitmap != 0) {
                    return (bucket << INDEX_SHIFT) + LibBit.fls(bitmap) + 1;
                }
            }
        }
        return 0;
    }

    function mapLength(Set storage /*self*/
    ) internal pure returns (uint256) {
        return MAX_LENGTH;
    }

    function length(Set storage self
    ) internal view returns (uint256) {
        return self.count & MASK_SET_COUNT;
    }

    function trim(Set storage self
    ) internal {
        uint256 len = self.map.length;
        while (len > 0 && self.map[len - 1] == 0) {
            delete self.map[--len];
        }
    }

    function values(Set storage self
    ) internal view returns (uint256[] memory result) {
        result = new uint256[](uint16(self.count));
        uint256 index = 0;
        uint256 offset = self.offset;
        for (uint256 i = 0; i < MAX_LENGTH; i++) {
            uint256 bucket = self.map[i];
            if (bucket == 0) continue;
            for (uint256 j = 0; j < MAX_POP_COUNT; j++) {
                if ((bucket & (1 << j)) == 0) continue;
                result[index] = ((i << INDEX_SHIFT) | j) + offset;
                index++;
            }
        }
    }

    function _addPopCount(Set storage self,
        uint8 slot,
        uint8 amount
    ) private {
        unchecked {
            self.popCounts[slot >> 5] += uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _addPopCounts(
        uint256[2] memory popCounts,
        uint8 slot,
        uint8 amount
    ) private pure {
        unchecked {
            popCounts[slot >> 5] += uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _subPopCount(Set storage self,
        uint8 slot,
        uint8 amount
    ) private {
        unchecked {
            self.popCounts[slot >> 5] -= uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _subPopCounts(
        uint256[2] memory popCounts,
        uint8 slot,
        uint8 amount
    ) private pure {
        unchecked {
            popCounts[slot >> 5] -= uint256(amount & INDEX_MASK) << ((slot & 31) << 3);
        }
    }

    function _getPopCount(
        uint256 count,
        uint256[2] memory popCounts,
        uint256 slot
    ) private pure returns (uint16) {
        return ((count >> (slot + OFFSET_BUCKET_FLAGS)) & 1) == 1 ?
            MAX_POP_COUNT :
            uint16((popCounts[slot >> 5] >> ((slot & 31) << 3)) & MASK_BIT_COUNT);
    }

    function _positionOfIndex(
        uint256 count,
        uint256[2] memory popCounts,
        uint16 index
    ) private pure returns (uint8 bucket, uint16 /*pos*/) {
        unchecked {
            if (index > uint16(count)) return (INDEX_NOT_FOUND, 0);
            uint16 total = 0;
            uint16 popCount = 0;
            uint16 next = 0;
            for (bucket = 0; bucket < MAX_LENGTH; ++bucket) {
                popCount = _getPopCount(count, popCounts, bucket);
                next = total + popCount;
                if (next > index) return (bucket, index - total);
                total = next;
            }
            return (INDEX_NOT_FOUND, 0);
        }
    }
}

// File: solady/src/utils/LibString.sol



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

/// @notice Library for converting numbers into strings and other string operations.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibString.sol)
/// @author Modified from Solmate (https://github.com/transmissions11/solmate/blob/main/src/utils/LibString.sol)
library LibString {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                        CUSTOM ERRORS                       */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev The `length` of the output is too small to contain all the hex digits.
    error HexLengthInsufficient();

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                         CONSTANTS                          */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev The constant returned when the `search` is not found in the string.
    uint256 internal constant NOT_FOUND = type(uint256).max;

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                     DECIMAL OPERATIONS                     */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Returns the base 10 decimal representation of `value`.
    function toString(uint256 value) internal pure returns (string memory str) {
        /// @solidity memory-safe-assembly
        assembly {
            // The maximum value of a uint256 contains 78 digits (1 byte per digit), but
            // we allocate 0xa0 bytes to keep the free memory pointer 32-byte word aligned.
            // We will need 1 word for the trailing zeros padding, 1 word for the length,
            // and 3 words for a maximum of 78 digits.
            str := add(mload(0x40), 0x80)
            // Update the free memory pointer to allocate.
            mstore(0x40, add(str, 0x20))
            // Zeroize the slot after the string.
            mstore(str, 0)

            // Cache the end of the memory to calculate the length later.
            let end := str

            let w := not(0) // Tsk.
            // We write the string from rightmost digit to leftmost digit.
            // The following is essentially a do-while loop that also handles the zero case.
            for { let temp := value } 1 {} {
                str := add(str, w) // `sub(str, 1)`.
                // Write the character to the pointer.
                // The ASCII index of the '0' character is 48.
                mstore8(str, add(48, mod(temp, 10)))
                // Keep dividing `temp` until zero.
                temp := div(temp, 10)
                if iszero(temp) { break }
            }

            let length := sub(end, str)
            // Move the pointer 32 bytes leftwards to make room for the length.
            str := sub(str, 0x20)
            // Store the length.
            mstore(str, length)
        }
    }

    /// @dev Returns the base 10 decimal representation of `value`.
    function toString(int256 value) internal pure returns (string memory str) {
        if (value >= 0) {
            return toString(uint256(value));
        }
        unchecked {
            str = toString(uint256(-value));
        }
        /// @solidity memory-safe-assembly
        assembly {
            // We still have some spare memory space on the left,
            // as we have allocated 3 words (96 bytes) for up to 78 digits.
            let length := mload(str) // Load the string length.
            mstore(str, 0x2d) // Store the '-' character.
            str := sub(str, 1) // Move back the string pointer by a byte.
            mstore(str, add(length, 1)) // Update the string length.
        }
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                   HEXADECIMAL OPERATIONS                   */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Returns the hexadecimal representation of `value`,
    /// left-padded to an input length of `length` bytes.
    /// The output is prefixed with "0x" encoded using 2 hexadecimal digits per byte,
    /// giving a total length of `length * 2 + 2` bytes.
    /// Reverts if `length` is too small for the output to contain all the digits.
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory str) {
        str = toHexStringNoPrefix(value, length);
        /// @solidity memory-safe-assembly
        assembly {
            let strLength := add(mload(str), 2) // Compute the length.
            mstore(str, 0x3078) // Write the "0x" prefix.
            str := sub(str, 2) // Move the pointer.
            mstore(str, strLength) // Write the length.
        }
    }

    /// @dev Returns the hexadecimal representation of `value`,
    /// left-padded to an input length of `length` bytes.
    /// The output is prefixed with "0x" encoded using 2 hexadecimal digits per byte,
    /// giving a total length of `length * 2` bytes.
    /// Reverts if `length` is too small for the output to contain all the digits.
    function toHexStringNoPrefix(uint256 value, uint256 length)
        internal
        pure
        returns (string memory str)
    {
        /// @solidity memory-safe-assembly
        assembly {
            // We need 0x20 bytes for the trailing zeros padding, `length * 2` bytes
            // for the digits, 0x02 bytes for the prefix, and 0x20 bytes for the length.
            // We add 0x20 to the total and round down to a multiple of 0x20.
            // (0x20 + 0x20 + 0x02 + 0x20) = 0x62.
            str := add(mload(0x40), and(add(shl(1, length), 0x42), not(0x1f)))
            // Allocate the memory.
            mstore(0x40, add(str, 0x20))
            // Zeroize the slot after the string.
            mstore(str, 0)

            // Cache the end to calculate the length later.
            let end := str
            // Store "0123456789abcdef" in scratch space.
            mstore(0x0f, 0x30313233343536373839616263646566)

            let start := sub(str, add(length, length))
            let w := not(1) // Tsk.
            let temp := value
            // We write the string from rightmost digit to leftmost digit.
            // The following is essentially a do-while loop that also handles the zero case.
            for {} 1 {} {
                str := add(str, w) // `sub(str, 2)`.
                mstore8(add(str, 1), mload(and(temp, 15)))
                mstore8(str, mload(and(shr(4, temp), 15)))
                temp := shr(8, temp)
                if iszero(xor(str, start)) { break }
            }

            if temp {
                // Store the function selector of `HexLengthInsufficient()`.
                mstore(0x00, 0x2194895a)
                // Revert with (offset, size).
                revert(0x1c, 0x04)
            }

            // Compute the string's length.
            let strLength := sub(end, str)
            // Move the pointer and write the length.
            str := sub(str, 0x20)
            mstore(str, strLength)
        }
    }

    /// @dev Returns the hexadecimal representation of `value`.
    /// The output is prefixed with "0x" and encoded using 2 hexadecimal digits per byte.
    /// As address are 20 bytes long, the output will left-padded to have
    /// a length of `20 * 2 + 2` bytes.
    function toHexString(uint256 value) internal pure returns (string memory str) {
        str = toHexStringNoPrefix(value);
        /// @solidity memory-safe-assembly
        assembly {
            let strLength := add(mload(str), 2) // Compute the length.
            mstore(str, 0x3078) // Write the "0x" prefix.
            str := sub(str, 2) // Move the pointer.
            mstore(str, strLength) // Write the length.
        }
    }

    /// @dev Returns the hexadecimal representation of `value`.
    /// The output is prefixed with "0x".
    /// The output excludes leading "0" from the `toHexString` output.
    /// `0x00: "0x0", 0x01: "0x1", 0x12: "0x12", 0x123: "0x123"`.
    function toMinimalHexString(uint256 value) internal pure returns (string memory str) {
        str = toHexStringNoPrefix(value);
        /// @solidity memory-safe-assembly
        assembly {
            let o := eq(byte(0, mload(add(str, 0x20))), 0x30) // Whether leading zero is present.
            let strLength := add(mload(str), 2) // Compute the length.
            mstore(add(str, o), 0x3078) // Write the "0x" prefix, accounting for leading zero.
            str := sub(add(str, o), 2) // Move the pointer, accounting for leading zero.
            mstore(str, sub(strLength, o)) // Write the length, accounting for leading zero.
        }
    }

    /// @dev Returns the hexadecimal representation of `value`.
    /// The output excludes leading "0" from the `toHexStringNoPrefix` output.
    /// `0x00: "0", 0x01: "1", 0x12: "12", 0x123: "123"`.
    function toMinimalHexStringNoPrefix(uint256 value) internal pure returns (string memory str) {
        str = toHexStringNoPrefix(value);
        /// @solidity memory-safe-assembly
        assembly {
            let o := eq(byte(0, mload(add(str, 0x20))), 0x30) // Whether leading zero is present.
            let strLength := mload(str) // Get the length.
            str := add(str, o) // Move the pointer, accounting for leading zero.
            mstore(str, sub(strLength, o)) // Write the length, accounting for leading zero.
        }
    }

    /// @dev Returns the hexadecimal representation of `value`.
    /// The output is encoded using 2 hexadecimal digits per byte.
    /// As address are 20 bytes long, the output will left-padded to have
    /// a length of `20 * 2` bytes.
    function toHexStringNoPrefix(uint256 value) internal pure returns (string memory str) {
        /// @solidity memory-safe-assembly
        assembly {
            // We need 0x20 bytes for the trailing zeros padding, 0x20 bytes for the length,
            // 0x02 bytes for the prefix, and 0x40 bytes for the digits.
            // The next multiple of 0x20 above (0x20 + 0x20 + 0x02 + 0x40) is 0xa0.
            str := add(mload(0x40), 0x80)
            // Allocate the memory.
            mstore(0x40, add(str, 0x20))
            // Zeroize the slot after the string.
            mstore(str, 0)

            // Cache the end to calculate the length later.
            let end := str
            // Store "0123456789abcdef" in scratch space.
            mstore(0x0f, 0x30313233343536373839616263646566)

            let w := not(1) // Tsk.
            // We write the string from rightmost digit to leftmost digit.
            // The following is essentially a do-while loop that also handles the zero case.
            for { let temp := value } 1 {} {
                str := add(str, w) // `sub(str, 2)`.
                mstore8(add(str, 1), mload(and(temp, 15)))
                mstore8(str, mload(and(shr(4, temp), 15)))
                temp := shr(8, temp)
                if iszero(temp) { break }
            }

            // Compute the string's length.
            let strLength := sub(end, str)
            // Move the pointer and write the length.
            str := sub(str, 0x20)
            mstore(str, strLength)
        }
    }

    /// @dev Returns the hexadecimal representation of `value`.
    /// The output is prefixed with "0x", encoded using 2 hexadecimal digits per byte,
    /// and the alphabets are capitalized conditionally according to
    /// https://eips.ethereum.org/EIPS/eip-55
    function toHexStringChecksummed(address value) internal pure returns (string memory str) {
        str = toHexString(value);
        /// @solidity memory-safe-assembly
        assembly {
            let mask := shl(6, div(not(0), 255)) // `0b010000000100000000 ...`
            let o := add(str, 0x22)
            let hashed := and(keccak256(o, 40), mul(34, mask)) // `0b10001000 ... `
            let t := shl(240, 136) // `0b10001000 << 240`
            for { let i := 0 } 1 {} {
                mstore(add(i, i), mul(t, byte(i, hashed)))
                i := add(i, 1)
                if eq(i, 20) { break }
            }
            mstore(o, xor(mload(o), shr(1, and(mload(0x00), and(mload(o), mask)))))
            o := add(o, 0x20)
            mstore(o, xor(mload(o), shr(1, and(mload(0x20), and(mload(o), mask)))))
        }
    }

    /// @dev Returns the hexadecimal representation of `value`.
    /// The output is prefixed with "0x" and encoded using 2 hexadecimal digits per byte.
    function toHexString(address value) internal pure returns (string memory str) {
        str = toHexStringNoPrefix(value);
        /// @solidity memory-safe-assembly
        assembly {
            let strLength := add(mload(str), 2) // Compute the length.
            mstore(str, 0x3078) // Write the "0x" prefix.
            str := sub(str, 2) // Move the pointer.
            mstore(str, strLength) // Write the length.
        }
    }

    /// @dev Returns the hexadecimal representation of `value`.
    /// The output is encoded using 2 hexadecimal digits per byte.
    function toHexStringNoPrefix(address value) internal pure returns (string memory str) {
        /// @solidity memory-safe-assembly
        assembly {
            str := mload(0x40)

            // Allocate the memory.
            // We need 0x20 bytes for the trailing zeros padding, 0x20 bytes for the length,
            // 0x02 bytes for the prefix, and 0x28 bytes for the digits.
            // The next multiple of 0x20 above (0x20 + 0x20 + 0x02 + 0x28) is 0x80.
            mstore(0x40, add(str, 0x80))

            // Store "0123456789abcdef" in scratch space.
            mstore(0x0f, 0x30313233343536373839616263646566)

            str := add(str, 2)
            mstore(str, 40)

            let o := add(str, 0x20)
            mstore(add(o, 40), 0)

            value := shl(96, value)

            // We write the string from rightmost digit to leftmost digit.
            // The following is essentially a do-while loop that also handles the zero case.
            for { let i := 0 } 1 {} {
                let p := add(o, add(i, i))
                let temp := byte(i, value)
                mstore8(add(p, 1), mload(and(temp, 15)))
                mstore8(p, mload(shr(4, temp)))
                i := add(i, 1)
                if eq(i, 20) { break }
            }
        }
    }

    /// @dev Returns the hex encoded string from the raw bytes.
    /// The output is encoded using 2 hexadecimal digits per byte.
    function toHexString(bytes memory raw) internal pure returns (string memory str) {
        str = toHexStringNoPrefix(raw);
        /// @solidity memory-safe-assembly
        assembly {
            let strLength := add(mload(str), 2) // Compute the length.
            mstore(str, 0x3078) // Write the "0x" prefix.
            str := sub(str, 2) // Move the pointer.
            mstore(str, strLength) // Write the length.
        }
    }

    /// @dev Returns the hex encoded string from the raw bytes.
    /// The output is encoded using 2 hexadecimal digits per byte.
    function toHexStringNoPrefix(bytes memory raw) internal pure returns (string memory str) {
        /// @solidity memory-safe-assembly
        assembly {
            let length := mload(raw)
            str := add(mload(0x40), 2) // Skip 2 bytes for the optional prefix.
            mstore(str, add(length, length)) // Store the length of the output.

            // Store "0123456789abcdef" in scratch space.
            mstore(0x0f, 0x30313233343536373839616263646566)

            let o := add(str, 0x20)
            let end := add(raw, length)

            for {} iszero(eq(raw, end)) {} {
                raw := add(raw, 1)
                mstore8(add(o, 1), mload(and(mload(raw), 15)))
                mstore8(o, mload(and(shr(4, mload(raw)), 15)))
                o := add(o, 2)
            }
            mstore(o, 0) // Zeroize the slot after the string.
            mstore(0x40, add(o, 0x20)) // Allocate the memory.
        }
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                   RUNE STRING OPERATIONS                   */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Returns the number of UTF characters in the string.
    function runeCount(string memory s) internal pure returns (uint256 result) {
        /// @solidity memory-safe-assembly
        assembly {
            if mload(s) {
                mstore(0x00, div(not(0), 255))
                mstore(0x20, 0x0202020202020202020202020202020202020202020202020303030304040506)
                let o := add(s, 0x20)
                let end := add(o, mload(s))
                for { result := 1 } 1 { result := add(result, 1) } {
                    o := add(o, byte(0, mload(shr(250, mload(o)))))
                    if iszero(lt(o, end)) { break }
                }
            }
        }
    }

    /// @dev Returns if this string is a 7-bit ASCII string.
    /// (i.e. all characters codes are in [0..127])
    function is7BitASCII(string memory s) internal pure returns (bool result) {
        /// @solidity memory-safe-assembly
        assembly {
            let mask := shl(7, div(not(0), 255))
            result := 1
            let n := mload(s)
            if n {
                let o := add(s, 0x20)
                let end := add(o, n)
                let last := mload(end)
                mstore(end, 0)
                for {} 1 {} {
                    if and(mask, mload(o)) {
                        result := 0
                        break
                    }
                    o := add(o, 0x20)
                    if iszero(lt(o, end)) { break }
                }
                mstore(end, last)
            }
        }
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                   BYTE STRING OPERATIONS                   */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    // For performance and bytecode compactness, all indices of the following operations
    // are byte (ASCII) offsets, not UTF character offsets.

    /// @dev Returns `subject` all occurrences of `search` replaced with `replacement`.
    function replace(string memory subject, string memory search, string memory replacement)
        internal
        pure
        returns (string memory result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let subjectLength := mload(subject)
            let searchLength := mload(search)
            let replacementLength := mload(replacement)

            subject := add(subject, 0x20)
            search := add(search, 0x20)
            replacement := add(replacement, 0x20)
            result := add(mload(0x40), 0x20)

            let subjectEnd := add(subject, subjectLength)
            if iszero(gt(searchLength, subjectLength)) {
                let subjectSearchEnd := add(sub(subjectEnd, searchLength), 1)
                let h := 0
                if iszero(lt(searchLength, 0x20)) { h := keccak256(search, searchLength) }
                let m := shl(3, sub(0x20, and(searchLength, 0x1f)))
                let s := mload(search)
                for {} 1 {} {
                    let t := mload(subject)
                    // Whether the first `searchLength % 32` bytes of
                    // `subject` and `search` matches.
                    if iszero(shr(m, xor(t, s))) {
                        if h {
                            if iszero(eq(keccak256(subject, searchLength), h)) {
                                mstore(result, t)
                                result := add(result, 1)
                                subject := add(subject, 1)
                                if iszero(lt(subject, subjectSearchEnd)) { break }
                                continue
                            }
                        }
                        // Copy the `replacement` one word at a time.
                        for { let o := 0 } 1 {} {
                            mstore(add(result, o), mload(add(replacement, o)))
                            o := add(o, 0x20)
                            if iszero(lt(o, replacementLength)) { break }
                        }
                        result := add(result, replacementLength)
                        subject := add(subject, searchLength)
                        if searchLength {
                            if iszero(lt(subject, subjectSearchEnd)) { break }
                            continue
                        }
                    }
                    mstore(result, t)
                    result := add(result, 1)
                    subject := add(subject, 1)
                    if iszero(lt(subject, subjectSearchEnd)) { break }
                }
            }

            let resultRemainder := result
            result := add(mload(0x40), 0x20)
            let k := add(sub(resultRemainder, result), sub(subjectEnd, subject))
            // Copy the rest of the string one word at a time.
            for {} lt(subject, subjectEnd) {} {
                mstore(resultRemainder, mload(subject))
                resultRemainder := add(resultRemainder, 0x20)
                subject := add(subject, 0x20)
            }
            result := sub(result, 0x20)
            let last := add(add(result, 0x20), k) // Zeroize the slot after the string.
            mstore(last, 0)
            mstore(0x40, add(last, 0x20)) // Allocate the memory.
            mstore(result, k) // Store the length.
        }
    }

    /// @dev Returns the byte index of the first location of `search` in `subject`,
    /// searching from left to right, starting from `from`.
    /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
    function indexOf(string memory subject, string memory search, uint256 from)
        internal
        pure
        returns (uint256 result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            for { let subjectLength := mload(subject) } 1 {} {
                if iszero(mload(search)) {
                    if iszero(gt(from, subjectLength)) {
                        result := from
                        break
                    }
                    result := subjectLength
                    break
                }
                let searchLength := mload(search)
                let subjectStart := add(subject, 0x20)

                result := not(0) // Initialize to `NOT_FOUND`.

                subject := add(subjectStart, from)
                let end := add(sub(add(subjectStart, subjectLength), searchLength), 1)

                let m := shl(3, sub(0x20, and(searchLength, 0x1f)))
                let s := mload(add(search, 0x20))

                if iszero(and(lt(subject, end), lt(from, subjectLength))) { break }

                if iszero(lt(searchLength, 0x20)) {
                    for { let h := keccak256(add(search, 0x20), searchLength) } 1 {} {
                        if iszero(shr(m, xor(mload(subject), s))) {
                            if eq(keccak256(subject, searchLength), h) {
                                result := sub(subject, subjectStart)
                                break
                            }
                        }
                        subject := add(subject, 1)
                        if iszero(lt(subject, end)) { break }
                    }
                    break
                }
                for {} 1 {} {
                    if iszero(shr(m, xor(mload(subject), s))) {
                        result := sub(subject, subjectStart)
                        break
                    }
                    subject := add(subject, 1)
                    if iszero(lt(subject, end)) { break }
                }
                break
            }
        }
    }

    /// @dev Returns the byte index of the first location of `search` in `subject`,
    /// searching from left to right.
    /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
    function indexOf(string memory subject, string memory search)
        internal
        pure
        returns (uint256 result)
    {
        result = indexOf(subject, search, 0);
    }

    /// @dev Returns the byte index of the first location of `search` in `subject`,
    /// searching from right to left, starting from `from`.
    /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
    function lastIndexOf(string memory subject, string memory search, uint256 from)
        internal
        pure
        returns (uint256 result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            for {} 1 {} {
                result := not(0) // Initialize to `NOT_FOUND`.
                let searchLength := mload(search)
                if gt(searchLength, mload(subject)) { break }
                let w := result

                let fromMax := sub(mload(subject), searchLength)
                if iszero(gt(fromMax, from)) { from := fromMax }

                let end := add(add(subject, 0x20), w)
                subject := add(add(subject, 0x20), from)
                if iszero(gt(subject, end)) { break }
                // As this function is not too often used,
                // we shall simply use keccak256 for smaller bytecode size.
                for { let h := keccak256(add(search, 0x20), searchLength) } 1 {} {
                    if eq(keccak256(subject, searchLength), h) {
                        result := sub(subject, add(end, 1))
                        break
                    }
                    subject := add(subject, w) // `sub(subject, 1)`.
                    if iszero(gt(subject, end)) { break }
                }
                break
            }
        }
    }

    /// @dev Returns the byte index of the first location of `search` in `subject`,
    /// searching from right to left.
    /// Returns `NOT_FOUND` (i.e. `type(uint256).max`) if the `search` is not found.
    function lastIndexOf(string memory subject, string memory search)
        internal
        pure
        returns (uint256 result)
    {
        result = lastIndexOf(subject, search, uint256(int256(-1)));
    }

    /// @dev Returns whether `subject` starts with `search`.
    function startsWith(string memory subject, string memory search)
        internal
        pure
        returns (bool result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let searchLength := mload(search)
            // Just using keccak256 directly is actually cheaper.
            // forgefmt: disable-next-item
            result := and(
                iszero(gt(searchLength, mload(subject))),
                eq(
                    keccak256(add(subject, 0x20), searchLength),
                    keccak256(add(search, 0x20), searchLength)
                )
            )
        }
    }

    /// @dev Returns whether `subject` ends with `search`.
    function endsWith(string memory subject, string memory search)
        internal
        pure
        returns (bool result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let searchLength := mload(search)
            let subjectLength := mload(subject)
            // Whether `search` is not longer than `subject`.
            let withinRange := iszero(gt(searchLength, subjectLength))
            // Just using keccak256 directly is actually cheaper.
            // forgefmt: disable-next-item
            result := and(
                withinRange,
                eq(
                    keccak256(
                        // `subject + 0x20 + max(subjectLength - searchLength, 0)`.
                        add(add(subject, 0x20), mul(withinRange, sub(subjectLength, searchLength))),
                        searchLength
                    ),
                    keccak256(add(search, 0x20), searchLength)
                )
            )
        }
    }

    /// @dev Returns `subject` repeated `times`.
    function repeat(string memory subject, uint256 times)
        internal
        pure
        returns (string memory result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let subjectLength := mload(subject)
            if iszero(or(iszero(times), iszero(subjectLength))) {
                subject := add(subject, 0x20)
                result := mload(0x40)
                let output := add(result, 0x20)
                for {} 1 {} {
                    // Copy the `subject` one word at a time.
                    for { let o := 0 } 1 {} {
                        mstore(add(output, o), mload(add(subject, o)))
                        o := add(o, 0x20)
                        if iszero(lt(o, subjectLength)) { break }
                    }
                    output := add(output, subjectLength)
                    times := sub(times, 1)
                    if iszero(times) { break }
                }
                mstore(output, 0) // Zeroize the slot after the string.
                let resultLength := sub(output, add(result, 0x20))
                mstore(result, resultLength) // Store the length.
                // Allocate the memory.
                mstore(0x40, add(result, add(resultLength, 0x20)))
            }
        }
    }

    /// @dev Returns a copy of `subject` sliced from `start` to `end` (exclusive).
    /// `start` and `end` are byte offsets.
    function slice(string memory subject, uint256 start, uint256 end)
        internal
        pure
        returns (string memory result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let subjectLength := mload(subject)
            if iszero(gt(subjectLength, end)) { end := subjectLength }
            if iszero(gt(subjectLength, start)) { start := subjectLength }
            if lt(start, end) {
                result := mload(0x40)
                let resultLength := sub(end, start)
                mstore(result, resultLength)
                subject := add(subject, start)
                let w := not(0x1f)
                // Copy the `subject` one word at a time, backwards.
                for { let o := and(add(resultLength, 0x1f), w) } 1 {} {
                    mstore(add(result, o), mload(add(subject, o)))
                    o := add(o, w) // `sub(o, 0x20)`.
                    if iszero(o) { break }
                }
                // Zeroize the slot after the string.
                mstore(add(add(result, 0x20), resultLength), 0)
                // Allocate memory for the length and the bytes,
                // rounded up to a multiple of 32.
                mstore(0x40, add(result, and(add(resultLength, 0x3f), w)))
            }
        }
    }

    /// @dev Returns a copy of `subject` sliced from `start` to the end of the string.
    /// `start` is a byte offset.
    function slice(string memory subject, uint256 start)
        internal
        pure
        returns (string memory result)
    {
        result = slice(subject, start, uint256(int256(-1)));
    }

    /// @dev Returns all the indices of `search` in `subject`.
    /// The indices are byte offsets.
    function indicesOf(string memory subject, string memory search)
        internal
        pure
        returns (uint256[] memory result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let subjectLength := mload(subject)
            let searchLength := mload(search)

            if iszero(gt(searchLength, subjectLength)) {
                subject := add(subject, 0x20)
                search := add(search, 0x20)
                result := add(mload(0x40), 0x20)

                let subjectStart := subject
                let subjectSearchEnd := add(sub(add(subject, subjectLength), searchLength), 1)
                let h := 0
                if iszero(lt(searchLength, 0x20)) { h := keccak256(search, searchLength) }
                let m := shl(3, sub(0x20, and(searchLength, 0x1f)))
                let s := mload(search)
                for {} 1 {} {
                    let t := mload(subject)
                    // Whether the first `searchLength % 32` bytes of
                    // `subject` and `search` matches.
                    if iszero(shr(m, xor(t, s))) {
                        if h {
                            if iszero(eq(keccak256(subject, searchLength), h)) {
                                subject := add(subject, 1)
                                if iszero(lt(subject, subjectSearchEnd)) { break }
                                continue
                            }
                        }
                        // Append to `result`.
                        mstore(result, sub(subject, subjectStart))
                        result := add(result, 0x20)
                        // Advance `subject` by `searchLength`.
                        subject := add(subject, searchLength)
                        if searchLength {
                            if iszero(lt(subject, subjectSearchEnd)) { break }
                            continue
                        }
                    }
                    subject := add(subject, 1)
                    if iszero(lt(subject, subjectSearchEnd)) { break }
                }
                let resultEnd := result
                // Assign `result` to the free memory pointer.
                result := mload(0x40)
                // Store the length of `result`.
                mstore(result, shr(5, sub(resultEnd, add(result, 0x20))))
                // Allocate memory for result.
                // We allocate one more word, so this array can be recycled for {split}.
                mstore(0x40, add(resultEnd, 0x20))
            }
        }
    }

    /// @dev Returns a arrays of strings based on the `delimiter` inside of the `subject` string.
    function split(string memory subject, string memory delimiter)
        internal
        pure
        returns (string[] memory result)
    {
        uint256[] memory indices = indicesOf(subject, delimiter);
        /// @solidity memory-safe-assembly
        assembly {
            let w := not(0x1f)
            let indexPtr := add(indices, 0x20)
            let indicesEnd := add(indexPtr, shl(5, add(mload(indices), 1)))
            mstore(add(indicesEnd, w), mload(subject))
            mstore(indices, add(mload(indices), 1))
            let prevIndex := 0
            for {} 1 {} {
                let index := mload(indexPtr)
                mstore(indexPtr, 0x60)
                if iszero(eq(index, prevIndex)) {
                    let element := mload(0x40)
                    let elementLength := sub(index, prevIndex)
                    mstore(element, elementLength)
                    // Copy the `subject` one word at a time, backwards.
                    for { let o := and(add(elementLength, 0x1f), w) } 1 {} {
                        mstore(add(element, o), mload(add(add(subject, prevIndex), o)))
                        o := add(o, w) // `sub(o, 0x20)`.
                        if iszero(o) { break }
                    }
                    // Zeroize the slot after the string.
                    mstore(add(add(element, 0x20), elementLength), 0)
                    // Allocate memory for the length and the bytes,
                    // rounded up to a multiple of 32.
                    mstore(0x40, add(element, and(add(elementLength, 0x3f), w)))
                    // Store the `element` into the array.
                    mstore(indexPtr, element)
                }
                prevIndex := add(index, mload(delimiter))
                indexPtr := add(indexPtr, 0x20)
                if iszero(lt(indexPtr, indicesEnd)) { break }
            }
            result := indices
            if iszero(mload(delimiter)) {
                result := add(indices, 0x20)
                mstore(result, sub(mload(indices), 2))
            }
        }
    }

    /// @dev Returns a concatenated string of `a` and `b`.
    /// Cheaper than `string.concat()` and does not de-align the free memory pointer.
    function concat(string memory a, string memory b)
        internal
        pure
        returns (string memory result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let w := not(0x1f)
            result := mload(0x40)
            let aLength := mload(a)
            // Copy `a` one word at a time, backwards.
            for { let o := and(add(aLength, 0x20), w) } 1 {} {
                mstore(add(result, o), mload(add(a, o)))
                o := add(o, w) // `sub(o, 0x20)`.
                if iszero(o) { break }
            }
            let bLength := mload(b)
            let output := add(result, aLength)
            // Copy `b` one word at a time, backwards.
            for { let o := and(add(bLength, 0x20), w) } 1 {} {
                mstore(add(output, o), mload(add(b, o)))
                o := add(o, w) // `sub(o, 0x20)`.
                if iszero(o) { break }
            }
            let totalLength := add(aLength, bLength)
            let last := add(add(result, 0x20), totalLength)
            // Zeroize the slot after the string.
            mstore(last, 0)
            // Stores the length.
            mstore(result, totalLength)
            // Allocate memory for the length and the bytes,
            // rounded up to a multiple of 32.
            mstore(0x40, and(add(last, 0x1f), w))
        }
    }

    /// @dev Returns a copy of the string in either lowercase or UPPERCASE.
    /// WARNING! This function is only compatible with 7-bit ASCII strings.
    function toCase(string memory subject, bool toUpper)
        internal
        pure
        returns (string memory result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let length := mload(subject)
            if length {
                result := add(mload(0x40), 0x20)
                subject := add(subject, 1)
                let flags := shl(add(70, shl(5, toUpper)), 0x3ffffff)
                let w := not(0)
                for { let o := length } 1 {} {
                    o := add(o, w)
                    let b := and(0xff, mload(add(subject, o)))
                    mstore8(add(result, o), xor(b, and(shr(b, flags), 0x20)))
                    if iszero(o) { break }
                }
                result := mload(0x40)
                mstore(result, length) // Store the length.
                let last := add(add(result, 0x20), length)
                mstore(last, 0) // Zeroize the slot after the string.
                mstore(0x40, add(last, 0x20)) // Allocate the memory.
            }
        }
    }

    /// @dev Returns a string from a small bytes32 string.
    function fromSmallString(bytes32 smallString) internal pure returns (string memory result) {
        if (smallString == bytes32(0)) return result;
        /// @solidity memory-safe-assembly
        assembly {
            result := mload(0x40)
            let n
            for {} 1 {} {
                n := add(n, 1)
                if iszero(byte(n, smallString)) { break } // Scan for '\0'.
            }
            mstore(result, n)
            let o := add(result, 0x20)
            mstore(o, smallString)
            mstore(add(o, n), 0)
            mstore(0x40, add(result, 0x40))
        }
    }

    /// @dev Returns a lowercased copy of the string.
    /// WARNING! This function is only compatible with 7-bit ASCII strings.
    function lower(string memory subject) internal pure returns (string memory result) {
        result = toCase(subject, false);
    }

    /// @dev Returns an UPPERCASED copy of the string.
    /// WARNING! This function is only compatible with 7-bit ASCII strings.
    function upper(string memory subject) internal pure returns (string memory result) {
        result = toCase(subject, true);
    }

    /// @dev Escapes the string to be used within HTML tags.
    function escapeHTML(string memory s) internal pure returns (string memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            let end := add(s, mload(s))
            result := add(mload(0x40), 0x20)
            // Store the bytes of the packed offsets and strides into the scratch space.
            // `packed = (stride << 5) | offset`. Max offset is 20. Max stride is 6.
            mstore(0x1f, 0x900094)
            mstore(0x08, 0xc0000000a6ab)
            // Store "&quot;&amp;&#39;&lt;&gt;" into the scratch space.
            mstore(0x00, shl(64, 0x2671756f743b26616d703b262333393b266c743b2667743b))
            for {} iszero(eq(s, end)) {} {
                s := add(s, 1)
                let c := and(mload(s), 0xff)
                // Not in `["\"","'","&","<",">"]`.
                if iszero(and(shl(c, 1), 0x500000c400000000)) {
                    mstore8(result, c)
                    result := add(result, 1)
                    continue
                }
                let t := shr(248, mload(c))
                mstore(result, mload(and(t, 0x1f)))
                result := add(result, shr(5, t))
            }
            let last := result
            mstore(last, 0) // Zeroize the slot after the string.
            result := mload(0x40)
            mstore(result, sub(last, add(result, 0x20))) // Store the length.
            mstore(0x40, add(last, 0x20)) // Allocate the memory.
        }
    }

    /// @dev Escapes the string to be used within double-quotes in a JSON.
    /// If `addDoubleQuotes` is true, the result will be enclosed in double-quotes.
    function escapeJSON(string memory s, bool addDoubleQuotes)
        internal
        pure
        returns (string memory result)
    {
        /// @solidity memory-safe-assembly
        assembly {
            let end := add(s, mload(s))
            result := add(mload(0x40), 0x20)
            if addDoubleQuotes {
                mstore8(result, 34)
                result := add(1, result)
            }
            // Store "\\u0000" in scratch space.
            // Store "0123456789abcdef" in scratch space.
            // Also, store `{0x08:"b", 0x09:"t", 0x0a:"n", 0x0c:"f", 0x0d:"r"}`.
            // into the scratch space.
            mstore(0x15, 0x5c75303030303031323334353637383961626364656662746e006672)
            // Bitmask for detecting `["\"","\\"]`.
            let e := or(shl(0x22, 1), shl(0x5c, 1))
            for {} iszero(eq(s, end)) {} {
                s := add(s, 1)
                let c := and(mload(s), 0xff)
                if iszero(lt(c, 0x20)) {
                    if iszero(and(shl(c, 1), e)) {
                        // Not in `["\"","\\"]`.
                        mstore8(result, c)
                        result := add(result, 1)
                        continue
                    }
                    mstore8(result, 0x5c) // "\\".
                    mstore8(add(result, 1), c)
                    result := add(result, 2)
                    continue
                }
                if iszero(and(shl(c, 1), 0x3700)) {
                    // Not in `["\b","\t","\n","\f","\d"]`.
                    mstore8(0x1d, mload(shr(4, c))) // Hex value.
                    mstore8(0x1e, mload(and(c, 15))) // Hex value.
                    mstore(result, mload(0x19)) // "\\u00XX".
                    result := add(result, 6)
                    continue
                }
                mstore8(result, 0x5c) // "\\".
                mstore8(add(result, 1), mload(add(c, 8)))
                result := add(result, 2)
            }
            if addDoubleQuotes {
                mstore8(result, 34)
                result := add(1, result)
            }
            let last := result
            mstore(last, 0) // Zeroize the slot after the string.
            result := mload(0x40)
            mstore(result, sub(last, add(result, 0x20))) // Store the length.
            mstore(0x40, add(last, 0x20)) // Allocate the memory.
        }
    }

    /// @dev Escapes the string to be used within double-quotes in a JSON.
    function escapeJSON(string memory s) internal pure returns (string memory result) {
        result = escapeJSON(s, false);
    }

    /// @dev Returns whether `a` equals `b`.
    function eq(string memory a, string memory b) internal pure returns (bool result) {
        /// @solidity memory-safe-assembly
        assembly {
            result := eq(keccak256(add(a, 0x20), mload(a)), keccak256(add(b, 0x20), mload(b)))
        }
    }

    /// @dev Returns whether `a` equals `b`. For short strings up to 32 bytes.
    function eqs(string memory a, bytes32 b) internal pure returns (bool result) {
        /// @solidity memory-safe-assembly
        assembly {
            // These should be evaluated on compile time, as far as possible.
            let x := and(b, add(not(b), 1))
            let r := or(shl(8, iszero(b)), shl(7, iszero(iszero(shr(128, x)))))
            r := or(r, shl(6, iszero(iszero(shr(64, shr(r, x))))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
            r := or(r, shl(4, lt(0xffff, shr(r, x))))
            r := or(r, shl(3, lt(0xff, shr(r, x))))
            result := gt(eq(mload(a), sub(32, shr(3, r))), shr(r, xor(b, mload(add(a, 0x20)))))
        }
    }

    /// @dev Packs a single string with its length into a single word.
    /// Returns `bytes32(0)` if the length is zero or greater than 31.
    function packOne(string memory a) internal pure returns (bytes32 result) {
        /// @solidity memory-safe-assembly
        assembly {
            // We don't need to zero right pad the string,
            // since this is our own custom non-standard packing scheme.
            result :=
                mul(
                    // Load the length and the bytes.
                    mload(add(a, 0x1f)),
                    // `length != 0 && length < 32`. Abuses underflow.
                    // Assumes that the length is valid and within the block gas limit.
                    lt(sub(mload(a), 1), 0x1f)
                )
        }
    }

    /// @dev Unpacks a string packed using {packOne}.
    /// Returns the empty string if `packed` is `bytes32(0)`.
    /// If `packed` is not an output of {packOne}, the output behaviour is undefined.
    function unpackOne(bytes32 packed) internal pure returns (string memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            // Grab the free memory pointer.
            result := mload(0x40)
            // Allocate 2 words (1 for the length, 1 for the bytes).
            mstore(0x40, add(result, 0x40))
            // Zeroize the length slot.
            mstore(result, 0)
            // Store the length and bytes.
            mstore(add(result, 0x1f), packed)
            // Right pad with zeroes.
            mstore(add(add(result, 0x20), mload(result)), 0)
        }
    }

    /// @dev Packs two strings with their lengths into a single word.
    /// Returns `bytes32(0)` if combined length is zero or greater than 30.
    function packTwo(string memory a, string memory b) internal pure returns (bytes32 result) {
        /// @solidity memory-safe-assembly
        assembly {
            let aLength := mload(a)
            // We don't need to zero right pad the strings,
            // since this is our own custom non-standard packing scheme.
            result :=
                mul(
                    // Load the length and the bytes of `a` and `b`.
                    or(
                        shl(shl(3, sub(0x1f, aLength)), mload(add(a, aLength))),
                        mload(sub(add(b, 0x1e), aLength))
                    ),
                    // `totalLength != 0 && totalLength < 31`. Abuses underflow.
                    // Assumes that the lengths are valid and within the block gas limit.
                    lt(sub(add(aLength, mload(b)), 1), 0x1e)
                )
        }
    }

    /// @dev Unpacks strings packed using {packTwo}.
    /// Returns the empty strings if `packed` is `bytes32(0)`.
    /// If `packed` is not an output of {packTwo}, the output behaviour is undefined.
    function unpackTwo(bytes32 packed)
        internal
        pure
        returns (string memory resultA, string memory resultB)
    {
        /// @solidity memory-safe-assembly
        assembly {
            // Grab the free memory pointer.
            resultA := mload(0x40)
            resultB := add(resultA, 0x40)
            // Allocate 2 words for each string (1 for the length, 1 for the byte). Total 4 words.
            mstore(0x40, add(resultB, 0x40))
            // Zeroize the length slots.
            mstore(resultA, 0)
            mstore(resultB, 0)
            // Store the lengths and bytes.
            mstore(add(resultA, 0x1f), packed)
            mstore(add(resultB, 0x1f), mload(add(add(resultA, 0x20), mload(resultA))))
            // Right pad with zeroes.
            mstore(add(add(resultA, 0x20), mload(resultA)), 0)
            mstore(add(add(resultB, 0x20), mload(resultB)), 0)
        }
    }

    /// @dev Directly returns `a` without copying.
    function directReturn(string memory a) internal pure {
        assembly {
            // Assumes that the string does not start from the scratch space.
            let retStart := sub(a, 0x20)
            let retSize := add(mload(a), 0x40)
            // Right pad with zeroes. Just in case the string is produced
            // by a method that doesn't zero right pad.
            mstore(add(retStart, retSize), 0)
            // Store the return offset.
            mstore(retStart, 0x20)
            // End the transaction, returning the string.
            return(retStart, retSize)
        }
    }
}

// File: solady/src/utils/LibPRNG.sol



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

/// @notice Library for generating pseudorandom numbers.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibPRNG.sol)
library LibPRNG {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                          STRUCTS                           */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev A pseudorandom number state in memory.
    struct PRNG {
        uint256 state;
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                         OPERATIONS                         */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Seeds the `prng` with `state`.
    function seed(PRNG memory prng, uint256 state) internal pure {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(prng, state)
        }
    }

    /// @dev Returns the next pseudorandom uint256.
    /// All bits of the returned uint256 pass the NIST Statistical Test Suite.
    function next(PRNG memory prng) internal pure returns (uint256 result) {
        // We simply use `keccak256` for a great balance between
        // runtime gas costs, bytecode size, and statistical properties.
        //
        // A high-quality LCG with a 32-byte state
        // is only about 30% more gas efficient during runtime,
        // but requires a 32-byte multiplier, which can cause bytecode bloat
        // when this function is inlined.
        //
        // Using this method is about 2x more efficient than
        // `nextRandomness = uint256(keccak256(abi.encode(randomness)))`.
        /// @solidity memory-safe-assembly
        assembly {
            result := keccak256(prng, 0x20)
            mstore(prng, result)
        }
    }

    /// @dev Returns a pseudorandom uint256, uniformly distributed
    /// between 0 (inclusive) and `upper` (exclusive).
    /// If your modulus is big, this method is recommended
    /// for uniform sampling to avoid modulo bias.
    /// For uniform sampling across all uint256 values,
    /// or for small enough moduli such that the bias is neligible,
    /// use {next} instead.
    function uniform(PRNG memory prng, uint256 upper) internal pure returns (uint256 result) {
        /// @solidity memory-safe-assembly
        assembly {
            for {} 1 {} {
                result := keccak256(prng, 0x20)
                mstore(prng, result)
                if iszero(lt(result, mod(sub(0, upper), upper))) { break }
            }
            result := mod(result, upper)
        }
    }

    /// @dev Shuffles the array in-place with Fisher-Yates shuffle.
    function shuffle(PRNG memory prng, uint256[] memory a) internal pure {
        /// @solidity memory-safe-assembly
        assembly {
            let n := mload(a)
            let w := not(0)
            let mask := shr(128, w)
            if n {
                for { a := add(a, 0x20) } 1 {} {
                    // We can just directly use `keccak256`, cuz
                    // the other approaches don't save much.
                    let r := keccak256(prng, 0x20)
                    mstore(prng, r)

                    // Note that there will be a very tiny modulo bias
                    // if the length of the array is not a power of 2.
                    // For all practical purposes, it is negligible
                    // and will not be a fairness or security concern.
                    {
                        let j := add(a, shl(5, mod(shr(128, r), n)))
                        n := add(n, w) // `sub(n, 1)`.
                        if iszero(n) { break }

                        let i := add(a, shl(5, n))
                        let t := mload(i)
                        mstore(i, mload(j))
                        mstore(j, t)
                    }

                    {
                        let j := add(a, shl(5, mod(and(r, mask), n)))
                        n := add(n, w) // `sub(n, 1)`.
                        if iszero(n) { break }

                        let i := add(a, shl(5, n))
                        let t := mload(i)
                        mstore(i, mload(j))
                        mstore(j, t)
                    }
                }
            }
        }
    }

    /// @dev Shuffles the bytes in-place with Fisher-Yates shuffle.
    function shuffle(PRNG memory prng, bytes memory a) internal pure {
        /// @solidity memory-safe-assembly
        assembly {
            let n := mload(a)
            let w := not(0)
            let mask := shr(128, w)
            if n {
                let b := add(a, 0x01)
                for { a := add(a, 0x20) } 1 {} {
                    // We can just directly use `keccak256`, cuz
                    // the other approaches don't save much.
                    let r := keccak256(prng, 0x20)
                    mstore(prng, r)

                    // Note that there will be a very tiny modulo bias
                    // if the length of the array is not a power of 2.
                    // For all practical purposes, it is negligible
                    // and will not be a fairness or security concern.
                    {
                        let o := mod(shr(128, r), n)
                        n := add(n, w) // `sub(n, 1)`.
                        if iszero(n) { break }

                        let t := mload(add(b, n))
                        mstore8(add(a, n), mload(add(b, o)))
                        mstore8(add(a, o), t)
                    }

                    {
                        let o := mod(and(r, mask), n)
                        n := add(n, w) // `sub(n, 1)`.
                        if iszero(n) { break }

                        let t := mload(add(b, n))
                        mstore8(add(a, n), mload(add(b, o)))
                        mstore8(add(a, o), t)
                    }
                }
            }
        }
    }
}

// File: OpenZeppelin4/PullPayment.sol



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

pragma solidity ^0.8.0;

import "./Escrow.sol";

/**
 * @dev Simple implementation of a
 * https://consensys.github.io/smart-contract-best-practices/development-recommendations/general/external-calls/#favor-pull-over-push-for-external-calls[pull-payment]
 * strategy, where the paying contract doesn't interact directly with the
 * receiver account, which must withdraw its payments itself.
 *
 * Pull-payments are often considered the best practice when it comes to sending
 * Ether, security-wise. It prevents recipients from blocking execution, and
 * eliminates reentrancy concerns.
 *
 * TIP: If you would like to learn more about reentrancy and alternative ways
 * to protect against it, check out our blog post
 * https://blog.openzeppelin.com/reentrancy-after-istanbul/[Reentrancy After Istanbul].
 *
 * To use, derive from the `PullPayment` contract, and use {_asyncTransfer}
 * instead of Solidity's `transfer` function. Payees can query their due
 * payments with {payments}, and retrieve them with {withdrawPayments}.
 */
abstract contract PullPayment {
    Escrow private immutable _escrow;

    constructor() {
        _escrow = new Escrow();
    }

    /**
     * @dev Withdraw accumulated payments, forwarding all gas to the recipient.
     *
     * Note that _any_ account can call this function, not just the `payee`.
     * This means that contracts unaware of the `PullPayment` protocol can still
     * receive funds this way, by having a separate account call
     * {withdrawPayments}.
     *
     * WARNING: Forwarding all gas opens the door to reentrancy vulnerabilities.
     * Make sure you trust the recipient, or are either following the
     * checks-effects-interactions pattern or using {ReentrancyGuard}.
     *
     * @param payee Whose payments will be withdrawn.
     *
     * Causes the `escrow` to emit a {Withdrawn} event.
     */
    function withdrawPayments(address payable payee) public virtual {
        _escrow.withdraw(payee);
    }

    /**
     * @dev Returns the payments owed to an address.
     * @param dest The creditor's address.
     */
    function payments(address dest) public view returns (uint256) {
        return _escrow.depositsOf(dest);
    }

    /**
     * @dev Called by the payer to store the sent amount as credit to be pulled.
     * Funds sent in this way are stored in an intermediate {Escrow} contract, so
     * there is no danger of them being spent before withdrawal.
     *
     * @param dest The destination address of the funds.
     * @param amount The amount to transfer.
     *
     * Causes the `escrow` to emit a {Deposited} event.
     */
    function _asyncTransfer(address dest, uint256 amount) internal virtual {
        _escrow.deposit{value: amount}(dest);
    }
}

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



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

pragma solidity ^0.8.20;

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

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

    uint256 private _status;

    /**
     * @dev Unauthorized reentrant call.
     */
    error ReentrancyGuardReentrantCall();

    constructor() {
        _status = NOT_ENTERED;
    }

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

    function _nonReentrantBefore() private {
        // On the first call to nonReentrant, _status will be NOT_ENTERED
        if (_status == ENTERED) {
            revert ReentrancyGuardReentrantCall();
        }

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

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

    /**
     * @dev Returns true if the reentrancy guard is currently set to "entered", which indicates there is a
     * `nonReentrant` function in the call stack.
     */
    function _reentrancyGuardEntered() internal view returns (bool) {
        return _status == ENTERED;
    }
}

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



// 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);
    }
}

// File: ERC721Psi/extension/ERC721PsiBurnable.sol



// SPDX-License-Identifier: MIT
/**
  ______ _____   _____ ______ ___  __ _  _  _ 
 |  ____|  __ \ / ____|____  |__ \/_ | || || |
 | |__  | |__) | |        / /   ) || | \| |/ |
 |  __| |  _  /| |       / /   / / | |\_   _/ 
 | |____| | \ \| |____  / /   / /_ | |  | |   
 |______|_|  \_\\_____|/_/   |____||_|  |_|   
                                              
                                            
 */
pragma solidity ^0.8.0;

import "solady/src/utils/LibBitmap.sol";
import "../ERC721Psi.sol";

abstract contract ERC721PsiBurnable is ERC721Psi {
    using LibBitmap for LibBitmap.Bitmap;
    LibBitmap.Bitmap private _burnedToken;

    /**
     * @dev Destroys `tokenId`.
     * The approval is cleared when the token is burned.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     *
     * Emits a {Transfer} event.
     */
    function _burn(uint256 tokenId) internal virtual {
        address from = ownerOf(tokenId);
        _beforeTokenTransfers(from, address(0), tokenId, 1);
        _burnedToken.set(tokenId);
        
        emit Transfer(from, address(0), tokenId);

        _afterTokenTransfers(from, address(0), tokenId, 1);
    }

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

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId)
        public
        view
        virtual
        override
        returns (address)
    {
        if (_burnedToken.get(tokenId)) {
            return address(0);
        }
        else {
            return super.ownerOf(tokenId);
        }
    }

    /**
     * @dev See {IERC721Enumerable-totalSupply}.
     */
    function totalSupply() public view virtual override returns (uint256) {
        return _currentIndex - _burned() - _startTokenId();
    }

    /**
     * @dev Returns number of token burned.
     */
    function _burned() internal view returns (uint256 burned){
        return _burnedToken.popCount( _startTokenId(), _totalMinted());
    }
}
// File: OpenZeppelin4/Escrow.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/escrow/Escrow.sol)

pragma solidity ^0.8.0;

import {Ownable} from "@openzeppelin/contracts/access/Ownable.sol";
import {Address} from "@openzeppelin/contracts/utils/Address.sol";

/**
 * @title Escrow
 * @dev Base escrow contract, holds funds designated for a payee until they
 * withdraw them.
 *
 * Intended usage: This contract (and derived escrow contracts) should be a
 * standalone contract, that only interacts with the contract that instantiated
 * it. That way, it is guaranteed that all Ether will be handled according to
 * the `Escrow` rules, and there is no need to check for payable functions or
 * transfers in the inheritance tree. The contract that uses the escrow as its
 * payment method should be its owner, and provide public methods redirecting
 * to the escrow's deposit and withdraw.
 */
contract Escrow is Ownable {
    using Address for address payable;

    event Deposited(address indexed payee, uint256 weiAmount);
    event Withdrawn(address indexed payee, uint256 weiAmount);

    mapping(address => uint256) private _deposits;

    /// @dev modify this to support Ownable v5.0
    constructor() Ownable(msg.sender) {}

    function depositsOf(address payee) public view returns (uint256) {
        return _deposits[payee];
    }

    /**
     * @dev Stores the sent amount as credit to be withdrawn.
     * @param payee The destination address of the funds.
     *
     * Emits a {Deposited} event.
     */
    function deposit(address payee) public payable virtual onlyOwner {
        uint256 amount = msg.value;
        _deposits[payee] += amount;
        emit Deposited(payee, amount);
    }

    /**
     * @dev Withdraw accumulated balance for a payee, forwarding all gas to the
     * recipient.
     *
     * WARNING: Forwarding all gas opens the door to reentrancy vulnerabilities.
     * Make sure you trust the recipient, or are either following the
     * checks-effects-interactions pattern or using {ReentrancyGuard}.
     *
     * @param payee The address whose funds will be withdrawn and transferred to.
     *
     * Emits a {Withdrawn} event.
     */
    function withdraw(address payable payee) public virtual onlyOwner {
        uint256 payment = _deposits[payee];

        _deposits[payee] = 0;

        payee.sendValue(payment);

        emit Withdrawn(payee, payment);
    }
}

// File: @openzeppelin/contracts/utils/structs/EnumerableMap.sol



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

pragma solidity ^0.8.20;

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

/**
 * @dev Library for managing an enumerable variant of Solidity's
 * https://solidity.readthedocs.io/en/latest/types.html#mapping-types[`mapping`]
 * type.
 *
 * Maps have the following properties:
 *
 * - Entries are added, removed, and checked for existence in constant time
 * (O(1)).
 * - Entries are enumerated in O(n). No guarantees are made on the ordering.
 *
 * ```solidity
 * contract Example {
 *     // Add the library methods
 *     using EnumerableMap for EnumerableMap.UintToAddressMap;
 *
 *     // Declare a set state variable
 *     EnumerableMap.UintToAddressMap private myMap;
 * }
 * ```
 *
 * The following map types are supported:
 *
 * - `uint256 -> address` (`UintToAddressMap`) since v3.0.0
 * - `address -> uint256` (`AddressToUintMap`) since v4.6.0
 * - `bytes32 -> bytes32` (`Bytes32ToBytes32Map`) since v4.6.0
 * - `uint256 -> uint256` (`UintToUintMap`) since v4.7.0
 * - `bytes32 -> uint256` (`Bytes32ToUintMap`) since v4.7.0
 *
 * [WARNING]
 * ====
 * Trying to delete such a structure from storage will likely result in data corruption, rendering the structure
 * unusable.
 * See https://github.com/ethereum/solidity/pull/11843[ethereum/solidity#11843] for more info.
 *
 * In order to clean an EnumerableMap, you can either remove all elements one by one or create a fresh instance using an
 * array of EnumerableMap.
 * ====
 */
library EnumerableMap {
    using EnumerableSet for EnumerableSet.Bytes32Set;

    // To implement this library for multiple types with as little code repetition as possible, we write it in
    // terms of a generic Map type with bytes32 keys and values. The Map implementation uses private functions,
    // and user-facing implementations such as `UintToAddressMap` are just wrappers around the underlying Map.
    // This means that we can only create new EnumerableMaps for types that fit in bytes32.

    /**
     * @dev Query for a nonexistent map key.
     */
    error EnumerableMapNonexistentKey(bytes32 key);

    struct Bytes32ToBytes32Map {
        // Storage of keys
        EnumerableSet.Bytes32Set _keys;
        mapping(bytes32 key => bytes32) _values;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(Bytes32ToBytes32Map storage map, bytes32 key, bytes32 value) internal returns (bool) {
        map._values[key] = value;
        return map._keys.add(key);
    }

    /**
     * @dev Removes a key-value pair from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(Bytes32ToBytes32Map storage map, bytes32 key) internal returns (bool) {
        delete map._values[key];
        return map._keys.remove(key);
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool) {
        return map._keys.contains(key);
    }

    /**
     * @dev Returns the number of key-value pairs in the map. O(1).
     */
    function length(Bytes32ToBytes32Map storage map) internal view returns (uint256) {
        return map._keys.length();
    }

    /**
     * @dev Returns the key-value pair stored at position `index` in the map. O(1).
     *
     * Note that there are no guarantees on the ordering of entries inside the
     * array, and it may change when more entries are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32ToBytes32Map storage map, uint256 index) internal view returns (bytes32, bytes32) {
        bytes32 key = map._keys.at(index);
        return (key, map._values[key]);
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool, bytes32) {
        bytes32 value = map._values[key];
        if (value == bytes32(0)) {
            return (contains(map, key), bytes32(0));
        } else {
            return (true, value);
        }
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bytes32) {
        bytes32 value = map._values[key];
        if (value == 0 && !contains(map, key)) {
            revert EnumerableMapNonexistentKey(key);
        }
        return value;
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(Bytes32ToBytes32Map storage map) internal view returns (bytes32[] memory) {
        return map._keys.values();
    }

    // UintToUintMap

    struct UintToUintMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(UintToUintMap storage map, uint256 key, uint256 value) internal returns (bool) {
        return set(map._inner, bytes32(key), bytes32(value));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(UintToUintMap storage map, uint256 key) internal returns (bool) {
        return remove(map._inner, bytes32(key));
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(UintToUintMap storage map, uint256 key) internal view returns (bool) {
        return contains(map._inner, bytes32(key));
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(UintToUintMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintToUintMap storage map, uint256 index) internal view returns (uint256, uint256) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (uint256(key), uint256(value));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(UintToUintMap storage map, uint256 key) internal view returns (bool, uint256) {
        (bool success, bytes32 value) = tryGet(map._inner, bytes32(key));
        return (success, uint256(value));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(UintToUintMap storage map, uint256 key) internal view returns (uint256) {
        return uint256(get(map._inner, bytes32(key)));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(UintToUintMap storage map) internal view returns (uint256[] memory) {
        bytes32[] memory store = keys(map._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // UintToAddressMap

    struct UintToAddressMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(UintToAddressMap storage map, uint256 key, address value) internal returns (bool) {
        return set(map._inner, bytes32(key), bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(UintToAddressMap storage map, uint256 key) internal returns (bool) {
        return remove(map._inner, bytes32(key));
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(UintToAddressMap storage map, uint256 key) internal view returns (bool) {
        return contains(map._inner, bytes32(key));
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(UintToAddressMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintToAddressMap storage map, uint256 index) internal view returns (uint256, address) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (uint256(key), address(uint160(uint256(value))));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(UintToAddressMap storage map, uint256 key) internal view returns (bool, address) {
        (bool success, bytes32 value) = tryGet(map._inner, bytes32(key));
        return (success, address(uint160(uint256(value))));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(UintToAddressMap storage map, uint256 key) internal view returns (address) {
        return address(uint160(uint256(get(map._inner, bytes32(key)))));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(UintToAddressMap storage map) internal view returns (uint256[] memory) {
        bytes32[] memory store = keys(map._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // AddressToUintMap

    struct AddressToUintMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(AddressToUintMap storage map, address key, uint256 value) internal returns (bool) {
        return set(map._inner, bytes32(uint256(uint160(key))), bytes32(value));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(AddressToUintMap storage map, address key) internal returns (bool) {
        return remove(map._inner, bytes32(uint256(uint160(key))));
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(AddressToUintMap storage map, address key) internal view returns (bool) {
        return contains(map._inner, bytes32(uint256(uint160(key))));
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(AddressToUintMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(AddressToUintMap storage map, uint256 index) internal view returns (address, uint256) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (address(uint160(uint256(key))), uint256(value));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(AddressToUintMap storage map, address key) internal view returns (bool, uint256) {
        (bool success, bytes32 value) = tryGet(map._inner, bytes32(uint256(uint160(key))));
        return (success, uint256(value));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(AddressToUintMap storage map, address key) internal view returns (uint256) {
        return uint256(get(map._inner, bytes32(uint256(uint160(key)))));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(AddressToUintMap storage map) internal view returns (address[] memory) {
        bytes32[] memory store = keys(map._inner);
        address[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // Bytes32ToUintMap

    struct Bytes32ToUintMap {
        Bytes32ToBytes32Map _inner;
    }

    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(Bytes32ToUintMap storage map, bytes32 key, uint256 value) internal returns (bool) {
        return set(map._inner, key, bytes32(value));
    }

    /**
     * @dev Removes a value from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(Bytes32ToUintMap storage map, bytes32 key) internal returns (bool) {
        return remove(map._inner, key);
    }

    /**
     * @dev Returns true if the key is in the map. O(1).
     */
    function contains(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool) {
        return contains(map._inner, key);
    }

    /**
     * @dev Returns the number of elements in the map. O(1).
     */
    function length(Bytes32ToUintMap storage map) internal view returns (uint256) {
        return length(map._inner);
    }

    /**
     * @dev Returns the element stored at position `index` in the map. O(1).
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32ToUintMap storage map, uint256 index) internal view returns (bytes32, uint256) {
        (bytes32 key, bytes32 value) = at(map._inner, index);
        return (key, uint256(value));
    }

    /**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool, uint256) {
        (bool success, bytes32 value) = tryGet(map._inner, key);
        return (success, uint256(value));
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(Bytes32ToUintMap storage map, bytes32 key) internal view returns (uint256) {
        return uint256(get(map._inner, key));
    }

    /**
     * @dev Return the an array containing all the keys
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the map grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function keys(Bytes32ToUintMap storage map) internal view returns (bytes32[] memory) {
        bytes32[] memory store = keys(map._inner);
        bytes32[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }
}

// File: solady/src/utils/LibBit.sol



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

/// @notice Library for bit twiddling and boolean operations.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibBit.sol)
/// @author Inspired by (https://graphics.stanford.edu/~seander/bithacks.html)
library LibBit {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                  BIT TWIDDLING OPERATIONS                  */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Find last set.
    /// Returns the index of the most significant bit of `x`,
    /// counting from the least significant bit position.
    /// If `x` is zero, returns 256.
    function fls(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            r := or(shl(8, iszero(x)), shl(7, lt(0xffffffffffffffffffffffffffffffff, x)))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
            r := or(r, shl(4, lt(0xffff, shr(r, x))))
            r := or(r, shl(3, lt(0xff, shr(r, x))))
            r := or(r, shl(2, lt(0xf, shr(r, x))))
            r := or(r, byte(shr(r, x), hex"00000101020202020303030303030303"))
        }
    }

    /// @dev Count leading zeros.
    /// Returns the number of zeros preceding the most significant one bit.
    /// If `x` is zero, returns 256.
    function clz(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
            r := or(r, shl(4, lt(0xffff, shr(r, x))))
            r := or(r, shl(3, lt(0xff, shr(r, x))))
            r := or(r, shl(2, lt(0xf, shr(r, x))))
            // forgefmt: disable-next-item
            r := add(iszero(x), xor(255,
                or(r, byte(shr(r, x), hex"00000101020202020303030303030303"))))
        }
    }

    /// @dev Find first set.
    /// Returns the index of the least significant bit of `x`,
    /// counting from the least significant bit position.
    /// If `x` is zero, returns 256.
    /// Equivalent to `ctz` (count trailing zeros), which gives
    /// the number of zeros following the least significant one bit.
    function ffs(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            // Isolate the least significant bit.
            let b := and(x, add(not(x), 1))

            r := or(shl(8, iszero(x)), shl(7, lt(0xffffffffffffffffffffffffffffffff, b)))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, b))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, b))))

            // For the remaining 32 bits, use a De Bruijn lookup.
            // forgefmt: disable-next-item
            r := or(r, byte(and(div(0xd76453e0, shr(r, b)), 0x1f),
                0x001f0d1e100c1d070f090b19131c1706010e11080a1a141802121b1503160405))
        }
    }

    /// @dev Returns the number of set bits in `x`.
    function popCount(uint256 x) internal pure returns (uint256 c) {
        /// @solidity memory-safe-assembly
        assembly {
            let max := not(0)
            let isMax := eq(x, max)
            x := sub(x, and(shr(1, x), div(max, 3)))
            x := add(and(x, div(max, 5)), and(shr(2, x), div(max, 5)))
            x := and(add(x, shr(4, x)), div(max, 17))
            c := or(shl(8, isMax), shr(248, mul(x, div(max, 255))))
        }
    }

    /// @dev Returns whether `x` is a power of 2.
    function isPo2(uint256 x) internal pure returns (bool result) {
        /// @solidity memory-safe-assembly
        assembly {
            // Equivalent to `x && !(x & (x - 1))`.
            result := iszero(add(and(x, sub(x, 1)), iszero(x)))
        }
    }

    /// @dev Returns `x` reversed at the bit level.
    function reverseBits(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            // Computing masks on-the-fly reduces bytecode size by about 500 bytes.
            let m := not(0)
            r := x
            for { let s := 128 } 1 {} {
                m := xor(m, shl(s, m))
                r := or(and(shr(s, r), m), and(shl(s, r), not(m)))
                s := shr(1, s)
                if iszero(s) { break }
            }
        }
    }

    /// @dev Returns `x` reversed at the byte level.
    function reverseBytes(uint256 x) internal pure returns (uint256 r) {
        /// @solidity memory-safe-assembly
        assembly {
            // Computing masks on-the-fly reduces bytecode size by about 200 bytes.
            let m := not(0)
            r := x
            for { let s := 128 } 1 {} {
                m := xor(m, shl(s, m))
                r := or(and(shr(s, r), m), and(shl(s, r), not(m)))
                s := shr(1, s)
                if eq(s, 4) { break }
            }
        }
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                     BOOLEAN OPERATIONS                     */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    // A Solidity bool on the stack or memory is represented as a 256-bit word.
    // Non-zero values are true, zero is false.
    // A clean bool is either 0 (false) or 1 (true) under the hood.
    // Usually, if not always, the bool result of a regular Solidity expression,
    // or the argument of a public/external function will be a clean bool.
    // You can usually use the raw variants for more performance.
    // If uncertain, test (best with exact compiler settings).
    // Or use the non-raw variants (compiler can sometimes optimize out the double `iszero`s).

    /// @dev Returns `x & y`. Inputs must be clean.
    function rawAnd(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := and(x, y)
        }
    }

    /// @dev Returns `x & y`.
    function and(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := and(iszero(iszero(x)), iszero(iszero(y)))
        }
    }

    /// @dev Returns `x | y`. Inputs must be clean.
    function rawOr(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := or(x, y)
        }
    }

    /// @dev Returns `x | y`.
    function or(bool x, bool y) internal pure returns (bool z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := or(iszero(iszero(x)), iszero(iszero(y)))
        }
    }

    /// @dev Returns 1 if `b` is true, else 0. Input must be clean.
    function rawToUint(bool b) internal pure returns (uint256 z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := b
        }
    }

    /// @dev Returns 1 if `b` is true, else 0.
    function toUint(bool b) internal pure returns (uint256 z) {
        /// @solidity memory-safe-assembly
        assembly {
            z := iszero(iszero(b))
        }
    }
}

// File: ERC721Psi/ERC721Psi.sol



// SPDX-License-Identifier: MIT
/**
  ______ _____   _____ ______ ___  __ _  _  _ 
 |  ____|  __ \ / ____|____  |__ \/_ | || || |
 | |__  | |__) | |        / /   ) || | \| |/ |
 |  __| |  _  /| |       / /   / / | |\_   _/ 
 | |____| | \ \| |____  / /   / /_ | |  | |   
 |______|_|  \_\\_____|/_/   |____||_|  |_|   

 - github: https://github.com/estarriolvetch/ERC721Psi
 - npm: https://www.npmjs.com/package/erc721psi

 */

pragma solidity ^0.8.0;

import "@openzeppelin/contracts/utils/Strings.sol";
import "@openzeppelin/contracts/utils/Address.sol";
import "solady/src/utils/LibBitmap.sol";
import "./interface/IERC721Psi.sol";

/**
 * @dev Interface of ERC721 token receiver.
 */
interface ERC721Psi__IERC721Receiver {
    function onERC721Received(
        address operator,
        address from,
        uint256 tokenId,
        bytes calldata data
    ) external returns (bytes4);
}

contract ERC721Psi is IERC721Psi {
    
    using Address for address;
    using Strings for uint256;
    using LibBitmap for LibBitmap.Bitmap;

    LibBitmap.Bitmap private _batchHead;

    string private _name;
    string private _symbol;

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

    mapping(uint256 => address) private _tokenApprovals;
    mapping(address => mapping(address => bool)) private _operatorApprovals;

    // The mask of the lower 160 bits for addresses.
    uint256 private constant _BITMASK_ADDRESS = (1 << 160) - 1;
    // The `Transfer` event signature is given by:
    // `keccak256(bytes("Transfer(address,address,uint256)"))`.
    bytes32 private constant _TRANSFER_EVENT_SIGNATURE =
        0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef;

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

    /**
     * @dev Returns the starting token ID.
     * To change the starting token ID, please override this function.
     */
    function _startTokenId() internal view virtual returns (uint256) {
        return 0;
    }

    /**
     * @dev Returns the next token ID to be minted.
     */
    function _nextTokenId() internal view virtual returns (uint256) {
        return _currentIndex;
    }

    /**
     * @dev Returns the total amount of tokens minted in the contract.
     */
    function _totalMinted() internal view virtual returns (uint256) {
        return _currentIndex - _startTokenId();
    }


    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * [EIP section](https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified)
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30000 gas.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        // The interface IDs are constants representing the first 4 bytes
        // of the XOR of all function selectors in the interface.
        // See: [ERC165](https://eips.ethereum.org/EIPS/eip-165)
        // (e.g. `bytes4(i.functionA.selector ^ i.functionB.selector ^ ...)`)
        return
            interfaceId == 0x01ffc9a7 || // ERC165 interface ID for ERC165.
            interfaceId == 0x80ac58cd || // ERC165 interface ID for ERC721.
            interfaceId == 0x5b5e139f; // ERC165 interface ID for ERC721Metadata.
    }

    /**
     * @dev See {IERC721-balanceOf}.
     */
    function balanceOf(address owner) 
        public 
        view 
        virtual 
        override 
        returns (uint) 
    {
        if(owner == address(0)) revert BalanceQueryForZeroAddress();

        uint count;
        for( uint i = _startTokenId(); i < _nextTokenId(); ++i ){
            if(_exists(i)){
                if( owner == ownerOf(i)){
                    ++count;
                }
            }
        }
        return count;
    }

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId)
        public
        view
        virtual
        override
        returns (address)
    {
        (address owner, ) = _ownerAndBatchHeadOf(tokenId);
        return owner;
    }

    function _ownerAndBatchHeadOf(uint256 tokenId) internal view returns (address owner, uint256 tokenIdBatchHead){
        if (!_exists(tokenId)) revert OwnerQueryForNonexistentToken();
        tokenIdBatchHead = _getBatchHead(tokenId);
        owner = _owners[tokenIdBatchHead];
    }

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

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

    /**
     * @dev See {IERC721Metadata-tokenURI}.
     */
    function tokenURI(uint256 tokenId) public view virtual override returns (string memory) {
        if( !_exists(tokenId)) revert URIQueryForNonexistentToken();
        string memory baseURI = _baseURI();
        return bytes(baseURI).length > 0 ? string(abi.encodePacked(baseURI, tokenId.toString())) : "";
    }

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


    /**
     * @dev See {IERC721-approve}.
     */
    function approve(address to, uint256 tokenId) public payable virtual override {
        address owner = ownerOf(tokenId);

        if (_msgSenderERC721Psi() != owner) {
            if (!isApprovedForAll(owner, _msgSenderERC721Psi())) {
                revert ApprovalCallerNotOwnerNorApproved();
            }
        }

        _approve(to, tokenId);
    }

    /**
     * @dev See {IERC721-getApproved}.
     */
    function getApproved(uint256 tokenId)
        public
        view
        virtual
        override
        returns (address) 
    {
        if (!_exists(tokenId)) revert ApprovalQueryForNonexistentToken();

        return _tokenApprovals[tokenId];
    }

    /**
     * @dev See {IERC721-setApprovalForAll}.
     */
    function setApprovalForAll(address operator, bool approved)
        public
        virtual
        override
    {
        _operatorApprovals[_msgSenderERC721Psi()][operator] = approved;
        emit ApprovalForAll(_msgSenderERC721Psi(), operator, approved);
    }

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

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

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

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

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

    /**
     * @dev Returns whether `tokenId` exists.
     *
     * Tokens can be managed by their owner or approved accounts via {approve} or {setApprovalForAll}.
     *
     * Tokens start existing when they are minted (`_mint`).
     */
    function _exists(uint256 tokenId) internal view virtual returns (bool) {
        return tokenId < _nextTokenId() && _startTokenId() <= tokenId;
    }

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

    /**
     * @dev Safely mints `quantity` tokens and transfers them to `to`.
     *
     * Requirements:
     *
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called for each safe transfer.
     * - `quantity` must be greater than 0.
     *
     * Emits a {Transfer} event.
     */
    function _safeMint(address to, uint256 quantity) internal virtual {
        _safeMint(to, quantity, "");
    }

    
    function _safeMint(
        address to,
        uint256 quantity,
        bytes memory _data
    ) internal virtual {
        _mint(to, quantity);
        uint256 end = _currentIndex;
        if (!_checkOnERC721Received(address(0), to, end - quantity, quantity, _data)) {
            revert TransferToNonERC721ReceiverImplementer();
        }
        // Reentrancy protection.
        if (_currentIndex != end) revert();
    }


    function _mint(
        address to,
        uint256 quantity
    ) internal virtual {
        uint256 nextTokenId = _nextTokenId();
        
        if (quantity == 0) revert MintZeroQuantity();
        if (to == address(0)) revert MintToZeroAddress();
        
        _beforeTokenTransfers(address(0), to, nextTokenId, quantity);
        _currentIndex += quantity;
        _owners[nextTokenId] = to;
        _batchHead.set(nextTokenId);

        uint256 toMasked;
        uint256 end = nextTokenId + quantity;

        // Use assembly to loop and emit the `Transfer` event for gas savings.
        // The duplicated `log4` removes an extra check and reduces stack juggling.
        // The assembly, together with the surrounding Solidity code, have been
        // delicately arranged to nudge the compiler into producing optimized opcodes.
        assembly {
            // Mask `to` to the lower 160 bits, in case the upper bits somehow aren't clean.
            toMasked := and(to, _BITMASK_ADDRESS)
            // Emit the `Transfer` event.
            log4(
                0, // Start of data (0, since no data).
                0, // End of data (0, since no data).
                _TRANSFER_EVENT_SIGNATURE, // Signature.
                0, // `address(0)`.
                toMasked, // `to`.
                nextTokenId // `tokenId`.
            )

            // The `iszero(eq(,))` check ensures that large values of `quantity`
            // that overflows uint256 will make the loop run out of gas.
            // The compiler will optimize the `iszero` away for performance.
            for {
                let tokenId := add(nextTokenId, 1)
            } iszero(eq(tokenId, end)) {
                tokenId := add(tokenId, 1)
            } {
                // Emit the `Transfer` event. Similar to above.
                log4(0, 0, _TRANSFER_EVENT_SIGNATURE, 0, toMasked, tokenId)
            }
        }

        _afterTokenTransfers(address(0), to, nextTokenId, quantity);
    }


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

        (address owner, uint256 tokenIdBatchHead) = _ownerAndBatchHeadOf(tokenId);

        if (owner != from) revert TransferFromIncorrectOwner();

        if (!_isApprovedOrOwner(_msgSenderERC721Psi(), tokenId)) {
            revert TransferCallerNotOwnerNorApproved();
        }

        if (to == address(0)) revert TransferToZeroAddress();

        _beforeTokenTransfers(from, to, tokenId, 1);

        // Clear approvals from the previous owner
        _approve(address(0), tokenId);   

        uint256 subsequentTokenId = tokenId + 1;

        if(!_batchHead.get(subsequentTokenId) &&  
            subsequentTokenId < _nextTokenId()
        ) {
            _owners[subsequentTokenId] = from;
            _batchHead.set(subsequentTokenId);
        }

        _owners[tokenId] = to;
        if(tokenId != tokenIdBatchHead) {
            _batchHead.set(tokenId);
        }

        emit Transfer(from, to, tokenId);

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

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

    /**
     * @dev Internal function to invoke {IERC721Receiver-onERC721Received} on a target address.
     * The call is not executed if the target address is not a contract.
     *
     * @param from address representing the previous owner of the given token ID
     * @param to target address that will receive the tokens
     * @param startTokenId uint256 the first ID of the tokens to be transferred
     * @param quantity uint256 amount of the tokens to be transfered.
     * @param _data bytes optional data to send along with the call
     * @return r bool whether the call correctly returned the expected magic value
     */
    function _checkOnERC721Received(
        address from,
        address to,
        uint256 startTokenId,
        uint256 quantity,
        bytes memory _data
    ) private returns (bool r) {
        /// @dev removed isContract() in v5.0 but their ERC721 uses this check:
        if (to.code.length > 0) {
            r = true;
            for(uint256 tokenId = startTokenId; tokenId < startTokenId + quantity; tokenId++){
                try ERC721Psi__IERC721Receiver(to).onERC721Received( _msgSenderERC721Psi(), from, tokenId, _data) returns (bytes4 retval) {
                    r = r && retval == ERC721Psi__IERC721Receiver.onERC721Received.selector;
                } catch (bytes memory reason) {
                    if (reason.length == 0) {
                        revert TransferToNonERC721ReceiverImplementer();
                    } else {
                        assembly {
                            revert(add(32, reason), mload(reason))
                        }
                    }
                }
            }
            return r;
        } else {
            return true;
        }
    }

    function _getBatchHead(uint256 tokenId) internal view returns (uint256 tokenIdBatchHead) {
        tokenIdBatchHead = _batchHead.findLastSet(tokenId); 
    }


    function totalSupply() public virtual override view returns (uint256) {
        return _totalMinted();
    }

    /**
     * @dev Returns an array of token IDs owned by `owner`.
     *
     * This function scans the ownership mapping and is O(`totalSupply`) in complexity.
     * It is meant to be called off-chain.
     *
     * This function is compatiable with ERC721AQueryable.
     */
    function tokensOfOwner(address owner) external view virtual returns (uint256[] memory) {
        unchecked {
            uint256 tokenIdsIdx;
            uint256 tokenIdsLength = balanceOf(owner);
            uint256[] memory tokenIds = new uint256[](tokenIdsLength);
            for (uint256 i = _startTokenId(); tokenIdsIdx != tokenIdsLength; ++i) {
                if (_exists(i)) {
                    if (ownerOf(i) == owner) {
                        tokenIds[tokenIdsIdx++] = i;
                    }
                }
            }
            return tokenIds;   
        }
    }

    /**
     * @dev Hook that is called before a set of serially-ordered token ids are about to be transferred. This includes minting.
     *
     * startTokenId - the first token id to be transferred
     * quantity - the amount to be transferred
     *
     * Calling conditions:
     *
     * - When `from` and `to` are both non-zero, ``from``'s `tokenId` will be
     * transferred to `to`.
     * - When `from` is zero, `tokenId` will be minted for `to`.
     */
    function _beforeTokenTransfers(
        address from,
        address to,
        uint256 startTokenId,
        uint256 quantity
    ) internal virtual {}

    /**
     * @dev Hook that is called after a set of serially-ordered token ids have been transferred. This includes
     * minting.
     *
     * startTokenId - the first token id to be transferred
     * quantity - the amount to be transferred
     *
     * Calling conditions:
     *
     * - when `from` and `to` are both non-zero.
     * - `from` and `to` are never both zero.
     */
    function _afterTokenTransfers(
        address from,
        address to,
        uint256 startTokenId,
        uint256 quantity
    ) internal virtual {}


    /**
     * @dev Returns the message sender (defaults to `msg.sender`).
     *
     * If you are writing GSN compatible contracts, you need to override this function.
     */
    function _msgSenderERC721Psi() internal view virtual returns (address) {
        return msg.sender;
    }
}
// File: solady/src/utils/LibBitmap.sol



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

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

/// @notice Library for storage of packed unsigned booleans.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibBitmap.sol)
/// @author Modified from Solmate (https://github.com/transmissions11/solmate/blob/main/src/utils/LibBitmap.sol)
/// @author Modified from Solidity-Bits (https://github.com/estarriolvetch/solidity-bits/blob/main/contracts/BitMaps.sol)
library LibBitmap {
    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                         CONSTANTS                          */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev The constant returned when a bitmap scan does not find a result.
    uint256 internal constant NOT_FOUND = type(uint256).max;

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                          STRUCTS                           */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev A bitmap in storage.
    struct Bitmap {
        mapping(uint256 => uint256) map;
    }

    /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
    /*                         OPERATIONS                         */
    /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

    /// @dev Returns the boolean value of the bit at `index` in `bitmap`.
    function get(Bitmap storage bitmap, uint256 index) internal view returns (bool isSet) {
        // It is better to set `isSet` to either 0 or 1, than zero vs non-zero.
        // Both cost the same amount of gas, but the former allows the returned value
        // to be reused without cleaning the upper bits.
        uint256 b = (bitmap.map[index >> 8] >> (index & 0xff)) & 1;
        /// @solidity memory-safe-assembly
        assembly {
            isSet := b
        }
    }

    /// @dev Updates the bit at `index` in `bitmap` to true.
    function set(Bitmap storage bitmap, uint256 index) internal {
        bitmap.map[index >> 8] |= (1 << (index & 0xff));
    }

    /// @dev Updates the bit at `index` in `bitmap` to false.
    function unset(Bitmap storage bitmap, uint256 index) internal {
        bitmap.map[index >> 8] &= ~(1 << (index & 0xff));
    }

    /// @dev Flips the bit at `index` in `bitmap`.
    /// Returns the boolean result of the flipped bit.
    function toggle(Bitmap storage bitmap, uint256 index) internal returns (bool newIsSet) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, index))
            let storageSlot := keccak256(0x00, 0x40)
            let shift := and(index, 0xff)
            let storageValue := xor(sload(storageSlot), shl(shift, 1))
            // It makes sense to return the `newIsSet`,
            // as it allow us to skip an additional warm `sload`,
            // and it costs minimal gas (about 15),
            // which may be optimized away if the returned value is unused.
            newIsSet := and(1, shr(shift, storageValue))
            sstore(storageSlot, storageValue)
        }
    }

    /// @dev Updates the bit at `index` in `bitmap` to `shouldSet`.
    function setTo(Bitmap storage bitmap, uint256 index, bool shouldSet) internal {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, index))
            let storageSlot := keccak256(0x00, 0x40)
            let storageValue := sload(storageSlot)
            let shift := and(index, 0xff)
            sstore(
                storageSlot,
                // Unsets the bit at `shift` via `and`, then sets its new value via `or`.
                or(and(storageValue, not(shl(shift, 1))), shl(shift, iszero(iszero(shouldSet))))
            )
        }
    }

    /// @dev Consecutively sets `amount` of bits starting from the bit at `start`.
    function setBatch(Bitmap storage bitmap, uint256 start, uint256 amount) internal {
        /// @solidity memory-safe-assembly
        assembly {
            let max := not(0)
            let shift := and(start, 0xff)
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, start))
            if iszero(lt(add(shift, amount), 257)) {
                let storageSlot := keccak256(0x00, 0x40)
                sstore(storageSlot, or(sload(storageSlot), shl(shift, max)))
                let bucket := add(mload(0x00), 1)
                let bucketEnd := add(mload(0x00), shr(8, add(amount, shift)))
                amount := and(add(amount, shift), 0xff)
                shift := 0
                for {} iszero(eq(bucket, bucketEnd)) { bucket := add(bucket, 1) } {
                    mstore(0x00, bucket)
                    sstore(keccak256(0x00, 0x40), max)
                }
                mstore(0x00, bucket)
            }
            let storageSlot := keccak256(0x00, 0x40)
            sstore(storageSlot, or(sload(storageSlot), shl(shift, shr(sub(256, amount), max))))
        }
    }

    /// @dev Consecutively unsets `amount` of bits starting from the bit at `start`.
    function unsetBatch(Bitmap storage bitmap, uint256 start, uint256 amount) internal {
        /// @solidity memory-safe-assembly
        assembly {
            let shift := and(start, 0xff)
            mstore(0x20, bitmap.slot)
            mstore(0x00, shr(8, start))
            if iszero(lt(add(shift, amount), 257)) {
                let storageSlot := keccak256(0x00, 0x40)
                sstore(storageSlot, and(sload(storageSlot), not(shl(shift, not(0)))))
                let bucket := add(mload(0x00), 1)
                let bucketEnd := add(mload(0x00), shr(8, add(amount, shift)))
                amount := and(add(amount, shift), 0xff)
                shift := 0
                for {} iszero(eq(bucket, bucketEnd)) { bucket := add(bucket, 1) } {
                    mstore(0x00, bucket)
                    sstore(keccak256(0x00, 0x40), 0)
                }
                mstore(0x00, bucket)
            }
            let storageSlot := keccak256(0x00, 0x40)
            sstore(
                storageSlot, and(sload(storageSlot), not(shl(shift, shr(sub(256, amount), not(0)))))
            )
        }
    }

    /// @dev Returns number of set bits within a range by
    /// scanning `amount` of bits starting from the bit at `start`.
    function popCount(Bitmap storage bitmap, uint256 start, uint256 amount)
        internal
        view
        returns (uint256 count)
    {
        unchecked {
            uint256 bucket = start >> 8;
            uint256 shift = start & 0xff;
            if (!(amount + shift < 257)) {
                count = LibBit.popCount(bitmap.map[bucket] >> shift);
                uint256 bucketEnd = bucket + ((amount + shift) >> 8);
                amount = (amount + shift) & 0xff;
                shift = 0;
                for (++bucket; bucket != bucketEnd; ++bucket) {
                    count += LibBit.popCount(bitmap.map[bucket]);
                }
            }
            count += LibBit.popCount((bitmap.map[bucket] >> shift) << (256 - amount));
        }
    }

    /// @dev Returns the index of the most significant set bit before the bit at `before`.
    /// If no set bit is found, returns `NOT_FOUND`.
    function findLastSet(Bitmap storage bitmap, uint256 before)
        internal
        view
        returns (uint256 setBitIndex)
    {
        uint256 bucket;
        uint256 bucketBits;
        /// @solidity memory-safe-assembly
        assembly {
            setBitIndex := not(0)
            bucket := shr(8, before)
            mstore(0x00, bucket)
            mstore(0x20, bitmap.slot)
            let offset := and(0xff, not(before)) // `256 - (255 & before) - 1`.
            bucketBits := shr(offset, shl(offset, sload(keccak256(0x00, 0x40))))
            if iszero(or(bucketBits, iszero(bucket))) {
                for {} 1 {} {
                    bucket := add(bucket, setBitIndex) // `sub(bucket, 1)`.
                    mstore(0x00, bucket)
                    bucketBits := sload(keccak256(0x00, 0x40))
                    if or(bucketBits, iszero(bucket)) { break }
                }
            }
        }
        if (bucketBits != 0) {
            setBitIndex = (bucket << 8) | LibBit.fls(bucketBits);
            /// @solidity memory-safe-assembly
            assembly {
                setBitIndex := or(setBitIndex, sub(0, gt(setBitIndex, before)))
            }
        }
    }
}

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



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (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;
    }
}

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



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

pragma solidity ^0.8.20;

/**
 * @dev Collection of functions related to the address type
 */
library Address {
    /**
     * @dev The ETH balance of the account is not enough to perform the operation.
     */
    error AddressInsufficientBalance(address account);

    /**
     * @dev There's no code at `target` (it is not a contract).
     */
    error AddressEmptyCode(address target);

    /**
     * @dev A call to an address target failed. The target may have reverted.
     */
    error FailedInnerCall();

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

        (bool success, ) = recipient.call{value: amount}("");
        if (!success) {
            revert FailedInnerCall();
        }
    }

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

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     */
    function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory) {
        if (address(this).balance < value) {
            revert AddressInsufficientBalance(address(this));
        }
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResultFromTarget(target, success, returndata);
    }

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

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

    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and reverts if the target
     * was not a contract or bubbling up the revert reason (falling back to {FailedInnerCall}) in case of an
     * unsuccessful call.
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata
    ) internal view returns (bytes memory) {
        if (!success) {
            _revert(returndata);
        } else {
            // only check if target is a contract if the call was successful and the return data is empty
            // otherwise we already know that it was a contract
            if (returndata.length == 0 && target.code.length == 0) {
                revert AddressEmptyCode(target);
            }
            return returndata;
        }
    }

    /**
     * @dev Tool to verify that a low level call was successful, and reverts if it wasn't, either by bubbling the
     * revert reason or with a default {FailedInnerCall} error.
     */
    function verifyCallResult(bool success, bytes memory returndata) internal pure returns (bytes memory) {
        if (!success) {
            _revert(returndata);
        } else {
            return returndata;
        }
    }

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

// File: ERC721Psi/interface/IERC721Psi.sol



// SPDX-License-Identifier: MIT

pragma solidity ^0.8.0;

/**
 * @dev Interface of ERC721Psi.
 */
interface IERC721Psi {
    /**
     * The caller must own the token or be an approved operator.
     */
    error ApprovalCallerNotOwnerNorApproved();

    /**
     * The token does not exist.
     */
    error ApprovalQueryForNonexistentToken();

    /**
     * Cannot query the balance for the zero address.
     */
    error BalanceQueryForZeroAddress();

    /**
     * Cannot mint to the zero address.
     */
    error MintToZeroAddress();

    /**
     * The quantity of tokens minted must be more than zero.
     */
    error MintZeroQuantity();

    /**
     * The token does not exist.
     */
    error OwnerQueryForNonexistentToken();

    /**
     * The caller must own the token or be an approved operator.
     */
    error TransferCallerNotOwnerNorApproved();

    /**
     * The token must be owned by `from`.
     */
    error TransferFromIncorrectOwner();

    /**
     * Cannot safely transfer to a contract that does not implement the
     * ERC721Receiver interface.
     */
    error TransferToNonERC721ReceiverImplementer();

    /**
     * Cannot transfer to the zero address.
     */
    error TransferToZeroAddress();

    /**
     * The token does not exist.
     */
    error URIQueryForNonexistentToken();


    // =============================================================
    //                         TOKEN COUNTERS
    // =============================================================

    /**
     * @dev Returns the total number of tokens in existence.
     * Burned tokens will reduce the count.
     * To get the total number of tokens minted, please see {_totalMinted}.
     */
    function totalSupply() external view returns (uint256);

    // =============================================================
    //                            IERC165
    // =============================================================

    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * [EIP section](https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified)
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);

    // =============================================================
    //                            IERC721
    // =============================================================

    /**
     * @dev Emitted when `tokenId` token is transferred from `from` to `to`.
     */
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

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

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

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

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

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

    /**
     * @dev Equivalent to `safeTransferFrom(from, to, tokenId, '')`.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external payable;

    /**
     * @dev Transfers `tokenId` from `from` to `to`.
     *
     * WARNING: Usage of this method is discouraged, use {safeTransferFrom}
     * whenever possible.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token
     * by either {approve} or {setApprovalForAll}.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external payable;

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

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

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

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

    // =============================================================
    //                        IERC721Metadata
    // =============================================================

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

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

    /**
     * @dev Returns the Uniform Resource Identifier (URI) for `tokenId` token.
     */
    function tokenURI(uint256 tokenId) external view returns (string memory);
}
// File: @openzeppelin/contracts/utils/Strings.sol



// 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));
    }
}

// File: @openzeppelin/contracts/utils/structs/EnumerableSet.sol



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

pragma solidity ^0.8.20;

/**
 * @dev Library for managing
 * https://en.wikipedia.org/wiki/Set_(abstract_data_type)[sets] of primitive
 * types.
 *
 * Sets have the following properties:
 *
 * - Elements are added, removed, and checked for existence in constant time
 * (O(1)).
 * - Elements are enumerated in O(n). No guarantees are made on the ordering.
 *
 * ```solidity
 * contract Example {
 *     // Add the library methods
 *     using EnumerableSet for EnumerableSet.AddressSet;
 *
 *     // Declare a set state variable
 *     EnumerableSet.AddressSet private mySet;
 * }
 * ```
 *
 * As of v3.3.0, sets of type `bytes32` (`Bytes32Set`), `address` (`AddressSet`)
 * and `uint256` (`UintSet`) are supported.
 *
 * [WARNING]
 * ====
 * Trying to delete such a structure from storage will likely result in data corruption, rendering the structure
 * unusable.
 * See https://github.com/ethereum/solidity/pull/11843[ethereum/solidity#11843] for more info.
 *
 * In order to clean an EnumerableSet, you can either remove all elements one by one or create a fresh instance using an
 * array of EnumerableSet.
 * ====
 */
library EnumerableSet {
    // To implement this library for multiple types with as little code
    // repetition as possible, we write it in terms of a generic Set type with
    // bytes32 values.
    // The Set implementation uses private functions, and user-facing
    // implementations (such as AddressSet) are just wrappers around the
    // underlying Set.
    // This means that we can only create new EnumerableSets for types that fit
    // in bytes32.

    struct Set {
        // Storage of set values
        bytes32[] _values;
        // Position is the index of the value in the `values` array plus 1.
        // Position 0 is used to mean a value is not in the set.
        mapping(bytes32 value => uint256) _positions;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function _add(Set storage set, bytes32 value) private returns (bool) {
        if (!_contains(set, value)) {
            set._values.push(value);
            // The value is stored at length-1, but we add 1 to all indexes
            // and use 0 as a sentinel value
            set._positions[value] = set._values.length;
            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function _remove(Set storage set, bytes32 value) private returns (bool) {
        // We cache the value's position to prevent multiple reads from the same storage slot
        uint256 position = set._positions[value];

        if (position != 0) {
            // Equivalent to contains(set, value)
            // To delete an element from the _values array in O(1), we swap the element to delete with the last one in
            // the array, and then remove the last element (sometimes called as 'swap and pop').
            // This modifies the order of the array, as noted in {at}.

            uint256 valueIndex = position - 1;
            uint256 lastIndex = set._values.length - 1;

            if (valueIndex != lastIndex) {
                bytes32 lastValue = set._values[lastIndex];

                // Move the lastValue to the index where the value to delete is
                set._values[valueIndex] = lastValue;
                // Update the tracked position of the lastValue (that was just moved)
                set._positions[lastValue] = position;
            }

            // Delete the slot where the moved value was stored
            set._values.pop();

            // Delete the tracked position for the deleted slot
            delete set._positions[value];

            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function _contains(Set storage set, bytes32 value) private view returns (bool) {
        return set._positions[value] != 0;
    }

    /**
     * @dev Returns the number of values on the set. O(1).
     */
    function _length(Set storage set) private view returns (uint256) {
        return set._values.length;
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function _at(Set storage set, uint256 index) private view returns (bytes32) {
        return set._values[index];
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function _values(Set storage set) private view returns (bytes32[] memory) {
        return set._values;
    }

    // Bytes32Set

    struct Bytes32Set {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _add(set._inner, value);
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _remove(set._inner, value);
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(Bytes32Set storage set, bytes32 value) internal view returns (bool) {
        return _contains(set._inner, value);
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(Bytes32Set storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32Set storage set, uint256 index) internal view returns (bytes32) {
        return _at(set._inner, index);
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(Bytes32Set storage set) internal view returns (bytes32[] memory) {
        bytes32[] memory store = _values(set._inner);
        bytes32[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // AddressSet

    struct AddressSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(AddressSet storage set, address value) internal returns (bool) {
        return _add(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(AddressSet storage set, address value) internal returns (bool) {
        return _remove(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(AddressSet storage set, address value) internal view returns (bool) {
        return _contains(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(AddressSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(AddressSet storage set, uint256 index) internal view returns (address) {
        return address(uint160(uint256(_at(set._inner, index))));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(AddressSet storage set) internal view returns (address[] memory) {
        bytes32[] memory store = _values(set._inner);
        address[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // UintSet

    struct UintSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(UintSet storage set, uint256 value) internal returns (bool) {
        return _add(set._inner, bytes32(value));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(UintSet storage set, uint256 value) internal returns (bool) {
        return _remove(set._inner, bytes32(value));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(UintSet storage set, uint256 value) internal view returns (bool) {
        return _contains(set._inner, bytes32(value));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(UintSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintSet storage set, uint256 index) internal view returns (uint256) {
        return uint256(_at(set._inner, index));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(UintSet storage set) internal view returns (uint256[] memory) {
        bytes32[] memory store = _values(set._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }
}

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



// 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);
        }
    }
}

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



// 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;
    }
}