يصطف لدى Farmer John عدد $N$ من الأبقار ($2\le N\le 10^3$)، مرقمة $1\ldots N$، لجلسة تصوير. خطط FJ أن تكون البقرة رقم $i$ من اليسار هي ذات الرقم $a_i,$، وكتب التبديل $a_1,a_2,\ldots,a_N$ على ورقة. للأسف سرق Farmer Nhoj الورقة مؤخرًا!

لحسن الحظ، ربما يستطيع FJ استعادة التبديل الذي كتبه. قبل السرقة سجلت Bessie المتتالية $b_1,b_2,\ldots,b_{N-1}$ التي تحقق $b_i=a_i+a_{i+1}$ لكل $1\le i<N.$

بناء على معلومات Bessie، ساعد FJ في استعادة التبديل $a$ «الأصغر معجميًا» الذي قد ينتج $b$. يكون التبديل $x$ أصغر معجميًا من $y$ إذا وجد $j$ بحيث $x_i=y_i$ لكل $i<j$ و$x_j<y_j$ (أي يتطابقان حتى موضع معين، حيث يكون $x$ أصغر من $y$). وجود تبديل $a$ واحد على الأقل مضمون.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $N.$

يحتوي الثاني على $N-1$ أعداد صحيحة $b_1,b_2,\ldots,b_{N-1}.$ مفصولة بمسافات.

الإخراج

سطر واحد فيه $N$ أعداد صحيحة $a_1,a_2,\ldots,a_{N}.$ مفصولة بمسافات.

أمثلة

الإدخال 1

5
4 6 7 6

الإخراج 1

3 1 5 2 4

ملاحظة

ينتج $a$ المتتالية $b$ لأن $3+1=4$ و$1+5=6$ و$5+2=7$ و$2+4=6.$

المهام الفرعية

• تحقق حالات الاختبار $2$–$4$ الشرط $N\le 8.$

• لا توجد قيود إضافية لحالات الاختبار $5$–$10$.

مؤلفا المسألة: Benjamin Qi وChris Zhang