سوال ۲

آقای مهندس و خانم دکتر تصمیم گرفته‌اند تابستان را به طور کامل استراحت کنند و برای مدتی کار را کنار بگذارند. آن‌ها روستای پدری آقای مهندس را برای استراحت انتخاب کرده‌اند. هر دوی آن‌ها به کشاورزی علاقه‌مند هستند و قصد دارند در مدت تعطیلات، در زمین زراعی که متعلق به پدر آقای مهندس است، کشاورزی کنند. ولی در نوع محصول بایکدیگر به توافق نرسیده‌اند! آقای مهندس دوست‌ دارد توت‌فرنگی بکارد، ولی خانم مهندس کاشتن شلغم را ترجیح می‌دهد. برای همین آن‌ها تصمیم گرفته‌اند زمین را قسمت‌بندی کنند.

زمین زراعی را می‌توان به صورت یک مستطیل $h \times w$ در نظر گرفت. آن‌ها قرار است با استفاده از جوب‌های افقی و عمودی، قسمت‌بندی را انجام دهند و در هر کدام از قسمت‌ها شلغم یا توت‌فرنگی بکارند. برای این‌که زمین کشاورزی خوشگل شود، آن‌ها به این نتیجه می‌رسند که محصولات را به صورت شطرنجی بکارند. یعنی محصول هیچ دو قسمتی که مرز مشترک دارند، (یک نقطه به تنهایی مرز مشترک محسوب نمی‌شود) یکی نباشد. جوب‌کشی با آقای مهندس است و انتخاب این‌که محصولات به چه صورت کاشته شوند، با خانم دکتر است. (دقت کنید که تنها دو حالت وجود دارد) خانم دکتر هم که از شلغم بیشتر خوشش می‌آید، دوست دارد نحوه کاشتن محصولات را طوری تعیین کند که مقدار شلغمی که باید کاشته شود، بیشینه شود.

شما باید برنامه‌ای بنویسید که با گرفتن اطلاعات مربوط به جوب‌کشی‌های آقای مهندس بر حسب زمان، بعد از هر جوبی که ایجاد می‌شود، مشخص کند خانم دکتر چه مقدار از زمین را به کاشتن شلغم اختصاص می‌دهد.

• سطر اول ورودی به ترتیب شامل سه عدد طبیعی $w$، عرض زمین، $h$، طول زمین و $q$، تعداد جوب‌کشی‌ها، آمده است.
• در هر کدام از $q$ سطر بعدی، ابتدا $t \in \{H,V\}$ و سپس عدد $p$ می‌آید که کشیده شدن یک جوب را نشان می‌دهد. در صورتی که $t$ برابر با $H$ باشد یک جوب افقی در مکان $y = p \ (0 < p < h)$ کشیده می‌شود و در صورتی که $t$ مساوی با $V$ باشد، یک جوب عمودی در مکان $x = p \ (0 < p < w)$ کشیده می‌شود.
• تضمین می‌شود که هیچ دو جوبی در یک مکان کشیده نمی‌شوند.
• $1 \leq w, h \leq 10^9$
• $1 \leq q \leq 5 * 10^5$

خروجی شامل $q$ سطر است که در سطر $i$ام از آن مقدار مساحتی از زمین را که با در نظر گرفتن $i‌$ جوب اول باید در آن شلغم کاشته شود، ‌چاپ کنید.

• زیرمسئله اول (۵ نمره): $q \leq 500$
• زیرمسئله دوم (۵ نمره): $q \leq 5000$ و تمامی جوب‌ها در یک جهت هستند. (یا همه افقی اند یا همه عمودی اند)
• زیرمسئله سوم (۲۵ نمره): $q \leq 5000$
• زیرمسئله چهارم (۲۰ نمره): تمامی جوب‌ها در یک جهت هستند. (یا همه افقی اند یا همه عمودی اند)
• زیرمسئله پنجم (۴۵ نمره): بدون محدودیت اضافه

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

ورودی نمونه اول مانند تصویر زیر است.

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