


def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list[list[int]]							):
     if len(SCREAMING_SNAKE_CASE__							) == 0 or not all(len(SCREAMING_SNAKE_CASE__							) == 2 for pair in coordinates							):
          raise ValueError('The program cannot work out a fitting polynomial.'							)

     if len({tuple(SCREAMING_SNAKE_CASE__							) for pair in coordinates}							) != len(SCREAMING_SNAKE_CASE__							):
          raise ValueError('The program cannot work out a fitting polynomial.'							)

     __UpperCamelCase       				={x for x, _ in coordinates}
     if len(SCREAMING_SNAKE_CASE__							) == 1:
          return F'x={coordinates[0][0]}'

     if len(SCREAMING_SNAKE_CASE__							) != len(SCREAMING_SNAKE_CASE__							):
          raise ValueError('The program cannot work out a fitting polynomial.'							)

     __UpperCamelCase       				=len(SCREAMING_SNAKE_CASE__							)

     __UpperCamelCase       				=0
     __UpperCamelCase       				=[]
     # put the x and x to the power values in a matrix
     while count_of_line < x:
          __UpperCamelCase       				=0
          __UpperCamelCase       				=coordinates[count_of_line][0]
          __UpperCamelCase       				=[]
          while count_in_line < x:
               count_line.append(a ** (x - (count_in_line + 1))							)
               count_in_line += 1
          matrix.append(SCREAMING_SNAKE_CASE__							)
          count_of_line += 1

     __UpperCamelCase       				=0
     # put the y values into a vector
     __UpperCamelCase       				=[]
     while count_of_line < x:
          vector.append(coordinates[count_of_line][1]							)
          count_of_line += 1

     __UpperCamelCase       				=0

     while count < x:
          __UpperCamelCase       				=0
          while zahlen < x:
               if count == zahlen:
                    zahlen += 1
               if zahlen == x:
                    break
               __UpperCamelCase       				=matrix[zahlen][count] / matrix[count][count]
               for counting_columns, item in enumerate(matrix[count]							):
                    # manipulating all the values in the matrix
                    matrix[zahlen][counting_columns] -= item * bruch
               # manipulating the values in the vector
               vector[zahlen] -= vector[count] * bruch
               zahlen += 1
          count += 1

     __UpperCamelCase       				=0
     # make solutions
     __UpperCamelCase       				=[]
     while count < x:
          solution.append(str(vector[count] / matrix[count][count]							)							)
          count += 1

     __UpperCamelCase       				=0
     __UpperCamelCase       				='f(x)='

     while count < x:
          __UpperCamelCase       				=solution[count].split('E'							)
          if len(SCREAMING_SNAKE_CASE__							) > 1:
               __UpperCamelCase       				=F'{remove_e[0]}*10^{remove_e[1]}'
          solved += F'x^{x - (count + 1)}*{solution[count]}'
          if count + 1 != x:
               solved += "+"
          count += 1

     return solved


if __name__ == "__main__":
   print(points_to_polynomial([]))
   print(points_to_polynomial([[]]))
   print(points_to_polynomial([[1, 0], [2, 0], [3, 0]]))
   print(points_to_polynomial([[1, 1], [2, 1], [3, 1]]))
   print(points_to_polynomial([[1, 3], [2, 3], [3, 3]]))
   print(points_to_polynomial([[1, 1], [2, 2], [3, 3]]))
   print(points_to_polynomial([[1, 1], [2, 4], [3, 9]]))
   print(points_to_polynomial([[1, 3], [2, 6], [3, 11]]))
   print(points_to_polynomial([[1, -3], [2, -6], [3, -11]]))
   print(points_to_polynomial([[1, 5], [2, 2], [3, 9]]))









def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   list     ,	SCREAMING_SNAKE_CASE__     :   int     ,	SCREAMING_SNAKE_CASE__     :   int     ,	SCREAMING_SNAKE_CASE__     :   int							):
     __UpperCamelCase       				=int((lower_bound + upper_bound) // 2							)
     if array[r] == value:
          return r
     if lower_bound >= upper_bound:
          return -1
     if array[r] < value:
          return binary_search(SCREAMING_SNAKE_CASE__     ,	r + 1     ,	SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__							)
     else:
          return binary_search(SCREAMING_SNAKE_CASE__     ,	SCREAMING_SNAKE_CASE__     ,	r - 1     ,	SCREAMING_SNAKE_CASE__							)

def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   int     ,	SCREAMING_SNAKE_CASE__     :   list							):
     __UpperCamelCase       				=0
     if matrix[index][0] == value:
          return [index, 0]
     while index < len(SCREAMING_SNAKE_CASE__							) and matrix[index][0] < value:
          __UpperCamelCase       				=binary_search(matrix[index]     ,	0     ,	len(matrix[index]							) - 1     ,	SCREAMING_SNAKE_CASE__							)
          if r != -1:
               return [index, r]
          index += 1
     return [-1, -1]


if __name__ == "__main__":
   import doctest

   doctest.testmod()





