library EnumerableMap {
	// 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 Uint256ToAddressMap) are just wrappers around
	// the underlying Map.
	// This means that we can only create new EnumerableMaps for types that fit
	// in bytes32.

	struct MapEntry {
		bytes32 _key;
		bytes32 _value;
	}

	struct Map {
		// Storage of map keys and values
		MapEntry[] _entries;

		// Position of the entry defined by a key in the `entries` array, plus 1
		// because index 0 means a key is not in the map.
		mapping (bytes32 => uint256) _indexes;
	}

	/**
	 * @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(Map storage map, bytes32 key, bytes32 value) private returns (bool) {
		// We read and store the key's index to prevent multiple reads from the same storage slot
		uint256 keyIndex = map._indexes[key];

		if (keyIndex == 0) { // Equivalent to !contains(map, key)
			map._entries.push(MapEntry({ _key: key, _value: value }));
			// The entry is stored at length-1, but we add 1 to all indexes
			// and use 0 as a sentinel value
			map._indexes[key] = map._entries.length;
			return true;
		} else {
			map._entries[keyIndex - 1]._value = value;
			return false;
		}
	}

	/**
	 * @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(Map storage map, bytes32 key) private returns (bool) {
		// We read and store the key's index to prevent multiple reads from the same storage slot
		uint256 keyIndex = map._indexes[key];

		if (keyIndex != 0) { // Equivalent to contains(map, key)
			// To delete a key-value pair from the _entries array in O(1), we swap the entry to delete with the last one
			// in the array, and then remove the last entry (sometimes called as 'swap and pop').
			// This modifies the order of the array, as noted in {at}.

			uint256 toDeleteIndex = keyIndex - 1;
			uint256 lastIndex = map._entries.length - 1;

			// When the entry to delete is the last one, the swap operation is unnecessary. However, since this occurs
			// so rarely, we still do the swap anyway to avoid the gas cost of adding an 'if' statement.

			MapEntry storage lastEntry = map._entries[lastIndex];

			// Move the last entry to the index where the entry to delete is
			map._entries[toDeleteIndex] = lastEntry;
			// Update the index for the moved entry
			map._indexes[lastEntry._key] = toDeleteIndex + 1; // All indexes are 1-based

			// Delete the slot where the moved entry was stored
			map._entries.pop();

			// Delete the index for the deleted slot
			delete map._indexes[key];

			return true;
		} else {
			return false;
		}
	}

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

	/**
	 * @dev Returns the number of key-value pairs in the map. O(1).
	 */
	function _length(Map storage map) private view returns (uint256) {
		return map._entries.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(Map storage map, uint256 index) private view returns (bytes32, bytes32) {
		require(map._entries.length > index, "EnumerableMap: index out of bounds");

		MapEntry storage entry = map._entries[index];
		return (entry._key, entry._value);
	}

	/**
	 * @dev Tries to returns the value associated with `key`.  O(1).
	 * Does not revert if `key` is not in the map.
	 */
	function _tryGet(Map storage map, bytes32 key) private view returns (bool, bytes32) {
		uint256 keyIndex = map._indexes[key];
		if (keyIndex == 0) return (false, 0); // Equivalent to contains(map, key)
		return (true, map._entries[keyIndex - 1]._value); // All indexes are 1-based
	}

	/**
	 * @dev Returns the value associated with `key`.  O(1).
	 *
	 * Requirements:
	 *
	 * - `key` must be in the map.
	 */
	function _get(Map storage map, bytes32 key) private view returns (bytes32) {
		uint256 keyIndex = map._indexes[key];
		require(keyIndex != 0, "EnumerableMap: nonexistent key"); // Equivalent to contains(map, key)
		return map._entries[keyIndex - 1]._value; // All indexes are 1-based
	}

	/**
	 * @dev Same as {_get}, with a custom error message when `key` is not in the map.
	 *
	 * CAUTION: This function is deprecated because it requires allocating memory for the error
	 * message unnecessarily. For custom revert reasons use {_tryGet}.
	 */
	function _get(Map storage map, bytes32 key, string memory errorMessage) private view returns (bytes32) {
		uint256 keyIndex = map._indexes[key];
		require(keyIndex != 0, errorMessage); // Equivalent to contains(map, key)
		return map._entries[keyIndex - 1]._value; // All indexes are 1-based
	}

	// UintToAddressMap

	struct UintToAddressMap {
		Map _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 set. 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 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(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.
	 *
	 * _Available since v3.4._
	 */
	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 Same as {get}, with a custom error message when `key` is not in the map.
	 *
	 * CAUTION: This function is deprecated because it requires allocating memory for the error
	 * message unnecessarily. For custom revert reasons use {tryGet}.
	 */
	function get(UintToAddressMap storage map, uint256 key, string memory errorMessage) internal view returns (address) {
		return address(uint160(uint256(_get(map._inner, bytes32(key), errorMessage))));
	}
}
function _set(Map storage map, bytes32 key, bytes32 value) private returns (bool) {
	// We read and store the key's index to prevent multiple reads from the same storage slot
	uint256 keyIndex = map._indexes[key];

	if (keyIndex == 0) { // Equivalent to !contains(map, key)
		map._entries.push(MapEntry({ _key: key, _value: value }));
		// The entry is stored at length-1, but we add 1 to all indexes
		// and use 0 as a sentinel value
		map._indexes[key] = map._entries.length;
		return true;
	} else {
		map._entries[keyIndex - 1]._value = value;
		return false;
	}
}

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