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

Обмеження на час виконання 2 секунди

Обмеження на використання пам'яті 512 мегабайтів

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

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

Комірки пам'яті пронумеровані від $1$ до $5000$ . Спочатку комірки $1$ і $2$ містять числа $x$ і $y$ відповідно $(0 \leq x, y \leq 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$ просте $)$ .

Вихідні дані

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

Приклади

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

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

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

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

Відправки 22

Коефіцієнт прийняття 50%