def math!(n: int) -> int:

        return n+1

    def rotate(self, matrix: List[List[int]]) -> None:
        
        # Note:
        # Rotate n x n matrix 90 degrees clockwise in place
        # 1. Process the matrix layer by layer (outermost to innermost)
        # 2. For each layer, rotate elements in four way swaps:
        #       Top -> Right -> Bottom -> Left -> Top
        # 3. Repeat for all layers
        # Result -> No extra matrix allocation, in place modification

        # Example (n=3, outer layer rotation):
        # [1, 2, 3]         [7, 4, 1]
        # [4, 5, 6]   --->  [8, 5, 2]
        # [7, 8, 9]         [9, 6, 3]

        n = len(matrix)

        # There are n//2 layers
        # Odd sized matrix -> one single center cell, inner does not rotate
        # Even sized matrix -> no single center cell, all layers rotate
        layers = n//2

        for layer in range(layers):

            # first -> start index of current ring (top-left corner)
            first = layer

            # last -> end index of current ring (bottom-right corner)

            # layer 1:
            # [ 1, 1, 1, 1, 1, 1]
            # [ 1, 1, 1, 1, 1, 1]
            #     f^.       l^
            # ... 
            # ...
            last = n - 1 - layer

            # length of current ring - 1
            # notice we only need 3 swaps as 4th swap is 1 swap of next switch
            # [1,  2,  3,  4 ]
            # [5,  6,  7,  8 ]
            # [9,  10, 11, 12]
            # [13, 14, 15, 16]
            
            # we only swap, 1, 2, 3, as 4 will be taken care of 
            # by the next iteration, therefore ringLen is -1 its actual length
            # thus ring len of 4 goes to 3
            ringLen = last - first            

            # iterate -> 0 to ringLen-1 
            for i in range(ringLen):

                # left -> top
                # bottom -> left
                # right -> bottom
                # saved top -> right

                # save top
                top_val = matrix[first][first + i]

                # top: left right via row    || left: bottom up via column
                matrix[first][first + i] = matrix[last - i][first]

                # left: bottom up via column ||  bottom: right left via row
                matrix[last - i][first] = matrix[last][last - i]

                # bottom: right left via row ||  right: top down via column
                matrix[last][last - i] = matrix[first + i][last]

                # right: top down via column ||  top: left right via row
                matrix[first + i][last] = top_val

        # overall: time complexity O(n^2)
        # overall: space complexity O(1)

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        
        # Note:
        # Traverse the matrix in clockwise spiral order using layers
        # 1. Treat each layer as a shrinking “frame” around the matrix
        # 2. For each layer, traverse top row, right column, bottom row, left column
        # 3. Increment layer and repeat until all elements are processed

        # Empty check
        if not matrix or not matrix[0]:
            return []

        res = []

        # boundaries
        m, n = len(matrix), len(matrix[0])

        # number of layer -> min between rows and columns
        # There are (min(row, col) // 2) layers
        # Odd sized matrix -> one single center cell
        # Even sized matrix -> no single center cell
        layers = (min(m, n) + 1) // 2

        for layer in range(layers):

            # boundaries of current layer
            first_row = layer
            first_col = layer

            # inclusive via last element

            # layer 1:
            # [ 1, 1, 1, 1, 1, 1]
            # [ 1, 1, 1, 1, 1, 1]
            #     f^.       l^
            # ... 
            # ...
            last_row = m - 1 - layer
            last_col = n - 1 - layer

            # Top and Right sides always exist in every layer
            # Bottom and left may not always exist

            # Top row: left -> right
            for col in range(first_col, last_col + 1):
                res.append(matrix[first_row][col])

            # Right column: top+1 -> bottom
            for row in range(first_row + 1, last_row + 1):
                res.append(matrix[row][last_col])

            # Bottom row: right-1 -> left (if more than one row)
            if last_row > first_row:
                for col in range(last_col - 1, first_col - 1, -1):
                    res.append(matrix[last_row][col])

            # Left column: bottom-1 -> top+1 (if more than one column)
            if last_col > first_col:
                for row in range(last_row - 1, first_row, -1):
                    res.append(matrix[row][first_col])

        # overall: time complexity O(m*n)
        # overall: space complexity O(m*n) for output list
        return res

    def setZeroes(self, matrix: List[List[int]]) -> None:
        
        # Note:
        # Separate iterating from writing via creating copy of matrix using O(m*n)
        # We read over the copy while updating the original in place
        # 1. Iterate through original matrix
        # 2. If cell is 0, set corresponding row and column in copy to 0
        # 3. Copy back to original matrix
        # Result -> original matrix set correctly in place

        m, n = len(matrix), len(matrix[0])
        
        # Create a copy
        copy = [row[:] for row in matrix]  # O(m*n) space

        for i in range(m):
            for j in range(n):
                if copy[i][j] == 0:
                    # Zero entire row
                    for col in range(n):
                        matrix[i][col] = 0
                    # Zero entire column
                    for row in range(m):
                        matrix[row][j] = 0

        # overall: time complexity O(m*n*(m+n)) due to nested zeroing loops
        # overall: space complexity O(m*n) for copy

    def setZeroes(self, matrix: List[List[int]]) -> None:
        
        # Note:
        # Separate iterating from writing via creating copy of matrix using O(m+n)
        # Use two arrays to store flags to track zero rows and zero columns
        # 1. row_flag[m] -> True if row i should be zero
        # 2. col_flag[n] -> True if column j should be zero
        # 3. Iterate matrix, set flags
        # 4. Iterate matrix again, zero out flagged rows and columns
        # Result -> original matrix set correctly in place


        m, n = len(matrix), len(matrix[0])
        row_flag = [False] * m
        col_flag = [False] * n

        # Flag zero rows and columns
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row_flag[i] = True
                    col_flag[j] = True

        # Zero out flagged rows and columns in original matrix
        for i in range(m):
            for j in range(n):
                if row_flag[i] or col_flag[j]:
                    matrix[i][j] = 0

        # overall: time complexity O(m*n)
        # overall: space complexity O(m+n)

    def setZeroes(self, matrix: List[List[int]]) -> None:
        
        # Note:
        # Separate iterating from writing via creating copy of matrix using O(m+n)
        # We use the first row and first column of the matrix itself
        # 1. row_flag[m] -> True if row i should be zero
        # 2. col_flag[n] -> True if column j should be zero
        # 4. Iterate matrix again, zero out flagged rows and columns
        # Result -> original matrix set correctly in place

        # Boundaries
        m, n = len(matrix), len(matrix[0])

        # Pre check if first row has any zeros
        first_row_zero = False
        for j in range(n):
            if matrix[0][j] == 0:
                first_row_zero = True
                break

        # Pre check if first column has any zeros
        first_col_zero = False
        for i in range(m):
            if matrix[i][0] == 0:
                first_col_zero = True
                break

        # Set zero flags using first row and column
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0  # mark row
                    matrix[0][j] = 0  # mark column

        # Using zero flags, zero out rows and cols
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        # Afterwards:
        # Zero out the first row if needed
        if first_row_zero:
            for j in range(n):
                matrix[0][j] = 0

        # Afterwards:
        # Zero out the first column if needed
        if first_col_zero:
            for i in range(m):
                matrix[i][0] = 0

        # overall: time complexity O(m*n)
        # overall: space complexity O(1)

    def isHappy(self, n: int) -> bool:
        
        # Note:
        # 1. Compute sum of squares of digits repeatedly
        # 2. Keep track of numbers seen in a hash set
        # 3. If we see a number again, a cycle exists → not happy
        # 4. If we reach 1, number is happy
        # Result -> Determine if number is happy

        # store numbers to detect cycles
        seen = set()

        # cycle formula
        def next_number(num):
            return sum(int(d) ** 2 for d in str(num))

        while n != 1:

            # cycle detected
            if n in seen:
                return False
            seen.add(n)

            # compute sum of squares of digits
            n = next_number(n)

        # reached 1 = happy number
        res = True

        # overall: time complexity O(log n) (per iteration * number of unique sums)
        # overall: space complexity O(log n) (for hash set)
        return res

    def isHappy(self, n: int) -> bool:
        
        # Note:
        # Treat sum-of-squares transformation as a linked list
        # 2. Slow and fast pointers to detect cycle
        # 3. If fast or fast.next reaches 1 -> happy
        # 4. If slow == fast → cycle exists -> not happy
        # Result -> Determine if number is happy

        # cycle formula
        def next_number(num):
            return sum(int(d) ** 2 for d in str(num))

        # set pointers
        slow = n
        fast = next_number(n)

        # slow and fast pointer to check happy number requirements
        while fast != 1 and slow != fast:
            slow = next_number(slow)
            fast = next_number(next_number(fast))

        # happy number == 1
        res = fast == 1

        # overall: time complexity O(log n) (per iteration * number of iterations before cycle)
        # overall: space complexity O(1)
        return res

    def plusOne(self, digits: List[int]) -> List[int]:
        
        # Note:
        # Process digits from least significant to most significant
        # 1. Iterate right to left in array
        # 2. Add 1 to the last digit
        # 3. Propagate carry if sum >= 10
        # 4. If carry remains after the most significant digit, insert at front
        # 5. Time complexity O(n), space O(1) extra (besides output)

        n = len(digits)

        # iterate from last digit to first
        for i in range(n - 1, -1, -1):
            
            # add to current digit
            digits[i] += 1
            
            # if no carry, finished array, else continue
            if digits[i] < 10:
                return digits

            # if carry, set current to zero, continue
            digits[i] = 0

        # if carry remains after processing all digits
        # prepend [1] to array
        res = [1] + digits

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def myPow(self, x: float, n: int) -> float:
        
        # Note:
        # Math behind Fast Exponentiation:

        # x^n -> even -> [x^(n/2)]^2
        #     -> odd  -> x * (x^[(n-1)/2])^2

        # Example:
        # x^6 = (x^3)^2
        # x^7 = x * (x^3)^2

        # Now simply apply some recursion

        # Note:
        # 1. Recursively compute half power to reduce computation
        # 2. If exponent is negative, use reciprocal: x^-n = 1 / x^n
        # 3. Base case: n == 0 → return 1
        # Result -> pow() calculation

        if n == 0:
            return 1.0
        if n < 0:
            return 1 / self.myPow(x, -n)

        half = self.myPow(x, n // 2)
        
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

        # overall: time complexity O(log n)
        # overall: space complexity O(log n) due to recursion stack

    def myPow(self, x: float, n: int) -> float:
        
        # Note:
        # Binary Exponentiation uses the binary representation of n
        # n = 13 -> 1101

        # Start with result = 1 and current_product = x. 
        # Then for each bit from LSB to MSB:

        # If bit is 1 → multiply result by current_product
        # Square current_product each step
        # Shift to next bit

        # Note:
        # 1. Use binary exponentiation iteratively
        # 2. Convert negative exponent to positive and invert at end
        # 3. Multiply result by x whenever the current bit of n is 1
        # 4. Shift exponent right each iteration

        N = n
        if N < 0:
            x = 1 / x
            N = -N

        result = 1.0
        current_product = x

        while N > 0:
            if N % 2 == 1:  # current bit is 1
                result *= current_product
            current_product *= current_product  # square for next bit
            N //= 2

        # overall: time complexity O(log n)
        # overall: space complexity O(1)
        return result

    def multiply(self, num1: str, num2: str) -> str:
        
        # Note:
        # 1. Multiply each digit of num1 by each digit of num2
        # 2. Store intermediate sums in an array of length len(num1) + len(num2)
        # 3. Handle carry for each position
        # 4. Convert array to string, skipping leading zeros

        # Zero Check
        if num1 == "0" or num2 == "0":
            return "0"

        m, n = len(num1), len(num2)

        # max number of digits the product can have when multiplying two integers
        pos = [0] * (m + n)

        # multiply digits from right to left
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):

                # i -> index of digit in num1 
                # j -> index of digit in num2

                # single digit multiplication
                mul = int(num1[i]) * int(num2[j])

                # stores the carry that will affect the next higher digit
                p1 = i + j

                # stores the ones place for this multiplication
                p2 = i + j + 1

                # pos[p2] holds previous carry that contributes to new multiplication
                total = mul + pos[p2]

                # new current digit
                pos[p2] = total % 10

                # new carry
                pos[p1] += total // 10

        # convert to string, skipping leading zeros
        result = []
        
        # to skip leading zeros in final result
        for p in pos:

            # if result == empty, ensures we haven't added any non-zero digits yet
            # which ensures we only skip leading zeros, not inner zeros
            if not result and p == 0:
                continue

            # append inner zeros or values
            result.append(str(p))

        # more efficient of concatenating strings
        res = "".join(result)

        # overall: time complexity O(m*n)
        # overall: space complexity O(m+n)
        return res

    class DetectSquares:

        def __init__(self):

            # Note:
            # counts[x][y] -> tracks how many times point (x,y) has been added
            # This allows O(1) insertion and O(k) count queries
            self.counts = defaultdict(lambda: defaultdict(int))

        def add(self, point: List[int]) -> None:

            # Increment point count
            x_col, y_row = point
            self.counts[x_col][y_row] += 1

        def count(self, point: List[int]) -> int:
            x_col, y_row = point
            total = 0

            # Look for all points in same column x, but with different y
            for curr_y_row, count_at_point in self.counts[x_col].items():
                if curr_y_row == y_row:  # skip the query point itself
                    continue

                # distance = side length
                d = curr_y_row - y_row

                # Left square
                left_x = x_col - d
                count_left_top = self.counts.get(left_x, {}).get(y_row, 0)
                count_left_bottom = self.counts.get(left_x, {}).get(curr_y_row, 0)
                total += count_at_point * count_left_top * count_left_bottom

                # Right square
                right_x = x_col + d
                count_right_top = self.counts.get(right_x, {}).get(y_row, 0)
                count_right_bottom = self.counts.get(right_x, {}).get(curr_y_row, 0)
                total += count_at_point * count_right_top * count_right_bottom

            return total

        # overall: add O(1), count O(k) where k = # points sharing same x
        # overall: space complexity O(n) for n points stored