class Point:

    # Конструктор
    def __init__(self, x, y, curve):
        self.curve = curve
        self.x = x
        self.y = y

    # Копирование точки
    def copy(self):
        return Point(
            curve = self.curve,
            x = self.x,
            y = self.y,
        )

    def show(self):
        if self.isNone():
            return "None"
        return "(0x{:x}, 0x{:x})".format(self.x, self.y)

    def showCoords(self):
        if self.isNone():
            return "None"
        return "({}, {})".format(self.x, self.y)

    # Инициализация новой точки по координатам
    def initXY(self, x, y):
        return Point(
            curve = self.curve,
            x = x,
            y = y
        )

    # Иницуиализация новой точки с неопределенными координатами
    def pointNull(self):
        return Point(
            x = None,
            y = None,
            curve = self.curve
        )

    # Проверка, определена ли точка.
    # ТОчка считается неопределенной, если одна из координат или кривая не определены
    def isNone(self):
        return self.x is None or self.y is None or self.curve is None

    # возвращает координаты x и y
    def coords(self):
        return self.x, self.y

    # Проверка пренадлежности точки к кривой
    def isInCurve(self):
        if self.isNone():
            return False
        x, y = self.coords()
        c = self.curve
        return (y * y - x * x * x - c.a * x - c.b) % c.p == 0

    # Вычисление наклона прямой, проходящей через 2 точки эллиптической кривой
    def getIncline(self, point):
        m = 0
        cur = self.curve
        x1, y1 = self.coords()
        x2, y2 = point.coords()
        if self.x == point.x:
            # точки равны.
            c = self.curve
            m = (3 * x1 * x1 + cur.a) * cur.inverseMod(2 * y1, cur.p)
        else:
            # точки не равны
            m = (y1 - y2) * cur.inverseMod(x1 - x2, cur.p)
        return m

    # Сложение
    def __add__(self, point):
        #assert is_on_curve(point1)
        #assert is_on_curve(point2)
        if self.isNone():
            return point.copy()
        if point.isNone():
            return self.copy()
        if self.x == point.x and self.y != point.y:
            # p + (-p) = 0, симметричная точка
            return self.pointNull()
        # вычисление наклона прямой, прходящей через 2 точки
        m = self.getIncline(point)
        # вычисление результирующих координат
        rx = m * m - self.x - point.x
        ry = self.y + m * (rx - self.x)
        return self.initXY(
            x = rx % self.curve.p,
            y = -ry % self.curve.p, 
        )

    # Унарный -
    def __neg__(self):
        return self.initXY(
            x = self.x,
            y = -self.y % self.curve.p,
        )

    # Сравнение. Точки считаются равны, если они совпадают по оси x
    def __eq__(self, point):
        # Точки считаются равны при совпадении по оси x
        return self.x == point.x

    # Умножение
    def __mul__(self, k):
        #assert is_on_curve(point)
        if self.isNone() or k % self.curve.n == 0:
            return self.pointNull()

        if k < 0:
            # k * point = -k * (-point)
            return -self * -k

        res = self.pointNull()
        addend = self.copy()

        while k:
            if k & 1:
                # Add.
                res = res + addend
            # Double.
            addend = addend + addend
            k >>= 1
        #assert is_on_curve(result)
        return res