منظور از یک عبارت جمع، رشته‌ایست که تعریف بازگشتی زیر را برآورده می‌کند:

• هر حرف کوچک لاتین، یک عبارت جمع است.
• اگر $s$ و $t$ دو عبارت جمع باشند، $(s+t)$ هم یک عبارت جمع است.

بر روی عبارت‌های جمع، دو عمل زیر تعریف می‌شود.

عمل جابجایی در اثر این عمل، عبارت $Xs+tY$ به $Xt+sY$‌تبدیل می‌شود.

عمل شرکت‌پذیری پس از اعمال آن، عبارت‌های $Xs+(t+u)Y$ و $X(s+t)+uY$ به هم تبدیل می‌شوند.

توضیح آن‌که $X$ و $Y$ به نشانه‌ی یک رشته از نویسه‌های «)»، «(»، «+» و «a» تا «z» و همچنین $s$، $t$ و $u$ به نشانه‌ی یک عبارت جمع به کار رفته‌اند.

به عنوان مثال عمل جابه‌جایی می‌تواند عبارت جمع $((a+(c+b))+z)$ را به یکی از عبارت‌های $((a+(b+c))+z)$، $(((c+b)+a)+z)$ و $(z+(a+(c+b)))$ تبدیل کند. همچنین عمل شرکت‌پذیری این عبارت را به یکی از عبارت‌های $(((a+c)+b)+z)$ و $(a+((c+b)+z))$ تبدیل می‌کند.

برنامه‌ای بنویسید که دو عبارت جمع $s$ و $t$ را از ورودی بخواند و رشته‌ای از عبارت‌های جمع به شکل $u_2،u_1،u_0$، …، $u_k$ را بیابد به طوری که $u_0=s$ و $u_k=t$ باشد و به ازای هر $i$ که $k<i \leq 0$، $u_i$ با یکی از تبدیل‌های گفته شده قابل تبدیل به $u_{i+1}$ باشد.

فایل ورودی شامل دو سطر است؛ در سطر نخست $s$ و در سطر بعد $t$ آمده است. فرض کنید طول این دو رشته از ۲۵۵ بیش‌تر نیست. برنامه‌ی شما باید در ظرف حداکثر ۲۰ ثانیه اجرای خود را خاتمه دهد.

فایل خروجی باید شامل $k$ سطر باشد؛ در سطر اول $k$ و در سطر $i+1$ ام $(1\leq i\leq k-1)$ آن $u_i$ را آمده باشد.

• سوال بعد
• سوال قبل