# "aabbcca" --> [('a', 2), ('b', 2), ('c', 2), ('a', 1)]

def compress(message: str) -> list[tuple[str, int]]:
    prev_unique = None
	ans = []
	for chr in message:
		if not(prev_unique) or prev_unique != chr:
			ans.append((chr, 1))
			prev_unique = chr
		else:
			ans[-1] = (chr, ans[-1][1] + 1)

	return ans

# "aabb" --> [('a', 2)]
# "c"    --> [('b', 2)]
# "ca"   --> [('c', 2)]

# c,c,a
class Encoder:
    def __init__(self) -> None:
        self.possible_next = None

    def receive(self, message: str) -> list[tuple[str, int]]:
		compressed = compress(message)

		if len(compressed) == 0:
			return []

		if not(self.possible_next):
			self.possible_next = compressed.pop()
			return compressed

		elif compressed[0][0] == self.possible_next[0]:
			merged = (compressed[0][0], compressed[0][1] + self.possible_next[1])
			compressed[0] = merged
			self.possible_next = compressed.pop()
			return compressed

		else:
			first = [self.possible_next]
			self.possible_next = compressed.pop()
			first.extend(compressed)
			return first

 # 4: "fg" --> []
 # 2: "c" --> []
 # 1: "ca" --> []
 # 0: "aabb" --> [('a', 2), ('b', 2), ('c', 1), ('a', 1)]
 # 3: "ddde" --> [('c', 1), ('d', 3), ('e', 1), ('f', 1)]
 class Encoder2:
    def __init__(self) -> None:
		self.possible_next_dict = {}
		self.msg_id_next = 0


    def receive(self, message_id: int, message: str) -> list[tuple[str, int]]:
		compressed = compress(message)

		if len(compressed) == 0:
			return []

		if message_id != msg_id_next:
			self.possible_next_dict[message_id] = compressed
			return []

		else:
			compressed = compress(message)

			for i in range(len(self.possible_next)):
				if self.possible_next_dict.get(msg_id_next + i + 1):

					next = self.possible_next_dict[msg_id_next + i + 1]
					if compressed[-1][0] == next[0][0]:



				else:
					break

			return compressed