+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- پارسا چون خیلی بچه درس خونی است و به شدت به حل معماها علاقه دارد، سر کلاس اصلا حواسش به درس نبود و در حل معما فرو رفته بود. به همین خاطر، یادش رفت تمرین های فیزیکش را انجام دهد. او هم اکنون در سر کلاس فیزیکش است و چیزی از مساحت زیر نمودار نمی داند. دکتر شریفی (معلم فیزیک پارسا) که از موضوع خبر دارد، برای تنبیه پارسا، هر ثانیه از $q$ ثانیه زنگ کلاس، یکی از دو کار زیر را انجام می دهد : 1. یک خط با عرض از مبدا $b_i$ و شیب $a_i$ روی تخته می کشد. 2. از پارسا می خواهد مساحت زیر نمودار $L_i$ تا $R_i$ را حساب کند. **در واقع شما در هر $x$، ارتفاع نمودار در آن $x$ را برابر ماکسیمم $y$ خطوط در آن $x$ فرض کنید.** پارسا که چیزی از این ها بلد نیست، از شما (کناردستی‌اش) می خواهد به سرعت پاسخ ها را برای اون محاسبه کنید. برای وضوح بیشتر به مثال ۲ مراجعه کنید. # ورودی در خط اول ورودی، عدد $q$، تعداد ثانیه های زنگ کلاس فیزیک می آید. در ادامه $q$ خط می آیند. خط $i$ ام، به یکی از دو صورت زیر است : $$1 \ a_i \ b_i$$ $$2 \ L_i \ R_i$$ که حالت اول نشان دهنده اضافه کردن خط توسط دکتر شریفی است و حالت دوم نشان دهنده یک پرسش از پارسا است. $$1 \leq q \leq 100\ 000$$ $$-10\ 000 \leq a_i, b_i \leq 10\ 000$$ $$0 \leq L_i < R_i \leq 20\ 000\ 000$$ # خروجی به ازای هر پرسش از پارسا، در یک خط، مساحت زیر نمودار را چاپ کنید. اختلاف مطلق و نسبی شما با جواب درست نباید بیش از $10^{-6}$ باشد. در واقع اگر جواب شما $p$ و جواب درست $j$ باشد، در صورتی جواب شما درست در نظر گرفته می‌شود که $\frac{|p - j|}{max(j, 1)} \le 10^{-6}$. # مثال ## ورودی نمونه ۱ ``` 2 1 1 0 2 0 1 ``` ## خروجی نمونه ۱ ``` 0.500000 ``` دقت کنید که $L , R$ گفته شده به حالت بسته - باز بر روی محور $x$ هاست. در نتیجه بازه $[0 , 1)$ ، شامل یک مثلث قائمه الزاویه به اضلاع قائمه $1$ خواهد بود که مساحت آن $0.5$ است. همچنین دقت کنید ممکن است این مقدار منفی هم باشد (در صورتی که تمام خط ها زیر محور $x$ ها بروند) همچنین اگر خطی کشیده نشده بود، مساحت زیر نمودار را ۰ در نظر بگیرید. ## ورودی نمونه ۲ ``` 6 1 -1 2 2 0 1 1 0 1 2 0 2 1 1 -1 2 0 3 ``` ## خروجی نمونه ۲ ``` 1.500000 2.500000 4.000000 ```