+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *سلیب* یک فایل $m$ بایتی روی هاردش دارد. او می‌خواهد **حجم تقریبی** این فایل را به روشی «خوانا برای انسان» نمایش دهد. هر نمایش «خوانا برای انسان» به فرم «`U`$n$» است. که از دو قسمت: + «عدد» که با $n$ نمایش داده شد، یک عدد صحیح در بازه‌ی $[1, 1023]$ (شامل ۱ و ۱۰۲۳) است. + «یکا» که با `U` نمایش داده شد، یک رشته از حروف کوچک و بزرگ انگلیسی است و برابر `B`، `KiB` یا `MiB` است. برای مثال، نمایش `37MiB` یک نمایش «خوانا برای انسان» است. که قسمت «عدد» `37` و قسمت «یکا» `MiB` است. ولی `12byte` (چون `byte` جزو کلمات مجاز نیست.) یا `40000KiB` (عدد بیشتر از ۱۰۲۳ است.) «خوانا برای انسان» نیست. همچنین می‌دانیم که: + هر `1KiB` معادل `1024B` است. + هر `1MiB` معادل `1024KiB` است.  توجه کنید همیشه نمی‌توانیم مقدار دقیق حجم یک فایل را به روش «خوانا برای انسان» نمایش دهیم و گاهی مجبور می‌شویم مقدار آن را تقریب بزنیم. **از شما می‌خواهیم در تقریب زدن، همواره رو به پایین گرد کنید.** برای بهتر متوجه شدن این موضوع به مثال‌ها توجه کنید. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $T$ داده می‌شود که نشان‌دهنده‌ی تعداد تست‌کیس‌ها است. $$1 \leq T \leq 100$$ در $T$ سطر بعدی، در هر سطر یک عدد مثل $m$ داده می‌شود که نشان‌دهنده‌ی ظرفیت فایل *سلیب* است. $$1 \leq m \leq 10^9$$ # خروجی خروجی $t$ سطر دارد. در هر سطر حجم فایل مربوط به آن تست را به روش «خوانا برای انسان» چاپ کنید. **توجه کنید سیستم داوری نسبت به بزرگ و کوچک بودن حروف حساس است.** **با توجه به محدودیت‌های سوال، می‌توان ثابت کرد همواره پاسخ مسئله موجود و یکتا است.** # مثال‌ها ## ورودی نمونه ۱ ``` 3 29 1401 14510629 ``` ## خروجی نمونه ۱ ``` 29B 1KiB 13MiB ``` ---------- **تست اول.** ظرفیت فایل ۲۹ بایت است. بنابراین نمایش «خوانا برای انسان» آن به صورت `29B` است. ---------- **تست دوم.** ظرفیت فایل ۱۴۰۱ بایت است. باتوجه به اینکه «عدد» در نمایش «خوانا برای انسان» باید در بازه‌ی ۱ تا ۱۰۲۳ باشد، نمایش `1401B` یا `0MiB` درست نیست و نمایش درست `1KiB` است. ---------- **تست سوم.** ظرفیت فایل ۱۴۵۱۰۶۲۹ است. با توجه به محدودیت «عدد» در نمایش «خوانا برای انسان» باید از یکای `MiB` استفاده کنیم. نزدیک‌ترین عدد ۱۳.۸ است ولی باید ظرفیت یک عدد صحیح و مثبت باشد و چون باید رو به پایین تقریب بزنیم `13MiB` را انتخاب می‌کنیم.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *گز* یک شهر نامتناهی است. خیابان‌های این شهر به صورت زیر است.  خیابان‌های این شهر را می‌توان روی صفحه مختصات دو بعدی به صورت زیر معرفی کرد. + یک خیابان افقی منطبق بر محور $x$ها است. + یک خیابان عمودی منطبق بر محور $y$ها است. + به ازای هر عدد طبیعی مانند $n$، یک خیابان دایره‌ای به شعاع $n$ و مرکز مختصات وجود دارد. می‌دانیم *سعید* در تقاطعی با مختصات $(x_1, y_1)$ و *سجاد* در تقاطعی با مختصات $(x_2, y_2)$ است. *سعید* می‌خواهد بداند کمترین فاصله‌ای که باید در خیابان‌های گز طی کند تا به *سجاد* برسد چقدر است. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $T$ آمده است که تعداد تست‌های ورودی را نشان می‌دهد. $$1 \leq T \leq 100$$ در سطر اول هر، چهار عدد صحیح $x_1$، $y_1$، $x_2$ و $y_2$ که با یک فاصله از هم جدا شده‌اند، آمده است؛ که نشان‌دهنده‌ی مختصات تقاطع هایی است که *سعید* و *سجاد* در آن قرار دارند. $$-10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9$$ **تضمین می‌شود که $(x_1, y_1)$ و $(x_2, y_2)$ مختصات دو تقاطع در شهر *گز* باشند.** # خروجی خروجی $t$ سطر دارد. در هر سطر، کمترین مسافتی که باید *سعید* طی کند تا به *سجاد* برسد را چاپ کنید. **باتوجه به اینکه پاسخ شما ممکن است عددی اعشاری باشد، زمانی عدد خروجی شما نمره کامل را دریافت می‌کند که با دقت حداقل ۳ رقم بعد از اعشار، پاسخ شما دقیق باشد.** # مثال‌ها ## ورودی نمونه ۱ ``` 4 2 0 -4 0 0 3 5 0 0 -7 0 0 0 -5 0 -5 ``` ## خروجی نمونه ۱ ``` 6.000000000000 6.712388980385 7.000000000000 0.000000000000 ``` ---------- **شکل تست اول.** کوتاه‌ترین مسیر بین این دو تقاطع با یک جاده به شکل یک خط مستقیم است. $$\sqrt{(2 - (-4))^2 + (0 - 0)^2} = 6$$  ---------- **شکل تست دوم.** کوتاه‌ترین مسیر بین این دو تقاطع با رنگ آبی مشخص شده است و طول آن برابر است با: $$\frac{1}{4} \times (2\pi \times 3) + \sqrt{(5 - 3)^2 + (0 - 0)^2} = \frac{3\pi}{2} + 2 \approx 6.712388980385$$  ---------- **شکل تست سوم.** کوتاه‌ترین مسیر بین این دو تقاطع با یک جاده به شکل یک خط مستقیم است. توجه کنید که مرکز شهر هم می‌تواند یک تقاطع باشد. $$\sqrt{(-7 - 0)^2 + (0 - 0)^2} = 7$$  ---------- **شکل تست چهارم.** کوتاه‌ترین مسیر بین این دو تقاطع صفر در نظر گرفته می‌شود. چون این دو تقاطع برهم منطبق هستند. $$0$$ 

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *کشی* $n$ رشته باینری به طول $m$ دارد. در هر عملیات می‌تواند یکی از این رشته‌ها را انتخاب کرده و پیشوندی از آن را برعکس کند. (کاراکترهای `0` را به `1` و `1` را به `0` تبدیل کنیم.)  او می‌خواهد همه این رشته‌ها را باهم برابر کند. شما باید برای $T$ سناریوی مختلف، کمترین عملیات لازم برای رسیدن به این هدف را پیدا کنید. # ورودی در سطر اول ورودی عدد صحیح و مثبت $T$ آمده است که نشان دهنده‌ی تعداد سناریو هایی است که شما باید به آنها پاسخ دهید. $$1 \leq T \leq 1000$$ در سطر اول هر سناریو، دو عدد صحیح و مثبت $n$ و $m$ که با یک فاصله از هم جدا شده‌اند؛ آمده است. $$1 \leq n \cdot m \leq 100 \, 000$$ در $n$ سطر بعدی هر سناریو، در هر سطر یک رشته به طول $m$ آمده است. تضمین می‌شود جمع تعداد کاراکترهای رشته‌ها از $100 \, 000$ بیشتر نمی‌شود. # خروجی خروجی برنامه شامل $T$ خط است که در خط $i$ام باید یک عدد صحیح و مثبت که برابر کمترین تعداد عملیات لازم برای برابر کردن همه‌ی رشته‌ها در سناریوی $i$ام است را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 1 0 2 2 01 10 4 5 01010 00101 11000 00110 ``` ## خروجی نمونه ۱ ``` 0 1 5 ``` **تست اول.** تنها یک رشته داریم، پس نیازی به انجام عملیات نیست. بنابراین پاسخ مسئله برابر ۰ خواهد بود. ---------- **تست دوم.** می‌توانیم به ترتیب علمیات‌های زیر را انجام دهیم. $$ \begin{array}{cc} 01 & \rightarrow & {\bf 10} \\ 10 & & 10 \\ \end{array} $$ بنابراین پاسخ مسئله برابر ۱ خواهد بود. ---------- **تست سوم.** می‌توانیم به ترتیب عملیات‌های زیر را انجام می‌دهیم. $$ \begin{array}{cccc} 01010 & & 01010 & & 01010 & & 01010 & & 01010 & & {\bf1}1010\\ 00101 & \rightarrow & {\bf11010} & \rightarrow & 11010 & \rightarrow & 11010 & \rightarrow & 11010 & \rightarrow & 11010\\ 11000 & & 11000 & & {\bf0011}0 & & {\bf110}10 & & 11010 & & 11010\\ 00110 & & 00110 & & 00110 & & 00110 & & {\bf110}10 & & 11010\\ \end{array} $$ بنابراین پاسخ مسئله برابر ۵ خواهد بود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در گذشته‌ای نه چندان دور $n$ کشور داشتیم که یکی از آن‌ها آلمان نازی بود و به رهبری هیتلر به دنبال فتح جهان بودند. برای راحتی، کشورها و روابط بین آن‌ها را به شکل گرافی $n$ راسی و $m$ یالی نشان می‌دهیم که راس‌ها نشان دهنده‌ی کشور‌ها و یال‌ها نشان دهنده‌ی همسایگی دو طرفه بین کشورها است. در ابتدا کشور $i$ام قدرت $a_i$ را دارد و یکی از آن‌ها آلمان نازی است. هیتلر در جهت کشورگشایی هر بار می‌تواند یک کشور جدید که حداقل یکی از همسایه‌هایش فتح شده را انتخاب کند، و اگر قدرت آلمان نازی بیشتر اکید از آن بود، آن کشور را فتح کند. پس از فتح یک کشور، به اندازه‌ی قدرت آن کشور، به قدرت آلمان نازی اضافه می‌شود.  سوالی که آن زمان فکر سیاست مداران را به خود درگیر کرده بود، این بود که آیا هیتلر می‌تواند موفق شود همه‌ی کشورها را فتح کند یا خیر؟ و اگر نمی‌تواند، حداقل چه مقدار باید قدرت آلمان نازی افزایش یابد تا بتواند به این هدف برسد؟ اما از آن‌جایی که هیتلر مخفی است و مکان اولیه آلمان نازی را نمی‌دانیم، شما باید به ازای هر کشور، این مقدار را محاسبه کنید! # ورودی در سطر اول ورودی، دو عدد $n$ و $m$ به ترتیب نشان‌دهنده‌ی تعداد کشورها و تعداد روابط همسایگی بین کشورها می‌آیند. $$ 1 \le n \le 1933, \quad\quad n-1 \le m \le 1945 $$ در سطر دوم ورودی، اعداد $a_1, a_2, \dots, a_n \,$ که قدرت کشورها را نشان می‌دهند، می‌آیند. $$ 1 \le a_i \le 10^9 $$ در هر کدام از $m$ سطر بعدی، دو عدد $v$ و $u$ می‌آیند که نشان دهنده‌ی یالی بین راس $v$ام و راس $u$ام است. $$ 1 \le v, u \le n, \quad\quad v \neq u $$ **تضمین می‌شود گراف داده شده همبند باشد.** # خروجی در تنها سطر خروجی، باید $n$ عدد با فاصله از هم چاپ کنید که عدد $i$ام حداقل مقداری است که باید به کشور $i$ام **اضافه** کنیم تا در صورتی که آلمان نازی این کشور باشد، بتواند همه‌ی کشورها را فتح کند. (ممکن است این مقدار $0$ باشد.) # مثال‌ها ## ورودی نمونه ۱ ``` 3 2 1 2 3 1 2 2 3 ``` ## خروجی نمونه ۱ ``` 2 1 0 ```  اگر مکان اولیه آلمان نازی: + کشور ۱ باشد و با قدرت $3$ شروع به کار کند، ابتدا می تواند کشور ۲ را فتح کند تا قدرتش $5$ شود. سپس می‌تواند کشور ۳ را فتح کند و به هدفش برسد. بنابراین باید حداقل $2$ واحد به قدرتش اضافه کند. + کشور ۲ باشد و با قدرت $3$ شروع به کار کند، ابتدا می تواند کشور ۱ را فتح کند تا قدرتش $4$ شود. سپس می‌تواند کشور ۳ را فتح کند و به هدفش برسد. بنابراین باید حداقل $1$ واحد به قدرتش اضافه کند. + کشور ۳ باشد و با قدرت $3$ شروع به کار کند، ابتدا می تواند کشور ۲ را فتح کند تا قدرتش $5$ شود. سپس می‌تواند کشور ۱ را فتح کند و به هدفش برسد. می‌توان نشان داد اگر با قدرتی کمتر از این مقدار شروع کند، نمی‌تواند به هدفش برسد. ## ورودی نمونه ۲ ``` 7 10 16 1 32 256 4 128 64 2 6 6 7 1 2 3 7 5 4 7 5 6 2 4 2 4 6 6 3 ``` ## خروجی نمونه ۲ ``` 112 112 33 0 61 12 29 ```  اگر مکان اولیه آلمان نازی: + کشور ۱ باشد و با قدرت $128$ شروع به کار کند، ابتدا می‌تواند کشور ۲ را فتح کند تا قدرتش $129$ شود. سپس می‌تواند کشور ۶ را فتح کند تا قدرتش $257$ شود. اکنون می‌تواند به ترتیب کشورهای ۳، ۴، ۵ و ۷ را فتح کند و به هدفش برسد. بنابراین باید حداقل $112$ واحد به قدرتش اضافه کند. + کشور ۲ باشد و با قدرت $128$ شروع به کار کند، ابتدا می‌تواند کشور ۱ را فتح کند تا قدرتش $129$ شود. سپس همان روال کشور ۱ را می‌توان ادامه داد. + کشور ۳ باشد و با قدرت $65$ شروع به کار کند، ابتدا می‌تواند کشور ۷ را فتح کند تا قدرتش $129$ شود. اکنون می‌تواند به ترتیب کشور ۶، ۵، ۴، ۲ و ۱ را فتح کند و به هدفش برسد. + کشور ۴ باشد و با قدرت $256$ شروع به کار کند، می‌تواند به ترتیب کشورهای ۲، ۱، ۵، ۶، ۳ و ۷ را فتح کند و به هدفش برسد. + کشور ۵ باشد و با قدرت $65$ شروع به کار کند، ابتدا می‌تواند کشور ۷ را فتح کند تا قدرتش $129$ شود. سپس می‌تواند کشور ۶ را فتح کند تا قدرتش $257$ شود. سپس می‌تواند به ترتیب کشورهای ۴، ۳، ۲ و ۱ را فتح کند و به هدفش برسد. + کشور ۶ باشد و با قدرت $140$ شروع به کار کند، ابتدا می‌تواند به ترتیب کشورهای ۲، ۳، ۷، ۵ و ۱ را فتح کند تا قدرتش $257$ شود. در نهایت می‌تواند کشورهای ۴ را فتح کند و به هدفش برسد. + کشور ۷ باشد و با قدرت $93$ شروع به کار کند، ابتدا می‌تواند کشور ۵ را فتح کند تا قدرتش $97$ شود. سپس می‌تواند کشور ۳ را فتح کند تا قدرتش $129$ شود. سپس می‌تواند کشور ۶ را فتح کند تا قدرتش $257$ شود. در نهایت می‌تواند به ترتیب کشورهای ۴، ۲ و ۱ و به هدفش برسد. می‌توان نشان داد اگر با قدرتی کمتر از این مقدار شروع کند، نمی‌تواند به هدفش برسد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- جایگشتی از اعداد $1$ تا $n$ در اختیار داریم که $n$ عددی زوج است. در هر مرحله *مشتلی* دو عضو **مجاور** را انتخاب می‌کند که عضو سمت چپ بزرگتر از عضو سمت راست باشد، سپس هر دو را حذف کرده و باقی اعضای آرایه را به هم می‌چسباند. حال *مشتلی* می‌خواهد تعداد روش‌های پاک کردن تمام اعضای جایگشت را پیدا کند. از آن‌جایی که ممکن است این مقدار بیش از حد بزرگ شود، مشتلی از شما می‌خواهد که باقی‌مانده این مقدار بر $10^9+7$ را برای او پیدا کنید. # ورودی در اولین سطر ورودی، عدد طبیعی **زوج** $n$ نمایانگر طول جایگشت آمده است. $$2 \le n \le 500$$ در سطر بعد جایگشت $a_1, a_2, ..., a_n\,$ آمده است. # خروجی در تنها سطر خروجی، باقی‌مانده تعداد روش‌های حذف تمام اعضای جایگشت ورودی بر $10^9+7$ را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 6 6 4 3 2 1 5 ``` ## خروجی نمونه ۱ ``` 3 ``` ۳ روش حذف تمام اعضا: + $[6, 4, 3, 2, 1, 5] \rightarrow [6, 2, 1, 5] \rightarrow [6, 5] \rightarrow []$ + $[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 1, 5] \rightarrow [6, 5] \rightarrow []$ + $[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 3, 5] \rightarrow [6, 5] \rightarrow []$ ## ورودی نمونه ۲ ``` 8 5 8 6 7 2 3 4 1 ``` ## خروجی نمونه ۲ ``` 9 ``` ۹ روش حذف تمام اعضا: + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [4, 1] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [5, 3] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3] \rightarrow [5, 3] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [4, 1] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [5, 3] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 8, 4, 1] \rightarrow [5, 1] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 8, 6, 3] \rightarrow [5, 3] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 7, 2, 3] \rightarrow [5, 7, 2, 3] \rightarrow [5, 3] \rightarrow []$ + $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 7, 2, 3] \rightarrow [5, 8, 6, 3] \rightarrow [5, 3] \rightarrow []$

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *آشمز* که با حقوق جدیدش دنباله‌ی $n$ عضوی $a_1, a_2, \dots, a_n\,$ از اعداد صحیح را خریده است، با اشتیاق دنباله‌اش را به *کشی* نشان داد. اما *کشی* در یک ضد حال به *آشمز* گفت تعداد ۴۲ های دنباله کم است! پس تصمیم گرفتند با انجام تعدادی عملیات دنباله را طوری تغییر دهند تا تعداد ۴۲ های آن زیاد شود. آن‌ها می‌توانند عملیات های زیر را انجام دهند: + *آشمز* در هر عملیات می‌تواند یک **پیشوند** از دنباله را انتخاب و یک واحد از آن کم کند. + *کشی* در هر عملیات می‌تواند یک **پسوند** از دنباله را انتخاب و یک واحد از آن کم کند.  در این سوال شما باید به *آشمز* و *کشی* کمک کنید و با ورودی گرفتن دنباله‌ی اولیه، بیشینه تعداد تکرار های ممکن ۴۲ را برای آن‌ها محاسبه کنید. دقت کنید که ترتیب و تعداد عملیات‌ها دلخواه است و اعداد دنباله، پس از انجام یک عملیات ممکن است منفی شوند. # ورودی در سطر اول ورودی، عدد $n$ نشان دهنده‌ی طول دنباله آمده است. $$1 \leq n \leq 1437$$ در سطر دوم ورودی، $n$ عدد صحیح به نام $a_1, a_2, \dots, a_n\,$ آمده که وضعیت اولیه دنباله را نشان می‌دهد. $$1 \leq a_i \leq 10^9$$ # خروجی در تنها سطر خروجی باید بیشینه تعداد تکرار های ممکن ۴۲ پس از انجام تعداد دلخواهی عملیات را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 43 42 43 ``` ## خروجی نمونه ۱ ``` 3 ``` در این مثال اگر آشمز روی پیشوند به طول ۱ و کشی روی پیشوند به طول ۱ عملیات انجام دهد، تمام اعضای دنباله ۴۲ خواهند شد. ## ورودی نمونه ۲ ``` 7 37 42 45 45 45 42 37 ``` ## خروجی نمونه ۲ ``` 4 ``` در این مثال اگر آشمز سه بار روی پیشوند به طول ۵ عملیات انجام دهد، دنباله به $a = [34, 39, 42, 42, 42, 42, 37]$ تبدیل خواهد شد که تعداد ۴۲ های آن ۴ است. می‌توان نشان داد به هر نحوی عملیات انجام دهیم، تعداد ۴۲ ها بیشتر از ۴ نخواهد شد. ## ورودی نمونه ۳ ``` 7 45 50 44 5 46 44 45 ``` ## خروجی نمونه ۳ ``` 5 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در یک رستوران غذاها را به صورت سلف سرویس در یک ردیف قرار می‌دهند. میزان کالری هر غذا را می‌توان با یک عدد صحیح نشان داد. (این عدد می‌تواند منفی باشد.) در واقع می‌توان وضعیت کالری‌ها را به صورت یک دنباله از اعداد صحیح $a_1, a_2, \dots, a_n \,$ در نظر بگیریم. که $a_i$ کالری غذای $i$ام را نشان می‌دهد. در یک روز $k$ نفر وارد رستوران می‌شوند و می‌خواهند این غذاها را بخورند. هر کس یک بازه از این دنباله را انتخاب می‌کند و همه‌ی غذاهای این بازه را می‌خورد. هر کس باید یک بازه ناتهی انتخاب کند و نباید بازه هیچ دو نفری اشتراک داشته باشد.  صاحب رستوران می‌خواهد بداند حداکثر کالری که این $k$ نفر می‌توانند بخورند را پیدا کند. اما چون نمی‌داند مقدار $k$ چقدر است؛ از شما می‌خواهد به‌ازای همه‌ای اعداد طبیعی از $1$ تا $n$ این مقدار را محاسبه کنید. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد غذاها را نشان می‌دهد. $$1 \leq n \leq 300 \, 000$$ در سطر دوم ورودی، $n$ عدد صحیح که با یک فاصله از هم جداشده‌اند آمده است که عدد $i$ام آن برابر $a_i$ بوده و نشان‌دهنده‌ی میزان کالری غذای $i$ام است. $$-10^9 \leq a_i \leq 10^9$$ # خروجی خروجی $n$ سطر دارد، در سطر $k$ام، حداکثر میزان کالری که با آمدن $k$ نفر به رستوران می‌توان بدست آورد را محاسبه کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 4 5 1 ``` ## خروجی نمونه ۱ ``` 10 10 10 ``` ## ورودی نمونه ۲ ``` 5 -1 -2 -3 -4 -5 ``` ## خروجی نمونه ۲ ``` -1 -3 -6 -10 -15 ``` ## ورودی نمونه ۳ ``` 8 1 3 -8 3 4 1 -9 7 ``` ## خروجی نمونه ۳ ``` 8 15 19 19 19 19 11 2 ```