* محدودیت زمان: ۰.۵ ثانیه
* محدودیت حافظه: ۱۲۸ مگابایت
----------
به سه‌تایی مرتب $(a, b, c)$ می‌گوییم **مثلثی** اگر $a, b, c$ سه عدد مثبت باشند و مثلثی به اضلاع $a, b, c$ وجود داشته باشد. به عنوان مثال $(4, 5, 6)$ و $(5, 4, 6)$ دو سه‌تایی مثلثی متفاوتند.
به شما سه عدد طبیعی $A, B, C$ داده می‌شود. تعداد سه‌تایی‌های مثلثی مانند $(a, b, c)$ را به پیمانه $10^9+7$ بیابید طوری که $1 \le a \le A $ و $1 \le b \le B $ و $1 \le c \le C $ باشد.
# ورودی
ورودی یک خط می‌باشد که شامل سه عدد $A, B, C$ است.
$$1 \le A, B, C \le 10^9$$
# خروجی
خروجی برنامه تنها یک عدد است که برابر با تعداد سه‌تایی‌های مثلثی با شرایط گفته شده به پیمانه $10^9+7$ است.
# زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|:-------:|:----------:|:-----------:|
|۱| ۱۰ | $A \times B \times C \le 10^6 $ |
|۲| ۲۰ |$\dfrac{A \times B \times C}{max(A, B, C)} \le 10^6 $|
|۳| ۷۰ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه ۱
```
1 10 20
```
## خروجی نمونه ۱
```
10
```
## ورودی نمونه ۲
```
10 10 10
```
## خروجی نمونه ۲
```
505
```
## ورودی نمونه ۳
```
1 1 1
```
## خروجی نمونه ۳
```
1
```
## ورودی نمونه ۴
```
123456789 987654321 555555555
```
## خروجی نمونه ۴
```
64296241
```
## ورودی نمونه ۵
```
2 2 1000000000
```
## خروجی نمونه ۵
```
6
```
سه‌تایی مثلثی
محدودیت زمان: ۰.۵ ثانیه
محدودیت حافظه: ۱۲۸ مگابایت
به سه‌تایی مرتب (a,b,c) می‌گوییم مثلثی اگر a,b,c سه عدد مثبت باشند و مثلثی به اضلاع a,b,c وجود داشته باشد. به عنوان مثال (4,5,6) و (5,4,6) دو سه‌تایی مثلثی متفاوتند.
به شما سه عدد طبیعی A,B,C داده می‌شود. تعداد سه‌تایی‌های مثلثی مانند (a,b,c) را به پیمانه 109+7 بیابید طوری که 1≤a≤A و 1≤b≤B و 1≤c≤C باشد.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۲۸ مگابایت
----------
روزی روزگاری $n$ تا از کامیون‌های شرکت باربری بمنثقتفخل بزرگراه امام علی (ع) را طی می‌کنند.
همان‌طور که می‌دانید بزرگراه دارای $10^6$ ورودی و $10^6$ خروجی است به این صورت که ورودی $i$-ام روبه‌روی خروجی $i$-ام است.
وقتی یک کامیون وارد بزرگراه می‌شود راننده آن یک بلیط سبز دریافت می‌کند که روی آن شماره آن ورودی و یک بلیط قرمز دریافت می‌کند که روی آن شماره خروجی که باید از آن خارج شود ثبت شده است. در هنگام خروج کامیون‌ها باید عوارض به مقدار اختلاف شماره دو عدد روی بلیط سبز و قرمز خود بپردازند.
بمنثقتفخل راهی پیدا کرده است تا رانندگانش عوارض کمتری بپردازد.هر دو راننده می‌توانند یکدیگر را در بزرگراه ملاقات کنند و بلیط‌های قرمز خود را با هم عوض کنند، حتی اگر هم مسیر نباشند.
به هر حال یک راننده نمی‌تواند از خروجی‌ای که از آن وارد بزرگراه شده است خارج شود زیرا این کار خیلی مشکوک است.
شرکت باربری بمنثقتفخل از شما می‌خواهد برایش کمینه مجموع عوارضی که باید رانندگانش بپردازند را حساب کنید.
# ورودی
خط اول ورودی فقط شامل عدد $n$ است.
در $n$ خط بعدی در هر خط دو عدد غیر برابر در بازه $1$ تا $10^6$ وجود دارد که به ترتیب شماره بلیط سبز و قرمز راننده $i$-ام است. هیچ دو راننده‌ای بلیط سبز برابر یا بلیط قرمز برابر ندارند.
$$ 1 \le n \le 100\ 000$$
# زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|:-------:|:----------:|:-----------:|
|۱| ۵ | $n\le 10$ |
|۲| ۱۵ | $n \le 20$ |
|۳| ۸۰ | بدون محدودیت اضافی |
# خروجی
خروجی برنامه تنها یک عدد است که برابر با کمینه مجموع عوارضی که باید رانندگان بمنثقتفخل بپردازند است.
# مثال
## ورودی نمونه ۱
```
3
3 65
45 10
60 25
```
## خروجی نمونه ۱
```
32
```
اگر راننده اول و سوم بلیط‌های قرمز خود را با هم عوض کنند سپس راننده دوم و سوم اینکار را انجام دهند. بعد از این کار بلیط قرمز رانندگان به ترتیب برابر ۱۰ و ۲۵ و ۶۵ می‌شود و مجموع عوارض پرداختی برابر $|65-60|+|25-45|+|10-3|=32$ می‌شود.
## ورودی نمونه ۲
```
3
5 5
6 7
8 8
```
## خروجی نمونه ۲
```
5
```
شرکت باربری بمنثقتفخل
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۱۲۸ مگابایت
روزی روزگاری n تا از کامیون‌های شرکت باربری بمنثقتفخل بزرگراه امام علی (ع) را طی می‌کنند.
همان‌طور که می‌دانید بزرگراه دارای 106 ورودی و 106 خروجی است به این صورت که ورودی i-ام روبه‌روی خروجی i-ام است.
وقتی یک کامیون وارد بزرگراه می‌شود راننده آن یک بلیط سبز دریافت می‌کند که روی آن شماره آن ورودی و یک بلیط قرمز دریافت می‌کند که روی آن شماره خروجی که باید از آن خارج شود ثبت شده است. در هنگام خروج کامیون‌ها باید عوارض به مقدار اختلاف شماره دو عدد روی بلیط سبز و قرمز خود بپردازند.
بمنثقتفخل راهی پیدا کرده است تا رانندگانش عوارض کمتری بپردازد.هر دو راننده می‌توانند یکدیگر را در بزرگراه ملاقات کنند و بلیط‌های قرمز خود را با هم عوض کنند، حتی اگر هم مسیر نباشند.
به هر حال یک راننده نمی‌تواند از خروجی‌ای که از آن وارد بزرگراه شده است خارج شود زیرا این کار خیلی مشکوک است.
شرکت باربری بمنثقتفخل از شما می‌خواهد برایش کمینه مجموع عوارضی که باید رانندگانش بپردازند را حساب کنید.
خط اول ورودی فقط شامل عدد n است.
در n خط بعدی در هر خط دو عدد غیر برابر در بازه 1 تا 106 وجود دارد که به ترتیب شماره بلیط سبز و قرمز راننده i-ام است. هیچ دو راننده‌ای بلیط سبز برابر یا بلیط قرمز برابر ندارند.
اگر راننده اول و سوم بلیط‌های قرمز خود را با هم عوض کنند سپس راننده دوم و سوم اینکار را انجام دهند. بعد از این کار بلیط قرمز رانندگان به ترتیب برابر ۱۰ و ۲۵ و ۶۵ می‌شود و مجموع عوارض پرداختی برابر ∣65−60∣+∣25−45∣+∣10−3∣=32 می‌شود.
* محدودیت زمان: ۰.۵ ثانیه
* محدودیت حافظه: ۲۵۶ مگابایت
----------
می‌گوییم دو دایره نسبت به هم اوکی اند اگر و تنها اگر یکی اکیدن داخل دیگری باشد و محیطشان هیچ نقطه‌ی مشترکی نداشته باشد. مجموعه‌ای از دوایر را خوب می‌نامیم اگر و تنها اگر هر دو دایره در این مجموعه نسبت به هم اوکی باشند. $n$ دایره داریم، آن‌ها را به کمینه تعداد مجموعه‌ی خوب افراز کنید.
# ورودی
در سطر اول ورودی عدد طبیعی $n$ آمده است.
در هر کدام از $n$ سطر بعد یک دایره، با سه عدد صحیح $ x_i, y_i, r_i $ (مختصات مرکز و شعاعش) آمده است.
$$1 \le n \le 400 $$$$1 \le x_i, y_i, r_i \le 10^9 $$
# خروجی
در یک سطر، کمینه تعداد مجموعه‌ها را در افراز بهینه چاپ کنید.
# زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|:-------:|:----------:|:-----------:|
|۱| ۵ | $ n \le 16 $ |
|۲| ۵ | $ n \le 21 $ |
|۳| ۱۰ | همه دایره‌ها هم مرکز اند. |
|۴| ۲۰ | $x_1=x_2=...=x_n$ |
|۵| ۶۰ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه
```
3
1 1 5
2 2 5
3 3 1
```
## خروجی نمونه
```
2
```
دایره‌ها را به دو دسته می‌توان افراز کرد. در یک دسته دایره‌ی ۱ و در دسته‌ی دیگر دایره‌ی ۲ و ۳.
دایره‌های اوکی
محدودیت زمان: ۰.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت
می‌گوییم دو دایره نسبت به هم اوکی اند اگر و تنها اگر یکی اکیدن داخل دیگری باشد و محیطشان هیچ نقطه‌ی مشترکی نداشته باشد. مجموعه‌ای از دوایر را خوب می‌نامیم اگر و تنها اگر هر دو دایره در این مجموعه نسبت به هم اوکی باشند. n دایره داریم، آن‌ها را به کمینه تعداد مجموعه‌ی خوب افراز کنید.