Складний пристрій#11523

Складний пристрій

2 секунди

512 мегабайтів

Дуже складна

Вам дано два натуральних числа $d$ і $p$ , де $p$ є простим числом.

У вас є загадковий обчислювач, що містить комірки пам'яті. Кожна комірка може зберігати число від $0$ до $p - 1$ p−1. Обчислювач підтримує дві інструкції: додавання і піднесення до степеня $d$ . Обидві операції виконуються за модулем $p$ .

Комірки пам'яті пронумеровані від $1$ до $5000$ . Спочатку комірки $1$ і $2$ містять числа $x$ і $y$ відповідно $(0 \leq x, y \leq p - 1)$ (0 \le x,y \le p−1). Усі інші комірки заповнені одиницями.

Ви не маєте прямого доступу до значень $x$ і $y$ , і їх точні значення невідомі. Ваше завдання — написати програму, яка, використовуючи доступні інструкції, обчислює добуток $x y$ за модулем $p$ в одній з комірок. Програма повинна працювати для всіх можливих $x$ і $y$ .

Інструкція додавання обчислює суму значень у двох комірках і записує результат у третю. Ця інструкція записується як "+ e1 e2 to", що означає, що сума значень у комірках e1 і e2 буде записана в комірку to. Будь-які з номерів e1, e2, to можуть збігатися.

Друга інструкція обчислює $d$ -ту степінь числа в комірці і записує результат в іншу комірку. Ця інструкція записується як "^ e to". Значення e і to можуть збігатися, у цьому випадку значення в комірці буде перезаписано.

Остання інструкція — це спеціальна інструкція повернення, яка записується як "f target". Це означає, що результат $x y$ mod $p$ отримано в комірці target. Ця інструкція повинна бути останньою.

Знайдіть послідовність інструкцій, яка обчислює $x y$ mod $p$ і використовує не більше $5000$ інструкцій (включаючи інструкцію повернення).

Гарантовано, що за даних обмежень рішення існує.

Вхідні дані

Єдиний рядок містить числа $d$ і $p$ , розділені пробілом $(2 \leq d \leq 10, d < p, 3 \leq p \leq 1 0^{9} + 9, p$ (2 \le d \le 10,~ d \lt p,~ 3 \le p \le 10^9 + 9,~ p просте $)$ .

Вихідні дані

Виведіть послідовність інструкцій, по одній інструкції в рядку. Програма повинна містити не більше $5000$ рядків. Остання інструкція повинна бути інструкцією повернення.

Приклади

У цій задачі відсутні тести з умови. Приклад виводу наведено нижче. Зверніть увагу, що цей вивід не є рішенням ні для якого тесту, і потрібен лише для того, щоб продемонструвати формат виводу.

Нижче наведено покроковий опис роботи програми:

комірка 1	комірка 2	комірка 3
початково	$x$	$y$	$1$
`+ 1 1 3`	$x$	$y$	$2 x$
`^ 3 3`	$x$	$y$	$(2 x)^{d}$ (2x)^d
`+ 3 2 2`	$x$	$y + (2 x)^{d}$ y+(2x)^d	$(2 x)^{d}$ (2x)^d
`+ 3 2 3`	$x$	$y + (2 x)^{d}$ y+(2x)^d	$y + 2 \cdot (2 x)^{d}$ y+2 \cdot (2x)^d
`^ 3 1`	$(y + 2 \cdot (2 x)^{d})^{d}$ (y+2 \cdot (2x)^d)^d	$y + (2 x)^{d}$ y+(2x)^d	$y + 2 \cdot (2 x)^{d}$ y+2 \cdot (2x)^d

Нехай $d = 2$ d=2 і $p = 3$ p=3. Оскільки при $x = 0$ x=0 і $y = 1$ y=1 повернений результат дорівнює $1 \neq = 0 \cdot 1$ 1 \ne 0 \cdot 1 mod $3$ , програма була оцінена як невірна.