{
    "allowed_reference_expressions_for_hint": [
        {
            "allowed_expressions": [],
            "hint_lines": [
                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift = 128)",
                "div = pack(ids.div, num_bits_shift = 128)",
                "quotient, remainder = divmod(a, div)",
                "",
                "quotient_split = split(quotient, num_bits_shift=128, length=3)",
                "assert len(quotient_split) == 3",
                "",
                "ids.quotient.d0 = quotient_split[0]",
                "ids.quotient.d1 = quotient_split[1]",
                "ids.quotient.d2 = quotient_split[2]",
                "",
                "remainder_split = split(remainder, num_bits_shift=128, length=3)",
                "ids.remainder.d0 = remainder_split[0]",
                "ids.remainder.d1 = remainder_split[1]",
                "ids.remainder.d2 = remainder_split[2]"
            ]
        },
        {
            "allowed_expressions": [],
            "hint_lines": [
                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift = 128)",
                "b = pack(ids.b, num_bits_shift = 128)",
                "p = pack(ids.p, num_bits_shift = 128)",
                "",
                "res = (a - b) % p",
                "",
                "",
                "res_split = split(res, num_bits_shift=128, length=3)",
                "",
                "ids.res.d0 = res_split[0]",
                "ids.res.d1 = res_split[1]",
                "ids.res.d2 = res_split[2]"
            ]
        },
        {
            "allowed_expressions": [],
            "hint_lines": [
                "from starkware.python.math_utils import div_mod",
                "",
                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift = 128)",
                "b = pack(ids.b, num_bits_shift = 128)",
                "p = pack(ids.p, num_bits_shift = 128)",
                "# For python3.8 and above the modular inverse can be computed as follows:",
                "# b_inverse_mod_p = pow(b, -1, p)",
                "# Instead we use the python3.7-friendly function div_mod from starkware.python.math_utils",
                "b_inverse_mod_p = div_mod(1, b, p)",
                "",
                "",
                "b_inverse_mod_p_split = split(b_inverse_mod_p, num_bits_shift=128, length=3)",
                "",
                "ids.b_inverse_mod_p.d0 = b_inverse_mod_p_split[0]",
                "ids.b_inverse_mod_p.d1 = b_inverse_mod_p_split[1]",
                "ids.b_inverse_mod_p.d2 = b_inverse_mod_p_split[2]"
            ]
        },
        {
            "allowed_expressions": [],
            "hint_lines": [
                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift ",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "    ",
                "def pack_extended(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2, z.d3, z.d4, z.d5)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack_extended(ids.a, num_bits_shift = 128)",
                "div = pack(ids.div, num_bits_shift = 128)",
                "",
                "quotient, remainder = divmod(a, div)",
                "",
                "quotient_split = split(quotient, num_bits_shift=128, length=6)",
                "",
                "ids.quotient.d0 = quotient_split[0]",
                "ids.quotient.d1 = quotient_split[1]",
                "ids.quotient.d2 = quotient_split[2]",
                "ids.quotient.d3 = quotient_split[3]",
                "ids.quotient.d4 = quotient_split[4]",
                "ids.quotient.d5 = quotient_split[5]",
                "",
                "remainder_split = split(remainder, num_bits_shift=128, length=3)",
                "ids.remainder.d0 = remainder_split[0]",
                "ids.remainder.d1 = remainder_split[1]",
                "ids.remainder.d2 = remainder_split[2]"
            ]
        },
        {
            "allowed_expressions": [],
            "hint_lines": [
                "from starkware.python.math_utils import isqrt",
                "",
                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift=128)",
                "root = isqrt(a)",
                "assert 0 <= root < 2 ** 192",
                "root_split = split(root, num_bits_shift=128, length=3)",
                "ids.root.d0 = root_split[0]",
                "ids.root.d1 = root_split[1]",
                "ids.root.d2 = root_split[2]"
            ]
        },
        {
            "allowed_expressions": [],
            "hint_lines": [
                "memory[ap] = 1 if 0 <= (ids.a.d2 % PRIME) < 2 ** 127 else 0"
            ]
        },
        {
            "allowed_expressions": [],
            "hint_lines": [
                "sum_d0 = ids.a.d0 + ids.b.d0",
                "ids.carry_d0 = 1 if sum_d0 >= ids.SHIFT else 0",
                "sum_d1 = ids.a.d1 + ids.b.d1 + ids.carry_d0",
                "ids.carry_d1 = 1 if sum_d1 >= ids.SHIFT else 0",
                "sum_d2 = ids.a.d2 + ids.b.d2 + ids.carry_d1",
                "ids.carry_d2 = 1 if sum_d2 >= ids.SHIFT else 0"
            ]
        },
        {
            "allowed_expressions": [],
            "hint_lines": [
                "from starkware.python.math_utils import is_quad_residue, sqrt",
                "",
                "def split(num: int, num_bits_shift: int = 128, length: int = 3):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int = 128) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "",
                "generator = pack(ids.generator)",
                "x = pack(ids.x)",
                "p = pack(ids.p)",
                "",
                "success_x = is_quad_residue(x, p)",
                "root_x = sqrt(x, p) if success_x else None",
                "",
                "success_gx = is_quad_residue(generator*x, p)",
                "root_gx = sqrt(generator*x, p) if success_gx else None",
                "",
                "# Check that one is 0 and the other is 1",
                "if x != 0:",
                "    assert success_x + success_gx ==1",
                "",
                "# `None` means that no root was found, but we need to transform these into a felt no matter what",
                "if root_x == None:",
                "    root_x = 0",
                "if root_gx == None:",
                "    root_gx = 0",
                "ids.success_x = int(success_x)",
                "ids.success_gx = int(success_gx)",
                "split_root_x = split(root_x)",
                "split_root_gx = split(root_gx)",
                "ids.sqrt_x.d0 = split_root_x[0]",
                "ids.sqrt_x.d1 = split_root_x[1]",
                "ids.sqrt_x.d2 = split_root_x[2]",
                "ids.sqrt_gx.d0 = split_root_gx[0]",
                "ids.sqrt_gx.d1 = split_root_gx[1]",
                "ids.sqrt_gx.d2 = split_root_gx[2]"
            ]
        }
    ]
}
