فلق

«صبح‌دم آغاز گشته و هنگام نبرد است

بشتابید ای دلاوران

تا آن نفس که مژده فرا رسد؛

و شما قدرت دوباره خواهید یافت…»

«سپید‌رویان»‌‌‌‌‌ و «سیه‌جامه‌گان» دو تمدن بسیار کهن بوده‌اند که این روزها سابقه‌ی نبرد و خونریزی میان آن دو تمدن٬ مورد توجه اکثر باستان‌شناسان حرفه‌ای قرار گرفته است. در اکتشافات اخیر٬ دکتر «گ»٬باستان‌شناس معروف٬ کتیبه‌ی طویلی یافته که شامل شرح کامل آخرین نبرد میان این دو تمدن است.

دکتر «گ» طریقت کتیبه را به ما چنین گزارش داده است:

در ابتدای آن٬ در سطر اول٬ سه مقدار $K$ , $n_b$ , $n_w$ نگاشته شده است که به ترتیب مبین تعداد مبارزان لشگر «سپید‌رویان»‌‌‌‌‌٬ تعداد مبارزان لشگر «سیه‌جامه‌گان» و تعداد روزهایی است که نبرد به طول انجامیده است.

سپس در سطر بعدی٬ $n_w$ عدد٬ با فاصله از هم نوشته شده‌اند که عدد $i$ام ‎$1 \leq i \leq n_w$ در این سطر٬‌ بیان‌گر میزان قدرت فرد $i$ از لشگر «سپید‌رویان»‌‌‌‌‌ ($w_i$)در آغاز کار است.

پس از آن در سطر بعدی (سوم)٬ $n_b$ عدد٬ با فاصله از هم نوشته شده‌اند که عدد $j$ام ‎$1 \leq j \leq n_b$ در این سطر٬‌ بیان‌گر میزان قدرت فرد $j$ از لشگر «سیه‌جامه‌گان» ($b_j$)در آغاز کار است.

پس از این سه سطر٬ در سطر چهارم تا سطر$K+3$ام٬ وقایع $K$ روز نبرد نگاشته شده است؛ که هر سطر آن٬ دقیقا یکی از سه حالت زیر است:

1. «F» بدین معنی است که در آن روز یک نبرد تن‌به‌تن رخ داده است و در طی آن٬ قوی‌ترین جنگجوی لشگر «سپید‌رویان»‌‌‌‌‌٬ به مصاف قوی‌ترین جنگجوی لشگر «سیه‌جامه‌گان» رفته است. می‌دانیم اگر در ابتدای یک نبرد تن‌به‌تن٬ قدرت نمایندگان دو لشگر٬ به ترتیب $P_w$ و $P_b$ باشد٬ پس از پایان نبرد٬ از قدرت هر دوی آن‌ها به اندازه‌ی$Min(P_w,P_b)$ واحد کم می‌شود و باطبع قدرت فرد ضعیف‌تر صفر می‌شود. دقت کنید که قوی‌ترین جنگجوی یک لشگر٬ در ابتدای همان روز انتخاب می‌شود و ممکن است پس از مدتی مجددا برای یک نبرد تن‌به‌تن دیگر فراخوانده شود.از سوی دیگر می‌دانیم در صورتی که در هنگام انتخاب قوی‌ترین جنگجو٬ دو (یا چند) جنگجو با قدرت بیشینه وجود داشته باشد٬ جنگجویی که شماره‌ی وی بیش‌تر است٬ «قوی‌ترین» در نظر گرفته شده و برای جنگ اعزام می‌شود.
2. «$HW \ x \ r$» بدین معنی است که در آن روز نه تنها نبردی صورت نگرفته بلکه قدرت نفر$x$ام از لشگر «سپید‌رویان»‌‌‌‌‌ نیز (که ‎$1 \leq x \leq n_w$)٬ به میزان$r \geq 0$ واحد توسط جادوگر مخصوص لشگر افزایش یافته است. توجه کنید که منظور از نفر$x$ام٬ جنگجوی شماره $x$ است و نه $x$امین فرد قوی لشگر.
3. «$HB \ y \ s$» بدین معنی است که در آن روز صلح کامل برقرار بوده و قدرت نفر $y$ام از لشگر «سیه‌جامه‌گان» که‎$1 \leq y \leq n_b$٬ توسط جادوگر ویژه آن لشگر٬ به میزان $s \geq 0$ واحد افزایش یافته است. مجددا به خاطر داشته باشید که منظور از نفر $y$ام٬ جنگجوی شماره $y$ است و نه $y$امین فرد قوی لشگر.

اکنون دکتر «گ» از شما می‌خواهد تا با حماسه آفرینی مجدد این نبرد عظیم به وی بگویید که در پایان این سلسله نبردها٬ میزان قدرت هر یک از افراد هر یک از دو قبیله٬ چه مقدار بوده است؟

• در ورودی٬ کتیبه با همان طریقت فوق‌الذکر داده شده است.
• ‎$1 \leq n_w,n_b \leq 10^5$
• ‎$0 \leq k \leq 333333$
• ‎$0 \leq w_i,b_j,r,s \leq 10^9$
• می‌توانید فرض کنید که قدرت هیچ جنگجویی در هیچ زمانی بیش‌تر از$2 \times 10^9$ نمی‌شود.

• در سطر اول٬ $n_w$ عدد بنویسید که به ترتیب بیان‌گر میزان قدرت نفرات اول تا $n_w$ام از لشگر «سپید‌رویان»‌‌‌‌‌ در پایان جنگ $k$ روزه است.
• در سطر دوم نیز قدرت افراد اول الی $n_b$ از لشگر «سیه‌جامه‌گان» در پایان نبرد با فاصله از هم بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• در روز اول یک نبرد تن‌به‌تن صورت می‌گیرد و نفر سوم از لشگر«سپید‌رویان»‌‌‌‌‌ با نفر چهارم از لشگر«سیه‌جامه‌گان» نبرد می‌کند و طی آن٬ قدرت آن دو به ترتیب به $6$ و $0$ کاهش پیدا می‌کند.
• در روز دوم٬ قدرت نفر اول «سپید‌رویان»‌‌‌‌‌ به $21$ افزایش پیدا می‌کند.
• در روز سوم٬ نفر اول از «سپید‌رویان»‌‌‌‌‌ به مصاف نفر سوم از «سیه‌جامه‌گان» می‌رود و پس از آن٬ قدرت آن دو از $21$ و $23$ به $0$ و $2$ کاهش می‌یابد.
• در روز چهارم٬ قدرت نفر چهارم «سیه‌جامه‌گان»٬ از صفر به $1000$ افزایش می‌یابد.
• در نهایت٬ در روز پنجم٬ نفر دوم از «سپید‌رویان»‌‌‌‌‌ با نفر چهارم از «سیه‌جامه‌گان» رودررو می‌شود که نتیجتا قدرت آن دو از $20$ و $1000$ به $0$ و $980$ کاهش می‌یابد.

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