Çətin cihaz#11523

Çətin cihaz

2 saniyə

512 meqabayt

Çox çətin

Sizə iki natural ədəd $d$ və $p$ verilir, burada $p$ sadə ədəddir.

Sizin yaddaş hüceyrələrindən ibarət sirli bir hesablama cihazınız var. Hər bir hüceyrə $0$ -dan $p - 1$ p−1-ə qədər bir ədəd saxlaya bilər. Hesablama cihazı iki əmri dəstəkləyir: toplama və $d$ -ci dərəcəyə yüksəltmə. Hər iki əməliyyat modul $p$ -yə görə yerinə yetirilir.

Yaddaş hüceyrələri $1$ -dən $5000$ -ə qədər nömrələnmişdir. Əvvəlcə $1$ və $2$ hüceyrələri müvafiq olaraq $x$ və $y$ ədədlərini ehtiva edir $(0 \leq x, y \leq p - 1)$ (0 \le x,y \le p−1). Bütün digər hüceyrələr birlərlə doldurulmuşdur.

Sizin $x$ və $y$ dəyərlərinə birbaşa girişiniz yoxdur və onların dəqiq dəyərləri naməlumdur. Sizin vəzifəniz mövcud əmrlərdən istifadə edərək $x y$ mod $p$ hasilini bir hüceyrədə hesablamaqdır. Proqram bütün mümkün $x$ və $y$ üçün işləməlidir.

Toplama əmri iki hüceyrədəki dəyərlərin cəmini hesablayır və nəticəni üçüncü hüceyrəyə yazır. Bu əmr "+ e1 e2 to" kimi yazılır, bu o deməkdir ki, e1 və e2 hüceyrələrindəki dəyərlərin cəmi to hüceyrəsinə yazılacaq. e1, e2, to nömrələri üst-üstə düşə bilər.

İkinci əmr bir hüceyrədəki ədədin $d$ -ci dərəcəsini hesablayır və nəticəni başqa bir hüceyrəyə yazır. Bu əmr "^ e to" kimi yazılır. e və to dəyərləri üst-üstə düşə bilər, bu halda hüceyrədəki dəyər yenidən yazılacaq.

Sonuncu əmr xüsusi bir qaytarma əmri olub, "f target" kimi yazılır. Bu, $x y$ mod $p$ nəticəsinin target hüceyrəsində əldə edildiyini bildirir. Bu əmr sonuncu olmalıdır.

$x y$ mod $p$ -ni hesablayan və $5000$ -dən çox olmayan əmrlərdən (qaytarma əmri daxil olmaqla) istifadə edən əmrlər ardıcıllığını tapın.

Verilən məhdudiyyətlər daxilində həllin mövcudluğu təmin edilir.

Giriş

Yeganə sətir $d$ və $p$ ədədlərini ehtiva edir, boşluqla ayrılmış $(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 sadə $)$ .

Çıxış

Əmrlər ardıcıllığını hər sətirdə bir əmr olmaqla çıxarın. Proqram $5000$ sətirdən çox olmamalıdır. Sonuncu əmr qaytarma əmri olmalıdır.

Nümunələr

Bu məsələdə şərtdə testlər yoxdur. Aşağıda çıxış nümunəsi verilmişdir. Qeyd edək ki, bu çıxış heç bir test üçün həll deyil və yalnız çıxış formatını nümayiş etdirmək üçündür.

Aşağıda proqramın işinin addım-addım təsviri verilmişdir:

hüceyrə 1	hüceyrə 2	hüceyrə 3
başlanğıcda	$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

Tutaq ki, $d = 2$ d=2 və $p = 3$ p=3. $x = 0$ x=0 və $y = 1$ y=1 olduqda qaytarılan nəticə $1 \neq = 0 \cdot 1$ 1 \ne 0 \cdot 1 mod $3$ olduğuna görə, proqram səhv qiymətləndirildi.