class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n //= 3
        return n == 1 

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        while n > 1:
            if n % 3 != 0:
                return False
            n //= 3
        return True

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(1, n + 1):
            val = i**x
            if val > n:
                break
            for j in range(n, val - 1, -1):
                dp[j] = (dp[j] + dp[j - val]) % MOD

        return dp[n]

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        mod = 10**9 + 7

        bins, rep = [], 1
        while n > 0:
            if n % 2 == 1:
                bins.append(rep)
            n //= 2
            rep *= 2

        m = len(bins)
        results = [[0] * m for _ in range(m)]
        for i in range(m):
            cur = 1
            for j in range(i, m):
                cur = cur * bins[j] % mod
                results[i][j] = cur

        ans = []
        for left, right in queries:
            ans.append(results[left][right])
        return ans

class Solution:
    def interpret(self, command: str) -> str:
        stack = []
        res = []
        for char in command:
            if char == ")":
                if stack:
                    res.extend(stack)
                    stack.clear()
                else:
                    res.append("o")
            elif char == "G":
                res.append("G")
            elif char != "(":
                stack.append(char)
        return "".join(res)

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        temp, res = word, 0
        while temp in sequence:
            res += 1
            temp += word
        return res

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        length = len(code)
        result = [0 for _ in range(length)]
        if k == 0:
            return result
        start, end, window_sum = 1, k + 1, 0
        if k < 0:
            start = length - (-k)
            end = length
        for i in range(start, end):
            window_sum += code[i]
        for i in range(length):
            result[i] = window_sum
            window_sum -= code[start % length]
            window_sum += code[end % length]
            start += 1
            end += 1
        return result

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0 or n == 1:
            return n
        nums = [0] * (n + 1)
        nums[1] = 1
        res = 1
        for i in range(2, n + 1):
            if i % 2 == 0:
                val = nums[i // 2]
            else:
                val = nums[i // 2] + nums[(i // 2) + 1]
            nums[i] = val
            res = max(res, val)
        return res

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        num_to_piece = {}
        for i, nums in enumerate(pieces):
            for num in nums:
                num_to_piece[num] = i
        i = 0
        length = len(arr)
        while i < length:
            num1 = arr[i]
            if num1 not in num_to_piece:
                return False
            piece = pieces[num_to_piece[num1]]
            for j, num2 in enumerate(piece):
                if i + j >= length:
                    return False
                num1 = arr[i + j]
                if num1 != num2:
                    return False
            i += len(piece)
        return True

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        freqs = collections.defaultdict(int)
        for num in nums:
            freqs[num] += 1
        nums.sort(key=lambda val: (freqs[val], -val))
        return nums

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        max_key, max_dur = keysPressed[0], releaseTimes[0]
        for i, num in enumerate(releaseTimes[1:], 1):
            dur = num - releaseTimes[i - 1]
            cur_key = keysPressed[i]
            if dur > max_dur or (dur == max_dur and cur_key > max_key):
                max_dur = dur
                max_key = cur_key
        return max_key

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        if n > 0 and n & (n - 1) == 0:
            return True
        def count_digits(num: int, out: list[int]) -> None:
            while num > 0:
                out.append(num % 10)
                num //= 10
            out.sort()
        target = []
        count_digits(n, target)
        cur = []
        for i in range(31):
            cur.clear()
            count_digits(1 << i, cur)
            if cur == target:
                return True
        return False

class Solution:
    def trimMean(self, arr: List[int]) -> float:
        arr.sort()
        length = len(arr)
        interval = length // 20
        res = sum(arr[interval:length - interval])
        res = (res / (length - interval * 2))
        return res

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        depth = 0
        for op in logs:
            if op == "../":
                depth = max(depth - 1, 0)
            elif op == "./":
                pass
            else:
                depth += 1
        return depth

class Solution:
    def reorderSpaces(self, text: str) -> str:
        res = []
        cur_word = []
        space_count = 0
        for char in text:
            if char == " ":
                space_count += 1
                if cur_word:
                    res.append("".join(cur_word))
                    cur_word.clear()
            else:
                cur_word.append(char)
        if cur_word:
            res.append("".join(cur_word))
        words = len(res) - 1
        if words == 0:
            join_str = ""
            rem_str = " " * space_count
        else:
            join_str = " " * (space_count // words) 
            rem_str = " " * (space_count % words)
        return "".join((join_str.join(res), rem_str))

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        length = len(arr)
        answer = 0
        for i, num in enumerate(arr):
            left, right = i, length - i - 1
            odd_left, odd_right = (left // 2) + 1, (right // 2) + 1
            even_left, even_right = (left + 1) // 2, (right + 1) // 2
            sub_count = (odd_left * odd_right) + (even_left * even_right)
            answer += num * sub_count
        return answer

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        res = 0
        for i in range(len(arr)):
            cur_sum = 0
            for j in range(i, len(arr)):
                cur_sum += arr[j]
                if (j - i + 1) % 2 != 0:
                    res += cur_sum
        return res

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

class Solution:
    def soupServings(self, n: int) -> float:
        m = ceil(n / 25)
        dp = collections.defaultdict(dict)

        def calculate_dp(i: int, j: int) -> float:
            if i <= 0 and j <= 0:
                return 0.5
            if i <= 0:
                return 1.0
            if j <= 0:
                return 0.0
            if i in dp and j in dp[i]:
                return dp[i][j]

            dp[i][j] = (
                calculate_dp(i - 4, j)
                + calculate_dp(i - 3, j - 1)
                + calculate_dp(i - 2, j - 2)
                + calculate_dp(i - 1, j - 3)
            ) / 4.0
            return dp[i][j]

        for k in range(1, m + 1):
            if calculate_dp(k, k) > 1 - 1e-5:
                return 1.0
        return calculate_dp(m, m)

class Solution:
    def maxCollectedFruits(self, fruits):
        n = len(fruits)
        ans = sum(fruits[i][i] for i in range(n))

        def dp():
            prev = [float("-inf")] * n
            curr = [float("-inf")] * n
            prev[n - 1] = fruits[0][n - 1]
            for i in range(1, n - 1):
                for j in range(max(n - 1 - i, i + 1), n):
                    best = prev[j]
                    if j - 1 >= 0:
                        best = max(best, prev[j - 1])
                    if j + 1 < n:
                        best = max(best, prev[j + 1])
                    curr[j] = best + fruits[i][j]
                prev, curr = curr, prev
            return prev[n - 1]

        ans += dp()

        for i in range(n):
            for j in range(i):
                fruits[i][j], fruits[j][i] = fruits[j][i], fruits[i][j]

        ans += dp()
        return ans

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        length = len(baskets)
        section_length = int(math.sqrt(length))
        sections = (length + section_length - 1) // section_length
        count = 0
        sections_max = [0] * sections
        for i in range(length):
            section = i // section_length
            sections_max[section] = max(sections_max[section], baskets[i])
        for fruit in fruits:
            unset = 1
            for section in range(sections):
                if sections_max[section] < fruit:
                    continue
                choose = 0
                sections_max[section] = 0
                for i in range(section_length):
                    pos = section * section_length + i
                    if pos < length and baskets[pos] >= fruit and not choose:
                        baskets[pos] = 0
                        choose = 1
                    if pos < length:
                        sections_max[section] = max(sections_max[section], baskets[pos])
                unset = 0
                break
            count += unset
        return count

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        count = 0
        length = len(baskets)
        for fruit in fruits:
            unset = 1
            for i in range(length):
                if fruit <= baskets[i]:
                    baskets[i] = 0
                    unset = 0
                    break
            count += unset
        return count

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        start = 0
        max_len = 0
        fruit_count = defaultdict(int)

        for end in range(len(fruits)):
            fruit_count[fruits[end]] += 1

            while len(fruit_count) > 2:
                fruit_count[fruits[start]] -= 1
                if fruit_count[fruits[start]] == 0:
                    del fruit_count[fruits[start]]
                start += 1

            max_len = max(max_len, end - start + 1)

        return max_len

class Solution:
    def modifyString(self, s: str) -> str:
        res = list(s)
        length = len(s)

        for i in range(length):
            char = res[i]
            if char != "?":
                continue
            for char_ascii in string.ascii_lowercase:
                if (
                    (i > 0 and res[i - 1] == char_ascii) 
                    or (i < length - 1 and res[i + 1] == char_ascii)
                ):
                    continue
                res[i] = char_ascii
                break
        return "".join(res)

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        length = len(mat)
        res = 0
        for i in range(length):
            row1, col1 = i, i
            row2, col2 = i, length - i - 1
            res += mat[row1][col1]
            if row2 != row1 or col2 != col1:
                res += mat[row2][col2]
        return res

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        length = len(arr)
        if length < m * k:
            return False
        for i in range(length - m + 1):
            cur_pat = arr[i:i+m]
            count = 1
            for j in range(i + m, length, m):
                if arr[j:j+m] == cur_pat:
                    count += 1
                else:
                    break
            if count >= k:
                return True
        return False

class Solution:
    def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
        start_sector, end_sector = rounds[0], rounds[-1]

        if start_sector <= end_sector:
            return tuple(range(start_sector, end_sector + 1))
            
        return tuple(
            itertools.chain(
                range(1, end_sector + 1),
                range(start_sector, n + 1)
            )
        )

class Solution:
    def thousandSeparator(self, n: int) -> str:
        if n < 1000:
            return str(n)
        res = []
        count = 0
        while n > 0:
            res.append(str(n % 10))
            count += 1
            n //= 10
            if count % 3 == 0 and n > 0:
                res.append(".")
        res.reverse()
        return "".join(res)

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        count = 0
        for num in arr:
            if num % 2 == 0:
                count = 0
            else:
                count += 1
            if count == 3:
                return True
        return False

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        prev = 0
        for num in arr:
            diff = num - prev - 1
            if k > diff:
                k -= diff
            else:
                return prev + k
            prev = num
        return prev + k

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        res = [None] * len(s)
        for i, char in zip(indices, s):
            res[i] = char
        return "".join(res)

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        res = 0
        empty = 0
        while numBottles > 0:
            res += numBottles
            empty += numBottles
            numBottles = empty // numExchange
            empty %= numExchange
        return res

class Solution:
    def reformatDate(self, date: str) -> str:
        day_str, mnth_str, year_str = date.split()
        if len(day_str) == 3:
            day = int(day_str[0:1])
        else:
            day = int(day_str[0:2])
        mnth = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"].index(mnth_str) + 1
        year = int(year_str)
        return f"{year}-{mnth:02}-{day:02}"

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        diff = abs(arr[0] - arr[1])
        for i in range(1, len(arr) - 1):
            if abs(arr[i] - arr[i+1]) != diff:
                return False
        return True

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        stack = deque()
        for i in range(len(prices)):
            price = prices[i]
            while True:
                if not stack:
                    break
                last_i, last_price = stack[-1]
                if last_price >= price:
                    prices[last_i] -= price
                    stack.pop()
                else:
                    break
            stack.append((i, price))
        return prices

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        res = []
        for j in range(n, 2 * n):
            res.extend((nums[j - n], nums[j]))
        return res

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        freqs = defaultdict(int)
        length = len(target)
        if length != len(arr):
            return False
        for i in range(length):
            freqs[target[i]] += 1
            freqs[arr[i]] -= 1
        for count in freqs.values():
            if count != 0:
                return False
        return True

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        for i, word in enumerate(sentence.split()):
            if word.startswith(searchWord):
                return i + 1
        return -1

class Solution:
    def maxPower(self, s: str) -> int:
        prev = s[0]
        count = 1
        max_count= 1
        for char in s[1:]:
            if char == prev:
                count += 1
                max_count = max(max_count, count)
            else:
                count = 1
                prev = char
        return max_count

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        prev = -k - 1
        for i, num in enumerate(nums):
            if num == 0:
                continue
            if i - prev - 1 >= k:
                prev = i
            else:
                return False
        return True

class Solution:
    def reformat(self, s: str) -> str:
        res, digits, al = [""], [], []
        for char in s:
            if char.isalpha():
                al.append(char)
            else:
                digits.append(char)
            while digits and al:
                res.extend((digits.pop(), al.pop()))
        if digits:
            res.append(digits.pop())
        elif al:
            res[0] = al.pop()
        if digits or al:
            return ""
        return "".join(res)

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        min_sum = float('inf')
        cur_sum = 0
        for num in nums:
            cur_sum += num
            min_sum = min(min_sum, cur_sum)
        return max(1 - min_sum, 1)

class Solution:

    class TrieNode:
        def __init__(self):
            # Tracks how many times this substring appears in the Trie.
            self.frequency = 0
            # Maps characters to their respective child nodes.
            self.child_nodes = {}

    def stringMatching(self, words: List[str]) -> List[str]:
        matching_words = []
        root = self.TrieNode()  # Initialize the root of the Trie.

        # Insert all suffixes of each word into the Trie.
        for word in words:
            for start_index in range(len(word)):
                # Insert each suffix starting from index start_index.
                self._insert_word(root, word[start_index:])

        # Check each word to see if it exists as a substring in the Trie.
        for word in words:
            if self._is_substring(root, word):
                matching_words.append(word)

        return matching_words

    def _insert_word(self, root: "TrieNode", word: str) -> None:
        current_node = root
        for char in word:
            if char not in current_node.child_nodes:
                # Create a new node if the character does not exist.
                current_node.child_nodes[char] = self.TrieNode()
            current_node = current_node.child_nodes[char]
            current_node.frequency += 1  # Increment the frequency of the node.

    def _is_substring(self, root: "TrieNode", word: str) -> bool:
        current_node = root
        for char in word:
            # Traverse the Trie following the characters of the word.
            current_node = current_node.child_nodes[char]
        # A word is a substring if its frequency in the Trie is greater than 1.
        return current_node.frequency > 1

class Solution:
    def maxTotalFruits(
        self, fruits: List[List[int]], startPos: int, k: int
    ) -> int:
        n = len(fruits)
        sum_ = [0] * (n + 1)
        indices = [0] * n

        for i in range(n):
            sum_[i + 1] = sum_[i] + fruits[i][1]
            indices[i] = fruits[i][0]

        ans = 0
        for x in range(k // 2 + 1):
            # move left x steps, then right (k - 2x) steps
            y = k - 2 * x
            left = startPos - x
            right = startPos + y
            start = bisect_left(indices, left)
            end = bisect_right(indices, right)
            ans = max(ans, sum_[end] - sum_[start])

            # move right x steps, then left (k - 2x) steps
            y = k - 2 * x
            left = startPos - y
            right = startPos + x
            start = bisect_left(indices, left)
            end = bisect_right(indices, right)
            ans = max(ans, sum_[end] - sum_[start])

        return ans

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        max_sum = sum(nums)
        nums.sort(reverse=True)
        cur_sum = 0
        res = []
        for num in nums:
            cur_sum += num
            res.append(num)
            if cur_sum > max_sum - cur_sum:
                break
        return res

class Solution:
    def countLargestGroup(self, n: int) -> int:
        freqs = defaultdict(int)
        def count(num: int) -> int:
            res = 0
            while num > 0:
                res += num % 10
                num //= 10
            return res
        max_freq = 0
        for i in range(1, n + 1):
            group = count(i)
            freq = freqs[group] + 1
            freqs[group] = freq
            if freq > max_freq:
                max_freq = freq
        res = 0
        for freq in freqs.values():
            if freq == max_freq:
                res += 1
        return res

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        freqs = defaultdict(int)
        for num in arr:
            freqs[num] += 1
        max_num = -1
        for num, freq in freqs.items():
            if num == freq:
                max_num = max(max_num, num)
        return max_num

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        res = []
        for i, num in zip(index, nums):
            res.insert(i, num)
        return res

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        rows = len(matrix)
        cols = len(matrix[0])
        min_row = float("-inf")
        max_col = float("inf")
        for row in range(rows):
            min_row = max(min_row, min(matrix[row]))
        for col in range(cols):
            cur_max_col = float("-inf")
            for row in range(rows):
                cur_max_col = max(cur_max_col, matrix[row][col])
            max_col = min(max_col, cur_max_col)
        if min_row == max_col:
            return [min_row]
        return []

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        rows = len(matrix)
        cols = len(matrix[0])
        min_row = [None] * rows
        max_col = [None] * cols
        for row in range(rows):
            min_row[row] = min(matrix[row])
        for col in range(cols):
            num_max = float("-inf")
            for row in range(rows):
                num = matrix[row][col]
                if num > num_max:
                    num_max = num
            max_col[col] = num_max
        res = []
        for row in range(rows):
            for col in range(cols):
                num = matrix[row][col]
                if num == min_row[row] and num == max_col[col]:
                    res.append(num)
        return res

class Solution:
    def generateTheString(self, n: int) -> str:
        if n % 2 == 0:
            return ("a" * (n - 1)) + "b"
        return "a" * n

class Solution:
    def sortString(self, s: str) -> str:
        freqs = defaultdict(int)
        for char in s:
            freqs[char] += 1
        keys = list(freqs.keys())
        keys.sort(key = ord)
        length = len(keys)
        res = []
        while freqs:
            for i in itertools.chain(range(length), reversed(range(length))):
                key = keys[i]
                if key not in freqs:
                    continue
                res.append(key)
                freqs[key] -= 1
                if freqs[key] == 0:
                    freqs.pop(key)
        return "".join(res)

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        num_to_count = {}
        for i, num in enumerate(sorted(nums)):
            if num not in num_to_count:
                num_to_count[num] = i
        for i in range(len(nums)):
            nums[i] = num_to_count[nums[i]]
        return nums

class Solution:
    def daysBetweenDates(self, date1: str, date2: str) -> int:
        year1, month1, day1 = map(int, date1.split('-'))
        year2, month2, day2 = map(int, date2.split('-'))
        date1 = datetime.date(year1, month1, day1)
        date2 = datetime.date(year2, month2, day2) 
        return abs((date2 - date1).days)

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        enc = set()
        for num in arr:
            if num == 0 and 0 in enc:
                return True
            if num % 2 == 0 and num // 2 in enc:
                return True
            if num * 2 in enc:
                return True
            enc.add(num)
        return False

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == s[::-1]:
            return 1
        return 2

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        num_to_rank = defaultdict(int)
        nums = sorted(set(arr))
        for rank, num in enumerate(nums, 1):
            num_to_rank[num] = rank
        for i in range(len(arr)):
            arr[i] = num_to_rank[arr[i]]
        return arr

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        ind = defaultdict(list)
        for i, num in enumerate(arr):
            ind[num].append(i)
        for rank, num in enumerate(sorted(ind.keys()), 1):
            for i in ind[num]:
                arr[i] = rank
        return arr

class Solution:
    def maximum69Number(self, num: int) -> int:
        digits = []
        while num > 0:
            digits.append(num % 10)
            num //= 10
        digits.reverse()
        res = 0
        enc = False
        length = len(digits)
        for i, digit in enumerate(digits):
            if digit == 6 and not enc:
                digit = 9
                enc = True
            res += (10 ** (length - i - 1)) * digit
        return res

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        if n <= 10:
            return [1, n - 1]
        def check(num: int) -> bool:
            while num > 0:
                if num % 10 == 0:
                    return False
                num //= 10
            return True
        for i in range(1, (n + 1) // 2):
            num1, num2 = i, n - i
            if check(num1) and check(num2):
                return [num1, num2]
        raise Exception

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        res = []
        i = 0
        length = len(nums)
        while i < length:
            freq, val = nums[i], nums[i + 1]
            i += 2
            res.extend((val, ) * freq)
        return res

class Solution:
    def freqAlphabets(self, s: str) -> str:
        res = []
        length = len(s)
        i = 0
        while i < length:
            if i + 2 <  length and s[i + 2] == "#":
                res.append(chr(int(s[i:i+2]) + 97 - 1))
                i += 3
            else:
                res.append(chr(int(s[i]) + 97 - 1))
                i += 1
        return "".join(res)

class Solution:
    def sumZero(self, n: int) -> List[int]:
        if n == 1:
            return [0]
        res = []
        if n % 2 != 0:
            res.append(0)
            n -= 1
        for i in range(1, (n // 2) + 1):
            res.extend((i, -i))
        return res

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        greatest = -1
        for i in reversed(range(len(arr))):
            current = arr[i]
            arr[i] = greatest
            if current > greatest:
                greatest = current
        return arr

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        def count(num: int) -> int:
            res = 0
            while num:
                res += 1
                num //= 10
            return res
        res = 0
        for num in nums:
            if count(num) % 2 == 0:
                res += 1
        return res

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getDecimalValue(self, head: Optional[ListNode]) -> int:
        res = 0
        while head:
            res <<= 1
            res |= head.val
            head = head.next
        return res

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        cols = [[0] * 3 for _ in range(2)]
        rows = [[0] * 3 for _ in range(2)]
        diags = [[0] * 2 for _ in range(2)]
        players = ["A", "B"]
        for i, (row, col) in enumerate(moves):
            if i % 2 == 0:
                player = 0
            else:
                player = 1
            rows[player][row] += 1
            cols[player][col] += 1
            if row == col:
                diags[player][0] += 1
            if row == 2 - col:
                diags[player][1] += 1
        for player in range(2):
            for win in (cols, rows, diags):
                if 3 in win[player]:
                    return players[player]
        if len(moves) == 9:
            return "Draw"
        return "Pending"

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        if not grid or not grid[0]:
            return grid
        
        row_length = len(grid)
        col_length = len(grid[0])
        num_count = row_length * col_length
        k %= num_count
        res = [[0] * col_length for _ in range(row_length)]
        
        for row in range(row_length):
            for col in range(col_length):
                flat_mat_index = (row * col_length) + col
                new_flat_mat_index = (flat_mat_index + k) % num_count
                new_row = new_flat_mat_index // col_length
                new_col = new_flat_mat_index % col_length
                res[new_row][new_col] = grid[row][col]
        return res

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        mat = [[0] * n for _ in range(m)]
        for row, col in indices:
            for cur_col in range(n):
                mat[row][cur_col] += 1
            for cur_row in range(m):
                mat[cur_row][col] += 1
        count = 0
        for row in range(m):
            for col in range(n):
                if mat[row][col] % 2 != 0:
                    count += 1
        return count

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        freq = Counter()
        m = float("inf")
        for b1 in basket1:
            freq[b1] += 1
            m = min(m, b1)
        for b2 in basket2:
            freq[b2] -= 1
            m = min(m, b2)

        merge = []
        for k, c in freq.items():
            if c % 2 != 0:
                return -1
            merge.extend([k] * (abs(c) // 2))

        if not merge:
            return 0
        merge.sort()
        return sum(min(2 * m, x) for x in merge[: len(merge) // 2])

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
        for x3, y3 in coordinates[2:]:
            if (x3 - x1) * (y2 - y1) != (x2 - x1) * (y3 - y1):
                return False
        return True

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        count_l, count_r = 0, 0
        count = 0
        for char in s:
            if char == "R":
                count_r += 1
            else:
                count_l += 1
            if count_l == count_r:
                count += 1
        return count
            

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        length = len(position)
        odd, even = 0, 0
        for pos in position:
            if pos % 2 == 0:
                even += 1
            else:
                odd += 1
        return min(odd, even)

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = float("inf")
        res = []
        for i, num in enumerate(arr[:-1]):
            nxt = arr[i + 1]
            diff = abs(nxt - num)
            if diff < min_diff:
                res.clear()
                res.append((num, nxt))
                min_diff = diff
            elif diff == min_diff:
                res.append((num, nxt))
        return res

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = float("inf")
        diffs = defaultdict(list)
        for i, num in enumerate(arr[:-1]):
            nxt = arr[i + 1]
            diff = abs(nxt - num)
            diffs[diff].append((num, nxt))
            min_diff = min(min_diff, diff)
        return diffs[min_diff]

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = float("inf")
        res = []
        for i, num in enumerate(arr[:-1]):
            nxt = arr[i + 1]
            diff = abs(nxt - num)
            min_diff = min(min_diff, diff)
        for i, num in enumerate(arr[:-1]):
            nxt = arr[i + 1]
            diff = abs(nxt - num)
            if diff == min_diff:
                res.append((num, nxt))
        return res

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        freqs = defaultdict(int)
        for char in text:
            freqs[char] += 1
        res = min(
            freqs["b"],
            freqs["a"],
            freqs["l"] // 2,
            freqs["o"] // 2,
            freqs["n"]
        )
        return res

class Solution:
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        return [
            "Monday", "Tuesday", "Wednesday", 
            "Thursday", "Friday", "Saturday", 
            "Sunday"
        ][datetime.date(year, month, day).weekday()]

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        length = len(distance)
        forward_dist, back_dist = 0, 0
        forward, back = start, start
        while True:
            if forward == destination:
                return forward_dist
            if back == destination or length + back == destination:
                return back_dist
            forward_dist += distance[forward]
            forward = (forward + 1) % length
            back_dist += distance[back - 1]
            back -= 1
        raise Exception

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        prime = [True] * (n + 1)
        prime[0] = prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not prime[i]:
                continue
            for j in range(i * i, n + 1, i):
                prime[j] = False
                    
        prime_count = sum(prime)
        mod = 10**9 + 7
        fact_primes = math.factorial(prime_count)
        fact_norm = math.factorial(n - prime_count)
        return (fact_primes * fact_norm) % mod

        

class Solution:
    def dayOfYear(self, date: str) -> int:
        year, month, day = map(int, date.split('-'))
        days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
            days_in_month[1] = 29
        day_number = sum(days_in_month[:month - 1]) + day
        return day_number

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        freqs = [0] * 100
        res = 0
        for num1, num2 in dominoes:
            if num1 > num2:
                val = num1 * 10 + num2
            else:
                val = num2 * 10 + num1
            res += freqs[val]
            freqs[val] += 1
        return res

class Foo:
    def __init__(self):
        self._lock1 = threading.Lock()
        self._lock2 = threading.Lock()
        self._lock1.acquire()
        self._lock2.acquire()

    def first(self, printFirst: 'Callable[[], None]') -> None:
        printFirst()
        self._lock1.release()


    def second(self, printSecond: 'Callable[[], None]') -> None:
        with self._lock1:
            printSecond()
        self._lock2.release()


    def third(self, printThird: 'Callable[[], None]') -> None:
        with self._lock2:
            printThird()

class Solution:
    def defangIPaddr(self, address: str) -> str:
        return address.replace(".", "[.]")

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        res = [0] * num_people
        i = 0
        while candies > 0:
            loss = min(i + 1, candies)
            res[i % num_people] += loss
            i += 1
            candies -= loss
        return res

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        res = [0] * num_people
        mult = 0
        while candies > 0:
            for i in range(num_people):
                target = min((mult * num_people) + (i + 1), candies)
                if candies > 0: 
                    res[i] += target
                    candies -= target
                else:
                    break
            mult += 1
        return res

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """

        possible_dups = 0
        length_ = len(arr) - 1

        for left in range(length_ + 1):
            if left > length_ - possible_dups:
                break
            if arr[left] == 0:
                if left == length_ - possible_dups:
                    arr[length_] = 0
                    length_ -= 1
                    break
                possible_dups += 1

        last = length_ - possible_dups
        for i in range(last, -1, -1):
            if arr[i] == 0:
                arr[i + possible_dups] = 0
                possible_dups -= 1
                arr[i + possible_dups] = 0
            else:
                arr[i + possible_dups] = arr[i]

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        queue = deque()
        for i in range(len(arr)):
            num = arr[i]
            if queue:
                arr[i] = queue.popleft()
                queue.append(num)
            if num == 0:
                queue.append(0)

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
        words = text.split()
        length = len(words)
        if length < 3:
            return []
        res = []
        i = 0
        while i + 2 < length:
            if words[i] == first and words[i+1] == second:
                res.append(words[i+2])
            i += 1
        return res

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for char in s:
            if stack and char == stack[-1]:
                stack.pop()
            else:
                stack.append(char)
        return "".join(stack)

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        for i, num in enumerate(stones):
            stones[i] = -num
        heapq.heapify(stones)
        while stones:
            last = -heapq.heappop(stones)
            if not stones:
                return last
            prev = -heapq.heappop(stones)
            if last > prev:
                heapq.heappush(stones, -(last - prev))
        return 0