Saitomo, an A-Rank professional hero who is famous as the One-Punch-Man, decided to share the real secret of his power to one of his disciples.
Riana (Saitomo's disciple) became a hero because she couldn't find any other job. Despite this sad fact, she is able to learn Saitomo's secret and can now also defeat any enemy with one punch. She is so strong that the shockwaves of her punch can be transmitted through the bodies of her enemies. This means that if an enemy is punched and defeated, the shockwaves of Riana's punch travels through the enemy to the enemy's neighbors and their neighbors' neighbors and so on and so forth. This domino effect only stops if there is an empty space between two enemies.
One day, a number of enemies appeared around the city, and formed a circle to surround it.
Given a string where X denotes that the space is occupied by an enemy, and . denotes that the space is empty, determine the minimum number of empty spaces that should be replaced with enemies so that Riana can defeat all enemies with at most one punch. The string is circular, which means that the last character of the string circles back and is connected to the first character.
Note that XXXXX means that the 5 enemies are beside each other, thus if you defeat any one of them, the shockwave will pass through and defeat all of them, but .X.X. will require Riana to use 2 punches to eliminate all enemies.
The only input contains a string, consisting of either . or X
The length of the string will not exceed 100 characters.
Output in a single line an integer denoting the minimum number of empty spaces needed to be filled with an enemy.
XX..XX.X....
3
X..XX.X..X
3
For the 2nd sample case, we can add 3 enemies (in locations 2, 3, 6) to connect all the enemies and transform it into XXXXXXX..X which Riana can use to defeat them all in one punch.
Last valentines, Riana went on a blind date with Zanoki-kun, a famous shoujo manga mangaka, but after a series of misunderstandings, she accidentally became one of his manga assistants.
In his new manga, Biidoru wa Meido-sama! (Class Beadle is Maid!), he adopts a new system of expressing dates on a calendar. In this system, Zanoki-kun takes the numerical value of the month (January = $$$1$$$, February = $$$2$$$, March = $$$6$$$, ... , November = $$$11$$$, December = $$$12$$$), and appends the day to it. Thus, representing each date as a single integer.
For example:
January $$$1$$$ becomes $$$11$$$.
February $$$23$$$ becomes $$$223$$$.
November $$$5$$$ becomes $$$115$$$.
December $$$24$$$ becomes $$$1224$$$.
It just so happens that it takes Zanoki-kun $$$1$$$ pencil to draw the integer '$$$1$$$', $$$2$$$ pencils to draw the integer '$$$2$$$', and so on. Generally, it takes Zanoki-kun $$$n$$$ pencils to draw the integer '$$$n$$$'.
In chapter $$$1$$$ of Biidoru wa Meido-sama!, Zanoki-kun decides to draw all the dates from year $$$A$$$ to year $$$B$$$ inclusive. Zanoki-kun wants to prepare all the pencils he needs before he starts drawing, but he doesn't want to waste any more money than he has to, so he commissions his manga assistants, including Riana, to compute the least number of pencils he needs to draw all the dates from year $$$A$$$ to year $$$B$$$ inclusive. Note that the date does not include the year.
More formally, let $$$S$$$ be the least number of pencils Zanoki-kun needs in order to draw all the dates from year $$$A$$$ and year $$$B$$$ inclusive. Find $$$S$$$ given $$$A$$$ and $$$B$$$.
Note that three criteria must be taken into account to identify leap years:
- The year can be evenly divided by $$$4$$$;
- If the year can be evenly divided by $$$100$$$, it is NOT a leap year, unless;
- The year is also evenly divisible by $$$400$$$. Then it is a leap year.
Two spaced integers $$$A$$$ and $$$B$$$. The first integer, $$$A$$$, is the year that Zanoki-kun chooses to begin drawing at. The second integer, $$$B$$$, is the year that Zanoki-kun chooses to end drawing at.
It is guaranteed that $$$A$$$ and $$$B$$$ ranges from $$$0$$$ to $$$10^{18}$$$ inclusive. ($$$0 \leq A \leq B \leq 10^{18}$$$)
Output the least number of pencils Zanoki-kun needs in order to draw all the dates from year $$$A$$$ and year $$$B$$$ inclusive. Since the answer can get quite large, output only the positive remainder when $$$S$$$ is divided by $$$104206969$$$, Zanoki-kun's favorite a prime number.
1 3
542274
$$$11 + 12 + \ldots + 21 + 22 + \ldots + 31 + 32 + \ldots + 41 + 42 + \ldots + 51 + 52 + \dots + 61 + 62 + \ldots$$$ $$$+ 71 + 72 + \ldots + 81 + 82 + \ldots + 91 + 92 + \ldots + 101 + 102 + \ldots + 111 + 112 + \ldots$$$ $$$+ 121 + 122 + \ldots + 11 + 12 + \ldots + 21 + 22 + \ldots + 31 + 32 + \ldots + 41 + 42 + \ldots + 51 + 52 + \ldots$$$ $$$+ 61 + 62 + \ldots + 71 + 72 + \ldots + 81 + 82 + \ldots + 91 + 92 + \ldots + 101 + 102 + \ldots + 111 + 112 + \ldots$$$ $$$+ 121 + 122 + \ldots + 11 + 12 + \ldots + 21 + 22 + \ldots + 31 + 32 + \dots + 41 + 42 + \ldots + 51 + 52 + \ldots$$$ $$$+ 61 + 62 + \ldots + 71 + 72 + \ldots + 81 + 82 + \ldots + 91 + 92 + \ldots + 101 + 102 + \ldots$$$ $$$+ 111 + 112 + \ldots + 121 + 122 + \ldots + 1230 + 1231 = 542274$$$
Riana is late for school! She is currently at block 1 of $$$N$$$ blocks along a straight line from left to right. She wants to go to Ateneo, located at block $$$A$$$. She can run leftwards or rightwards.
Additionally, there are $$$B$$$ bus stops scattered about, and Riana might come across one or more of these bus stops. Each bus stop is located at some block and always has a bus ready to take Riana to some other fixed, predetermined block, and nowhere else. (Passengers aren't allowed to get off the bus at any location other than the predetermined destination block.) All the bus stops are in different blocks. There is only a single destination for all buses that serve the same bus stop, but buses for different bus stops may have different destinations. Being the rich Atenean that she is, Riana always grabs the opportunity to ride these fancy buses (w/ aircon and free WiFi!) at every moment she comes across a bus stop. A destination block may have another bus stop. In this case, after getting off one bus, Riana immediately takes another bus to another destination block. Buses only take passengers towards higher-numbered blocks, so Riana can never take a bus to return to a bus stop that she just came from.
Given this, will Riana be able to get to Ateneo? If so, print YES. Otherwise, print NO.
The first line contains three space-separated integers $$$N$$$, $$$A$$$, and $$$B$$$ — the number of blocks, the block where Ateneo is located, and the number of bus stops, respectively. $$$N$$$ and $$$A$$$ are guaranteed to be between $$$2$$$ and $$$100$$$ (inclusive), with $$$A$$$ $$$\leq$$$ $$$N$$$. $$$B$$$ is guaranteed to be between $$$1$$$ and $$$50$$$ (inclusive).
The next $$$B$$$ lines contain two space-separated integers $$$X$$$ and $$$Y$$$ — the location of a bus stop and its destination, respectively. Both of these values are guaranteed to be between $$$1$$$ and $$$100$$$ (inclusive). It is also guaranteed that $$$X$$$ $$$ \lt $$$ $$$Y$$$.
It is guaranteed that the first numbers in each of the $$$B$$$ lines are distinct from each other.
Single line containing YES or NO.
10 5 4 1 3 2 6 4 10 7 9
YES
8 3 2 2 6 4 7
NO
For Example 1, Riana takes a bus to block 3, then runs left towards block 2 and takes a bus to block 6, then she finally runs left to block 5.
Riana baked a round pie in preparation for her birthday party. After baking the pie, she thought that it would be boring to simply give the pie evenly across everyone attending her party. After some thought, she came up with the idea of using the pie in a game for the party goers.
In her game, each person attending the party will each take only one turn.
One full turn goes like this:
- Person $$$i$$$ begins his turn by choosing a percentage $$$P_i\%$$$ between 0-100.
- Person $$$i$$$ then takes $$$P_i\%$$$ of the pie remaining.
- Person $$$i$$$ ends his turn by taking $$$P_i\%$$$ of the slices of pie that have already been taken by everyone who went before person $$$i$$$.
For example, if four people Mathil, Quin, Octavian, and Velyna attend the party:
- In the first turn, Mathil starts by choosing 30%.
- He then takes 30% of the remaining pie which has not been touched, meaning Mathil takes 30%.
- Mathil has 30% of the pie.
- The pie is now 70% of its original size.
- In the second turnn Quin chooses 20%.
- Quin then takes 20% of what's left of the pie, which is 14% of the pie's original size.
- Next, Quin takes 20% of Mathil's slice, which is 6% of the pie's original size.
- Mathil now only has 24% of the pie, while Quin has (14%+6%) 20% of the pie's original size.
- The pie is now 56% of its original size.
- In the third turn, Octavian comes in and chooses 10%.
- Octavian take 10% of the what's left of the pie, which is 5.6% of the pie's original size.
- He then takes 10% of Mathil's remaining 24% and Quin's 20%
- Mathil now only has 21.6% of the pie's original size.
- Quin now only has 18% of the pie's original size.
- Octavian has 10% of the pie's original size.
- The pie is now 50.4% of its original size.
- In the fourth and final turn, Velyna comes in and chooses 50%.
- Velyna takes 50% of the what's left of the pie, which is 25.2% of the pie's original size.
- She then takes 50% of Mathil's remaining 21.6%, Quin's remaining 18%, and Octavian's 10%.
- Mathil now only has 10.8% of the pie's original size.
- Quin now only has 9% of the pie's original size.
- Octavian now only has 5% of the pie's original size.
- Velyna has 50% of the pie's original size.
- The pie is now 25.2% of its original size.
But wait! this is wrong! Riana's household has a strict 'no leftovers' policy, so she wants 100% of the pie to get eaten!
Riana is also an advocate of equality, so she wants to distribute the pie slices such that the difference between the biggest slice and the smallest slice is minimized.
However, Riana is also secretly lazy, so she enlisted the help of her friend, you! Help her figure out the optimal percentage each person should take.
The input will contain one line containing a single integer $$$N$$$, the number of people going to the party.
The value $$$N$$$ is guaranteed to be between $$$1$$$ and $$$10^{3}$$$.
Output contains $$$N$$$ lines.
The $$$i$$$th line of the output must contain the percentage of the pie which the $$$i$$$th person to take slices should take. (The first person's percentage should be on the first line, the second should be on the second line, the third should be on the third line, etc.)
Answers will be accepted if they are within $$$10^{-4}$$$ away from the correct answer.
1
100.0000
In the sample test case, since the first person is the only person in the party (quite sad), he takes the whole cake.
This satisfies the two conditions that Riana wanted to satisfy:
- 100% of the cake is eaten.
- The difference between the Maximum and the Minimum is minimized. (The difference is 0.)
After a long week of orgwork and acads, Riana spends her Saturday evenings unwinding on the famous MMORPG Blue Eagle Online. Here, she is not Riana, CompSAt president and model student—she is the infamous $$$\texttt{r}\color{red}{\texttt{airay}}$$$, Lvl 420 Ranger, PvP Legendary Grandmaster, and highest-ranking solo player on the OBF server. Online, no one is dependent on her and she herself answers to no one. She can let go of her responsibilities and live only for the thrill of battle and the glory of triumph. She is one of only three people in the game to have a MAGIS Bow, a legendary weapon that requires you to trade in rare drops from five different insanely difficult raid bosses in order to get it (Ch'thon, Cyandragosa, Collector, Centennarius, and Chromewing).
Like many MMORPGs, Blue Eagle Online has a crafting system that allows players to enhance their weapons using ore. An ore can bestow different properties to a weapon, such as stat modifiers, elemental damage modifiers, immunity to status, increased movement speed, lowered cooldown for skills, and even specific skills or abilities that can only be used while the enhance weapon is equipped. Riana is primarily interested in an ore's Might Multiplier $$$v$$$. Each weapon has some initial value for its might. If the crafting with the ore succeeds, then the might of the weapon is multiplied by $$$v$$$. If the crafting fails, the might of the weapon gets multiplied by $$$\dfrac{1}{v}$$$ instead.
If, after a crafting attempt, Riana enhances her weapon with another ore, the process still works as detailed above, except now using the modified might of the weapon, i.e. the effects stack. For example, suppose Riana begins with a bow whose might is $$$9$$$. She successfully enhances it with an ore with Might Multiplier $$$2$$$, so the bow's new might is $$$18$$$. Then, she tries to enhance it with an ore with Might Multiplier $$$6$$$, but it fails, so the bow's new might is $$$3$$$. Note that even if the bow's might and the ore's Might Multiplier are both integers, it is possible that the might of the bow after crafting is no longer an integer. This RPG stores the exact rational number value, and does not round the might of the bow at any point.
The MAGIS Bow currently has a might value of $$$x$$$. Riana has a list of $$$m$$$ ores which she plans to use to upgrade it. Consider the set of all possible upgraded bows that could be the final result of all possible combinations of success and failure of the enhancing attempts. If there are $$$m$$$ ores, then there are $$$2^m$$$ possible upgraded bows that Riana could get, depending on the results of the crafting. Normally, Riana might want to find the arithmetic mean of the final mights of all of these bows, but she thinks that's too easy. Instead, as a challenge, she wants you to find their geometric mean instead.
The geometric mean of a set of $$$n$$$ non-negative numbers is the $$$n$$$th root of their product. So, if the final mights of each of the possible bows is $$$s_1, s_2, \dots, s_{2^m}$$$, then their geometric mean is computed as
$$$$$$ \sqrt[2^m]{s_1 \times s_2 \times \dots \times s_{2^m}}. $$$$$$
Given the current might $$$x$$$ of MAGIS Bow and the properties of $$$m$$$ different ores, compute the geometric mean of the might of all $$$2^m$$$ possible bows that could be the final result of crafting with all the ores.
The first line of input consists of a single integer $$$x$$$, the initial might of the MAGIS Bow. It is guaranteed that $$$x$$$ is between $$$1$$$ and $$$10^{18}$$$ (inclusive).
The second line of input consists of a single integer $$$m$$$, the number of different ores. It is guaranteed that $$$m$$$ is between $$$1$$$ and $$$10$$$ (inclusive).
Each of the $$$m$$$ lines that follows contains the description of a given ore that will be used for enhancement. Each line will be in the following format,
name_of_ore + ":" + property1 + ";" + property2 + ";" + ... + ";" + final_property
The name of the ore and the description of each property are non-empty strings consisting of upper and lower case English letters, numbers, plus +, forward slash /, open and close square brackets [], period ., and/or space characters. There will never be two spaces in a row, and a name or property will never begin or end in a space. It is guaranteed that each ore has at least one property and exactly one of these properties is of the form "Might Multiplier x" + v, where $$$v$$$ is a real number between $$$0$$$ and $$$10$$$ (exclusive) indicating the Might Multiplier of that ore, given to at most one decimal point. This will be the only property which contains the string Might Multiplier. It is guaranteed that the line describing each ore is at most 1000 characters in length, including spaces and other punctuation.
Output in a single line the geometric mean of the mights of all possible bows that could be a result of the enhancements. The answer will be accepted if it is no more than $$$10^{-9}$$$ away from the correct answer.
6 2 Champion Dust:Might Multiplier x3;STA +2019;STR x5;[Skill] 5 Hit Sweeping Strikes;[Passive] Immunity Lordlight Crystal:[Elemental Damage] Holy;RES +1859;Might Multiplier x1.5;[Passive] Cura Personalis;[Color] Ultramarine
6
If both enhancements succeed, the MAGIS Bow has might $$$27$$$. If both enhancements fail, the MAGIS Bow has might $$$\dfrac{4}{3}$$$. If only the first enhancement succeeds, its might is $$$12$$$, and if only the second enhancement succeeds, its might is $$$3$$$. Thus, the four possible mights of the bow, depending on the results of the enhancements, are $$$27$$$, $$$12$$$, $$$3$$$, and $$$\dfrac{4}{3}$$$. To get the geometric mean, we need the $$$4$$$th root of their product, which is $$$\sqrt[4]{27\times12\times3\times\dfrac{4}{3}} = \sqrt[4]{1296} = 6$$$.
Riana recently made a Fiber account! Fiber is an all-new healthy, fibrous chatroom system that obviously does not collect any data about you or your chats. Because Fiber is a Weast Korean service, its users follow an unusual lingustic tradition of Confucian respect based on age; essentially, rules on who uses informal language to refer to other people and who uses formal language to refer to their chatroom mates, within each Fiber chatroom.
A Fiber user must use informal language (talk informally) to a user of the same age or younger. A user must use formal language (talk formally) to older users. Age in Weast Korea is determined by year: users born in the same year are considered to be the same age, regardless of birthday. A user born on a date whose year is greater than the year of the birthdate of another user is considered to be younger. Similarly, A user born in a year less than that of another user is considered to be older.
The members of Girl's Generation. How would they talk to each other in their Fiber chatroom?
This sounds simple enough, except there is one other thing to consider. Users born on or before February 28 of a certain year are considered to be "fast year", and are considered to be the same age to users born in the immediately previous year, as well as those users born on the same year. Also, if two users in a Fiber chatroom has a common user who are considered to be the same age, then these two users are also the same age.
Refer to the sample cases and the notes section for an example of the rules above.
Riana is not very accustomed to this whole "talking formally" thing, so when she joins a chatroom with $$$N$$$ users already in it, she wants to bring some more users so that everyone in the chatroom (including the users that she brought in) can talk informally to each other. More formally, for every pair of users in the chatroom (including the new users), both users should talk to each other informally. Fortunately, Riana is sociable enough to bring along an arbitrary number of users, each with arbitrary birthdays to the chatroom. But she wants to bring the least number of users necessary to accomplish the task. Given that Riana's registered birthday in Fiber is $$$B$$$, help her accomplish this.
Please note that Riana's sometimes uses different birthdays to register in Fiber!
The first line of input contains the integer $$$1 \leq N \leq 100000$$$, the number of people who are already in the Fiber chatroom that Riana wants to join. The second line of input contains Riana's birthday $$$B$$$ in the YYYY-MM-DD format or the YYYYY-MM-DD format. The next $$$N$$$ lines of input contains the birthdays of the people in the Fiber chatroom in the YYYY-MM-DD format or the YYYYY-MM-DD format. It is guaranteed that all of the given birthdays are valid dates. There will be no dates corresponding to leap days. Also, it is guaranteed that the year of each date will be at least $$$1000$$$ and no more than $$$99999$$$.
The first line of output should contain the number of people $$$p$$$ that Riana needs to bring along. Then, for each of the next $$$p$$$ lines, print the birthdates of the people she should add to the Fiber chatroom. Print all of them using the YYYY-MM-DD format, if the year of the birthdate is less than 10000, and YYYYY-MM-DD format otherwise. If there are multiple possible answers, print any one of them. If Riana does not need to bring users, then print $$$0$$$. If Riana cannot accomplish her task, then output $$$-1$$$.
4 1999-09-13 1999-08-01 1999-05-15 1999-12-05 2000-05-30
1 2000-02-10
2 1999-07-25 1999-03-05 1996-09-03
3 1999-01-28 1998-01-03 1997-01-13
For the first sample case, Riana's Birthday $$$B$$$ is on September 13, 1999.
Tiffany, who was born on August 1, 1999, is the same age as Sunny, who was born on May 15, 1999, as well as Yuri, who was born on December 5, 1999. Tiffany is also older than Seohyun, born on May 30, 2000. This means that Seohyun, in turn, is younger than Tiffany, or any of the people born on 1999. Now, Riana brings in Sooyoung, who was born on February 10, 2000. Sooyoung is considered to be the same age as Seohyun, because they were born on the same year. Sooyoung is also considered to be the same age as Yuri, for example, because Sooyoung is considered to be "fast year". Now, because Yuri and Seohyun are both considered to be the same age as Sooyoung, Yuri and Seohyun are considered the same age too. It can be shown that, by adding Sooyoung to the chat, everyone will now talk to each other informally.
For the second sample case, Riana's Birthday $$$B$$$ is on July 25, 1999.
Joy, born on September 3, 1996, is older than both Riana, and Yeri, born on March 5, 1999. Riana and Yeri are of the same age. To make sure that Riana and Yeri should talk informally to Joy, Riana will bring three people. Let us label these three people as A, B, and C, as shown in the sample output. Riana and Yeri are considered the same age as A. A is also considered the same age as B. Therefore, Riana and Yeri are considered the same age as B. In this way, it can be shown that, when Riana adds A, B, and C to the chatroom, everyone will talk to each other informally.
Due to her success as a singer, songwriter, DISCS PrO problem setter, and CEO of the cosmetics brand Fenwick Beautree, Riana has been having trouble dealing with aggressive fans and rude boys. She can't use her usual strategy of hiding under her umbrella because it hasn't been raining, raining.
In spite of difficult fans, Riana is planning an event for launching her new product, the Matte Flow Lipstick. She needs your help to make the product launch work, work, work, work, work. As much as she believes that her fans are beautiful like diamonds in the sky, she admits that there can be some who stir up trouble before her events can even start.
Riana's launch venue has a width of $$$W$$$ and a length of $$$L$$$ when viewed from the top, and she has a reliable team of bodyguards who can call as much backup to the venue as needed. Their years of experience have helped them develop an optimal strategy for minimizing the access of troublemakers to the event grounds! They don't want to alarm Riana's guests during her events, so they assemble gradually.
Let's say the first bodyguard at the venue is positioned as follows:
That bodyguard will call at most four ($$$4$$$) backup bodyguards who will, after one second, position themselves exactly one unit north, exactly one unit south, exactly one unit east, and exactly one unit west of the original bodyguard if the spot is vacant and does not go beyond the venue. Those bodyguards will then do the same thing immediately after they position themselves, and even more bodyguards arrive after another second. This process will continue until all spots in the venue are taken. This is illustrated as follows:
Unfortunately, the troublemaking fans have learned this and will plan on using the exact same strategy. Troublemaking fans also arrive and position themselves at exactly one unit north, exactly one unit south, exactly one unit east, and exactly one unit west of the fan that called them, one second after they are called. Each newly arrived troublemaker will also call more troublemakers immediately after they position themselves, and even more troublemakers arrive after another second, and so on.
However, Riana's bodyguards took an oath. If at any point they will have to compete with the fans for a spot in the venue, they'll stick it out 'til the end and will be able to take the spot before Riana's fans do!
Riana wants to position the first bodyguard such that they minimize the troublemakers at the venue. If you are given the starting position $$$(X,Y)$$$ of the first troublemaking fan, where should Riana's first bodyguard be positioned? Note that $$$X$$$ corresponds to the row where the troublemaker is, and $$$Y$$$ corresponds to the column. The position $$$(1,1)$$$ is located at the upper-left corner of the venue when viewed from the top.
The first line of input contains two integers, $$$W$$$ and $$$L$$$ which represent the width and the length of the venue respectively. $$$W$$$ and $$$L$$$ are guaranteed to be between $$$1$$$ and $$$1000$$$ (both inclusive).
The second line of input contains two integers, $$$X$$$ and $$$Y$$$ which correspond to the position $$$(X,Y)$$$ of the first troublemaking fan. $$$X$$$ is guaranteed to be between $$$1$$$ and $$$W$$$ (both inclusive). $$$Y$$$ is guaranteed to be between $$$1$$$ and $$$L$$$ (both inclusive).
Output one integer which represents the minimum number of troublemakers that will be at the venue after it becomes fully occupied, if the first bodyguard is positioned at the optimal spot. Output this number only if the number of bodyguards is strictly greater than the number of troublemakers. Otherwise, output I don't wanna do this anymore!
4 3 3 2
4
1000 1000 306 865
41616
For the first sample test case, the first fan is positioned as follows:
It can be shown that if the first bodyguard is stationed at the right location, the number of troublemakers is $$$4$$$.
Riana got really bored one day and decided to play with some integers. She started with the positive integer $$$N$$$. She then noticed that $$$N$$$ was too small and boring. Suddenly, she got the idea to create a really big integer. To do so, she multiplied all of the positive divisors of $$$N$$$ and got the integer $$$M$$$. After getting the value of $$$M$$$, she challenged her friend Cisco to determine the value of the original integer $$$N$$$ given $$$M$$$. Help Cisco find the value of $$$N$$$.
The input contains one line containing the integer $$$M$$$. It is guaranteed that $$$M$$$ is a positive integer less than $$$10^{15}$$$.
Output the original integer $$$N$$$ if possible. Otherwise, output $$$-1$$$.
8
4
4
-1
In the first test case, the positive divisors of 4 are 1, 2, and 4. The product is 8.
In the second test case, there is no integer whose product of its positive divisors is 4.
Riana always wanted to join the secret order of the ProgVar. Most people doubt its existence, believing it to be just a myth propagated by paranoid conspiracy theorists. However, some, including Riana, know the truth: ProgVar is an immensely influential organization working behind the scenes to control the world at large.
The all-knowing ProgVar, of course, is aware of her intent. One day, she received an initiation parchment. The parchment contains a geometric graph of $$$n$$$ points, no three of which are collinear. Riana knows that ProgVar is obsessed with triangles, and that she may form a triangle from any three of the $$$n$$$ points.
To demonstrate her commitment to joining the order, she must count how many ways there are of forming two triangles such that one triangle lies entirely within the other. In particular, these two triangles must not share a vertex. Two ways of forming triangles are considered distinct if there is a point that is used as a triangle vertex in one way but not in the other way.
Riana, of course, is a capable follower, and she sent her answers to the order in less than two seconds. ProgVar, busy with more important world affairs, has outsourced the task of checking her answers to you. How many such ways of forming two triangles are there?
The first line contains the number of points $$$n \leq 300$$$.
The next $$$n$$$ lines each contains two integers $$$x$$$ and $$$y$$$, where the $$$i$$$th line denotes that the $$$i$$$th point is $$$(x, y)$$$.
The absolute values of the coordinates of each point are guaranteed not to exceed $$$10^4$$$.
Print how many such ways there are of forming two triangles that satisfy the problem.
Note that the answer may exceed $$$10^{10}$$$.
7 1 1 1 -1 -1 -1 -1 1 4 -2 -4 -2 0 3
4
8 3 0 2 2 0 3 -2 2 -3 0 -2 -2 0 -3 2 -2
0
15 -691 -45 -5993 -7095 4994 -4998 6585 6740 -3726 -241 -8489 -1030 -3261 3284 -2295 -2242 5985 -5838 -7843 -8290 -6834 278 3974 2002 -9268 6063 5698 6962 5664 -6676
307
It may also be shown that there are no other pairs of triangles that satisfy the problem conditions. Therefore, the answer for the first test case is $$$4$$$.