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

---

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

زمین زراعی را می‌توان به صورت یک مستطیل $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\le w,h \le 10^9$$ $$1\le q\le 500\ 000$$

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۵	$ q \le 500 $
۲	۵	تمام جوب‌ها در یک جهت هستند(همه افقی یا عمودی هستند) , $ q \le 5\ 000$
۳	۲۵	$ q \le 5\ 000$
۴	۲۰	تمام جوب‌ها در یک جهت هستند(همه افقی یا عمودی هستند)
۵	۴۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 3 2
V 1
H 2

خروجی نمونه ۱

9
7

ورودی نمونه ۲

5 5 4
H 3
H 2
H 4
H 1

خروجی نمونه ۲

15
20
15
15

۲۴امین دوره‌ المپیاد کامپیوتر - آزمون چهارم - ۱۳۹۳/۰۶/۱۲