contract ERC721 is Context, Ownable, ERC165, IERC721, IERC721Metadata {
  using Strings for uint256;

  string constant private ERR = "ERC721: ERROR";

  // Token name
  string internal _name;

  // Token symbol
  string internal _symbol;

  // Base URI
  string private _baseURI;

  // Current owner address index
  uint256 _ownerCounter = 0;

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

  // Mapping owner address to internal owner id + balances
  mapping(address => uint256) private _extToIntMap;

  // Mapping internal address to external address
  mapping(uint256 => address) private _intToExtMap;

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

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

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

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

  /**
   * @dev See {IERC721-balanceOf}.
   */
  function balanceOf(address owner)
    public
    view
    virtual
    override
    returns (uint256)
  {
    require(owner != address(0), ERR);
    return _extToIntMap[owner] >> 128;
  }

  /**
   * @dev See {IERC721-ownerOf}.
   */
  function ownerOf(uint256 tokenId)
    public
    view
    virtual
    override
    returns (address)
  {
    uint256 internalOwner = _getInternalOwner(tokenId);
    require(internalOwner != 0, ERR);
    return _intToExtMap[internalOwner];
  }

  /**
   * @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)
  {
    require(_getInternalOwner(tokenId) != 0, ERR);

    bytes memory bytesURI = bytes(_baseURI);
    if (bytesURI.length == 0 || bytesURI[bytesURI.length - 1] == '/')
      return string(abi.encodePacked(_baseURI, tokenId.toString(), ".json"));
    else return _baseURI;
  }

  function setBaseURI(string memory newBaseURI) external onlyOwner {
    _baseURI = newBaseURI;
  }

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

    require(
      _msgSender() == owner || isApprovedForAll(owner, _msgSender()),
      ERR
    );
    _approve(to, tokenId);
  }

  /**
   * @dev See {IERC721-getApproved}.
   */
  function getApproved(uint256 tokenId)
    public
    view
    virtual
    override
    returns (address)
  {
    require(_getInternalOwner(tokenId) != 0, ERR);

    return _tokenApprovals[tokenId];
  }

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

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

  /**
   * @dev See {IERC721-transferFrom}.
   */
  function transferFrom(
    address from,
    address to,
    uint256 tokenId
  ) public virtual override {
    //solhint-disable-next-line max-line-length
    require(
      _isApprovedOrOwner(_msgSender(), tokenId),
      ERR
    );

    _transfer(from, to, 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(_getInternalOwner(tokenId) != 0, ERR);
    address owner = ERC721.ownerOf(tokenId);
    return (spender == owner ||
      getApproved(tokenId) == spender ||
      isApprovedForAll(owner, spender));
  }

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

    uint256 toInt = _getInternalOwnerFromAddress(to);
    uint256 tokenIdEnd = tokenId + num;
    uint256 curBase = tokenId >> 4;
    uint256 mask = _owners[curBase];

    for (; tokenId < tokenIdEnd; ++tokenId) {
      // Update storage balance of previous bin
      uint256 base = tokenId >> 4;
      uint256 idBits = (tokenId & 0xF) << 4;
      if (base != curBase) {
        _owners[curBase] = mask;
        curBase = base;
        mask = _owners[curBase];
      }
      require(((mask >> idBits) & 0xFFFF) == 0, ERR);
      mask |= (toInt << idBits);

      emit Transfer(address(0), to, tokenId);
    }
    _owners[curBase] = mask;
    _extToIntMap[to] += num << 128;
  }

  /**
   * @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 {
    // Clear approvals
    _approve(address(0), tokenId);
    
    uint256 intOwner = _getInternalOwner(tokenId);
    require(intOwner != 0, ERR);
    _setInternalOwner(tokenId, 0);

    address owner = _intToExtMap[intOwner];
    _extToIntMap[owner] -= 1 << 128;

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

  /**
   * @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 {
    uint256 intOwner = _getInternalOwner(tokenId);
    require(
      _intToExtMap[intOwner] == from,
      ERR
    );
    require(to != address(0), ERR);

    // Clear approvals from the previous owner
    _approve(address(0), tokenId);
    
    uint256 toInt = _getInternalOwnerFromAddress(to);
    _setInternalOwner(tokenId, toInt);

    _extToIntMap[from] -= 1 << 128;
    _extToIntMap[to] += 1 << 128;

    emit Transfer(from, to, tokenId);
  }

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

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

  function _getInternalOwner(uint256 tokenId) internal view returns(uint256) {
    return (_owners[tokenId >> 4] >> ((tokenId & 0xF) << 4)) & 0xFFFF;
  }

  function _getInternalOwnerFromAddress(address externalOwner) internal returns(uint256) {
    uint256 intOwner = _extToIntMap[externalOwner];
    if (intOwner == 0) {
      require(_ownerCounter < 0xFFFF, ERR);
      _extToIntMap[externalOwner] = intOwner = ++_ownerCounter;
      _intToExtMap[intOwner] = externalOwner;
    }
    return uint256(uint128(intOwner));
  }

  function _setInternalOwner(uint256 tokenId, uint256 newOwner) internal {
    uint256 mask = _owners[tokenId >> 4] &~ (0xFFFF << ((tokenId & 0xF) << 4));
    _owners[tokenId >> 4] = mask | newOwner << ((tokenId & 0xF) << 4);
  }
}
/**
 * @dev Implementation of https://eips.ethereum.org/EIPS/eip-721[ERC721] Non-Fungible Token Standard, including
 * the Metadata extension, but not including the Enumerable extension, which is available separately as
 * {ERC721Enumerable}.
 */
function _isApprovedOrOwner(address spender, uint256 tokenId)
    internal
    view
    virtual
    returns (bool)
  {
    require(_getInternalOwner(tokenId) != 0, ERR);
    address owner = ERC721.ownerOf(tokenId);
    return (spender == owner ||
      getApproved(tokenId) == spender ||
      isApprovedForAll(owner, spender));
  }
/**
 * @dev Returns whether `spender` is allowed to manage `tokenId`.
 *
 * Requirements:
 *
 * - `tokenId` must exist.
 */