def generate_lucas_sequence(n: int, P: int, Q: int, k: int) ->(int, int, int):
    """
    Generates a Lucas sequence. Used internally for the Lucas primality test.

    References:
        https://docs.sympy.org/latest/_modules/sympy/ntheory/primetest.html#isprime
    """
    D = P ** 2 - 4 * Q
    assert n > 1
    assert k >= 0
    assert D != 0
    if k == 0:
        return 0, 2, Q
    U = 1
    V = P
    Qk = Q
    b = k.bit_length()
    while b > 1:
        U = U * V % n
        V = (V * V - 2 * Qk) % n
        Qk *= Qk
        b -= 1
        if k >> b - 1 & 1:
            U, V = U * P + V, V * P + U * D
            if U & 1:
                U += n
            if V & 1:
                V += n
            U >>= 1
            V >>= 1
            Qk *= Q
        Qk %= n
    return U % n, V % n, Qk
