The team of competitive comedians, comedians++, needs to buy plane tickets to participate in the International Competition of Prehistoric Comedians (ICPC). You might know the founder of the team, the legendary Navarrosaur, who teaches some programming classes. However, the organization that is taking care of issuing the tickets is very well known for its bureaucracy, the Inorganized Management of Education (IME) (Yes, they are so unorganized they've never fixed the spelling mistake). The coordinator of the French arts sector of IME, professor Du'Art, is a very busy person and he asks his advisor, from Netherlands music sector, professor Van Der Som, to take care of the process to buy the flight tickets, but the comedians are having a hard time since the advisor has refused to buy the tickets!
The coordinator wants to help but he cannot interfere in the bureaucracy of IME. He gives the team a list of signatures they must obtain to discuss the advisor's decision and get the authorization to travel. Although, as IME is a very hierarchized institution, the signatures must be obtained in some order, called chain of command. To be more specific, if signature $$$A$$$ precedes signature $$$B$$$, signature $$$B$$$ can only be obtained if you already have signature $$$A$$$.
Given the list by the coordinator, help the comedians to look for a possible way to get all the necessary signatures.
The first line contains one integer, $$$M$$$ ($$$2 \leq M \leq 10^5$$$) — the number of precedence relations.
Each of the next $$$M$$$ lines contain $$$2$$$ strings, $$$A$$$ and $$$B$$$ ($$$1 \leq |A|,|B| \leq 30$$$) — the precedence relations between signatures, meaning "signature $$$A$$$ precedes signature $$$B$$$". $$$A$$$ and $$$B$$$ are different and consist only of uppercase English letters without blank spaces.
If it is possible to get all signatures print "I disagree with the advisor", otherwise print "No more comedians++".
2 JEFF POTATO JEFF MARK
I disagree with the advisor
3 PETER PARKER PARKER WAYNE WAYNE PETER
No more comedians++
Cosenza always goes to his Middle School Internship (MSI) in his brand new red Ferrari (pandas are color blind). Unfortunately, General Macário visited the school where Cosenza does his MSI and Cosenza got caught in the $$$5$$$ Km Rule! It states: "It's prohibited to have a better car than a general in a $$$5$$$ Km radius", so his Ferrari got towed. Now he has to take the bus home.
His android arch-enemy, D8, is mocking him for this situation, even though he also has to take the bus to go home. Infuriated, Cosenza decides to make a bet to shut D8 up. He bets that, for each bus he has to take while going home, he's able to complete one entire codeforces contest just in the time between getting on the bus and getting out of it. If he takes $$$X$$$ buses to get home, he would have to finish $$$X$$$ contests, one in each bus, and complete each one in the time he spent inside each bus.
The bus routes in this city are such that each route connects only two bus stops, in both directions. Also, the buses always take exactly the same amount of time on the same route, in both directions, and everyone is kicked out of the bus at each stop as soon as it arrives.
D8 likes bets, but he likes even more to win them, so first he asks for your help to see how fast does Cosenza have to be to win the bet. If the wager is accepted, Cosenza can solely go from one station to another using buses. D8 knows that Cosenza may take a longer route home just to win this bet, as long as it's not too long. He will not walk between bus stops even if it means losing his bet. Given the bus routes, can you find the fastest Cosenza has to be in the contests in order to win the bet? In other words, given all possible routes home, find the one with the longest smallest bus section. Notice that given these constraints, it may be impossible for Cosenza to get home.
The first line of the input consists of three integers, $$$N$$$, $$$M$$$ and $$$T$$$ ($$$1 \lt N, M \leq 5 \times 10^5$$$ and $$$0 \lt T \leq 10^8$$$) — the number of bus stops, the number of bus routes, and the longest Cosenza accepts to spend going home, respectively. Consider the worst case scenario, in which there's always the exact bus Cosenza wants waiting for him at the bus stop.
Each of the next $$$M$$$ lines consists of three integers, $$$u$$$, $$$v$$$ and $$$t$$$ ($$$1 \leq u \lt v \leq N$$$ and $$$1 \leq t \leq 5 \times 10^5$$$) — the stops this route connects and the time it takes from one stop to the other.
A single integer, the answer to D8's question when Cosenza's MSI is at bus stop $$$1$$$ and Cosenza's home is at bus stop $$$N$$$. If it's impossible for Cosenza to get home by bus, print "He's taking an uber.".
2 2 100 1 2 1 1 2 10
10
2 2 5 1 2 10 1 2 20
He is taking an uber.
3 3 5 1 2 3 2 3 3 1 3 2
2
The string lecture ended 15 minutes ago. As usual, student Danon is still thinking about it. He likes to come up with weird problems for his professors to solve after the classes. What intrigues him the most on this subject is palindromes. How can a sentence with an arbitrary pattern gain a higher status among other sentences just because humans found it cute!?!?
Danon decides to create his own cute pattern! He defines a cute sentence as a sentence where its first word is an acronym of the whole sentence. This means that the first word should consist of the first letter of each word of the sentence, including itself, in the order they appear, without extra letters.
Now he asks for the professor to show how to code a program that, given a sentence, tells if it's cute or not. But the strings professor is Navarrosaur, who just turned 160 million years old, and has no energy to make this code. Thus, he gives this task to you!
The first line contains a single integer $$$N$$$ ($$$0 \lt N \leq 100$$$) — the number of words in the sentence.
The second line contains $$$N$$$ non-empty strings $$$s_i$$$ ($$$|s_i| \leq 100$$$) — the sentence, separated by spaces.
All the words consist only of uppercase English letters.
Print "Yes" if it's a cute sentence and "No" otherwise.
3 IME MELHOR ENGENHARIA
Yes
2 IME MITO
No
3 ITA TUDO MELHOR
No
5 AMAN MUITO ACIMA NESSA PARADA
No
After working very hard for it, the lovely dynamic duo, made up of Evandro Lins and Hebert Henriques, is finally part of the group that assists the lieutenants at some odd military academy. Due to this being an honor of immense prestige, when the second year students went on an expedition they were assigned the roles of shooting range assistants to a commanding lieutenant.
Like always, the shooting instruction will be performed in an unusual manner. First of all, the lieutenant lines up all of the $$$N$$$ students, side by side, with each person facing their respective target. For some odd reason, during the instruction, both Evandro and Hebert are only able to perform very specific tasks. Evandro is able to quickly find out whether a student in the firing range has enough ammo to fire a specific amount of rounds. Complementarily, Hebert, in some weird way, is able to quickly give bullets to students, however, the caveat is that he's only capable of doing that to a continuous sequence of students in the firing range and giving the same amount to all of them.
With this knowledge, the lieutenant is prepared to proceed with the shooting instruction; $$$Q$$$ commands will be given out to the duo. When he shouts his command, it'll be directed towards Hebert, commanding him to give out bullets to some students. When he's asking something, it'll be directed towards Evandro, asking if a student has enough ammo to fire a specific amount of rounds. If the student has enough ammo, he will be asked to fire them. Everyone begins with $$$0$$$ bullets.
The first line contains two integers, $$$N$$$ and $$$Q$$$ $$$(1 \le N, Q \le 10^5)$$$ — the number of students and the number of commands given out to the duo, respectively.
Each of the next $$$Q$$$ lines represents a command. Each command will start with a character, indicating whether the lieutenant is shouting or asking.
If the character is an exclamation mark !, then three numbers, $$$l$$$, $$$r$$$, $$$x$$$, will follow $$$(1 \le l \le r \le n)$$$ and $$$(1 \le x \le 10^9)$$$ — meaning that Evandro has to deliver $$$x$$$ bullets for the students in positions $$$l$$$ to $$$r$$$.
If the character is a question mark ?, then two numbers, $$$p$$$, $$$x$$$, will follow $$$(1 \le p \le n)$$$ and $$$(1 \le x \le 10^{12})$$$ — meaning that the lieutenant is asking if the student in position $$$p$$$ is able to fire $$$x$$$ rounds. If he's able, he then fires the asked amount.
For each ? query, print yes sir if the student is able to fire the amount asked or negative otherwise.
10 4 ? 7 9 ! 1 10 17 ? 7 9 ? 7 9
negative yes sir negative
5 7 ! 1 5 13 ! 2 3 123832 ? 5 13 ! 1 5 12873 ? 5 1337 ! 1 4 128312 ? 3 278302
yes sir yes sir negative
Everyone is excited for their first bus expedition outside of town, especially because it'll be the first task of everyone's favorite dynamic duo (story for another time). You are the command assistant and thus are responsible for letting the lieutenants aware of how much time is needed to occupy the bus.
The bus has four seats per row, two on each side, and only one entrance, in the front of the bus. It's instructed that, when entering the bus, the student should find the farthest row from the entrance which still has an empty seat. Then, the student should prioritize the window seats, to let the next student seat on the aisle seat. Each student should take $$$2$$$ seconds to cross a row, $$$5$$$ seconds to sit in an aisle seat and $$$10$$$ seconds to sit in a window seat.
It should be an easy task, but there are some introverted students who don't follow the instructions. They instead search for the farthest row from the entrance which still has an empty window seat, in the hopes that they will travel alone. They will still sit on the window seat, leaving the aisle seat available. If there are no window seats left, they will follow the instructions normally. The other students don't know which students are introverted, so they will not avoid sitting next to them. Fortunately, you know which students are introverted, so you should be able to give the correct information to the lieutenants.
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 30$$$) — the number of rows in the bus.
The next line contains a string $$$S$$$ ($$$1 \leq |S| \leq 4 \times N$$$) — the aspect of each student in the order they enter the bus. $$$S_0$$$ is the first to enter. If student $$$i$$$ is an introvert, $$$S_i = I$$$. Otherwise, $$$S_i = E$$$.
Print a single line, the amount of time needed for everyone to sit down, in seconds.
1 IEIE
30
2 IEEI
41
Vasconcelos is the best student in his class, but he is feeling very tired and does not want to go to university anymore. He got a doctor's note by breaking his feet, although it has expired and now he can't skip more classes without being punished.
He still wants to skip the maximum amount of classes, but his university has a strict policy on faulty points. It's considered that every student should love to go to classes even if it's just to stand still for five hours, and thus the students that don't appreciate classes are called faulty. To control them, the faulty point system was created. Each missed period gives a student $$$3$$$ faulty points. If, in one semester, a student hits $$$90$$$ total faulty points or $$$50$$$ faulty points in a same discipline, he's expelled.
Fortunately, to actually receive your faulty points, the professor has to report your absence. Most of the professors are too prehistoric or occupied for this (you can check their stories in other problems). As a matter of fact, there are only two professors that actually report absences. Since they are foreign, students often refer to them as the French and the Dutch professors.
Vasconcelos's classmates already tried convincing him to attend just these professor's classes, but the worst part for him is going to the university. If he already has to go to the university that day, he doesn't mind attending all classes during the day. That's why he decided to make his Faulty Plan. He has no faulty points, there are $$$80$$$ class days left and he'll make a plan to go to the university as little as possible without being expelled.
It's a little tricky to architect his plan because the professors change their weekly schedule all the time, thus your help is required. Your mission, if you choose to accept it, is to find the number of days Vasconcelos can skip class without being expelled.
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 80$$$) — the number of days when there are classes of the French or the Dutch professors.
Each of the next $$$N$$$ lines consists of integers $$$D$$$, $$$P_f$$$ and $$$P_d$$$ ($$$1 \leq D \leq 80$$$ and $$$0 \leq P_f, P_d \leq 10$$$) — the day and the number of periods the French and the Dutch professors lectures that day, respectively. The days will all be distinct and be given in ascending order.
The maximum number of days Vasconcelos is able to skip class without being expelled.
3 1 0 10 2 0 10 3 0 10
78
3 1 6 5 2 5 6 3 5 5
79
Wei is in a delicate situation. He has to get out of his unorganized art university! … for a few months… He got a great internship opportunity, but his university doesn't let him just go. To have some fun, the administration of the university made a deal: if he goes to class everyday and stays completely still for five consecutive hours for a whole semester, he will gain permission to do his internship and come back to finish his studies after the internship.
He did not like this solution, but he had no choice, so he kept this deal while trying to find a way out. It's already the last month of the semester, so Wei tried for the last time. And it worked! …sort off… The administration still wants to have some fun, so they are going to play a game with Wei.
Given a list of students registration numbers, they are going to give a series of queries with registration numbers of the administration. For each query, Wei should respond with the student number which gives the greatest digit modular sum with the administration's number. They defined digit modular sum as the sum digit by digit, taking $$$mod 10$$$. For example, $$$56 + 7 =_{dms} 53$$$, because $$$5 + 0 \equiv 5 \pmod{10}$$$ and $$$6 + 7 \equiv 3 \pmod{10}$$$.
Unfortunately, these are empty promises, because the administration added a rule for the game: Wei has to give a response in $$$1$$$ second! So he basically would have to guess anything. But you won't give up on him! Make him a program to win the administration game.
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$) — the number of students registration numbers given.
Each of the next $$$N$$$ lines contains a $$$6$$$ digit registration number, possibly with leading zeros — the students numbers. All numbers will be different.
The next line contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) — the number of queries.
Each of the next $$$Q$$$ lines contains a $$$6$$$ digit registration number, possibly with leading zeros — the administration numbers.
$$$Q$$$ lines, one for each query — the answers to the game.
2 000001 999999 1 100009
000001
3 123456 654321 162534 3 123456 654321 432165
654321 123456 162534
Andrade and his followers… love to skip their programming classes… to study High Profile Math (HPM)… (it was supposed to be Low Profile Math… but the professor is so good… that his subject got an upgrade… Hmmm…)
They were watching the recorded classes on HPM together when they noticed a pattern: the professor always talks about exactly $$$N$$$ topics and in the middle of each topic he takes a long pause to… apparently do nothing. They were getting bored of studying, so they decided to play a game! Each of Andrade's followers will guess how long one of the $$$N$$$ pauses of their next HPM class will last. Then, Andrade, infamous icoschampion (20 times champion) of the iberoamerican math olympics, has to calculate the expected value for the total pause time of the next class, considering that each pause could last each guessed amount with equal probability. They want to see how close their guesses were.
But Andrade found the task too easy (of course), so, in the HPM spirit, he took his result as an irreducible fraction $$$\frac{p}{q}$$$ and changed it to $$$p * q^{-1} \pmod{10^9+7}$$$, where $$$q^{-1}$$$ is such that $$$q * q^{-1} \equiv 1 \pmod{10^9+7}$$$.
As no one is able to keep up with Andrade, your task is to make a program that checks if Andrade got the right result, even though you know he did. You need to make a fast program, since HPM has lots of topics and Andrade has lots of followers!
The first line contains a single integer $$$N$$$ ($$$0 \lt N \leq 10^5$$$) — the number of topics.
The second line contains a single integer $$$M$$$ ($$$N \leq M \leq 10^5$$$) — the number of Andrade's followers.
The next $$$M$$$ lines contain two integers each, $$$a_i$$$ ($$$0 \lt a_i \leq N$$$) and $$$b_i$$$ ($$$0 \leq b_i \leq 100$$$) — the topic Andrade's $$$i$$$-th follower wants to guess about and the amount of time he guesses, respectively.
There will always be at least one guess for each topic.
A single line consisting of the expected value in the way described.
3 3 1 0 2 100 3 5
105
1 2 1 5 1 10
500000011
Cosenza hates studying. He hates it so much that he can't study on the same day he takes an exam. He developed a method of studying that optimizes his time: for each exam he studies for exactly one full day. As long as he takes a full day to study a single subject, he won't forget it until the exam arrives. But this method is not always possible, as Cosenza sometimes notices too late that the exams are coming. If he is not able to use his method, he's going to cry, and we don't want that! Help him find out if he still has time to study in his weird way.
For the last few months, Cosenza has also been addicted to CSGO. He is on a streak of $$$100$$$ consecutive days playing it daily! He only plays on free days, which are the days without exams and that he doesn't have to study. He doesn't want to lose his streak, so he also wants to know how many more days he can add to his streak if he uses his method of studying.
Remember to make a fast program, as Cosenza's exams can occur for a few centuries.
The first and only line of input consists of a non-empty string $$$S$$$ ($$$0 \lt |S| \leq 10^6$$$) containing only F's and E's — Cosenza's exam schedule. An 'F' represents a free day. An 'E' represents an exam day. There's at least one exam day.
Print a single integer, the number of days Cosenza can add to his streak. If it's not possible to use his method of studying, print "I cry".
EFFFFF
I cry
FFEE
0
FFEEE
I cry
FFFEFFFFFFFFFE
2
After every GRUPODEESTUDOSPARAPROGRAMACAO++ (study group with a catchy name) contest in vjudge, the contest setters, who call themselves "judges", like to check the precision of the contestants. Since Ana Livia always finishes her upsolving in less than a minute and has a big crush on one of the judges, she decided to write a program that tells the total number of submissions of the contest. To get more accurate data, she will actually only count the incorrect submissions on the problems that the contestant eventually got a correct submission.
Unfortunately, the "Rank" section is not working properly, so she is getting her data through the "Status" section. There, she can only see the submissions and its verdict one by one. The submission appears along with the contestants ID, which are all different and between $$$1$$$ and the number of contestants, and the problem ID, which are all different and between $$$1$$$ and the number of problems. The possible verdicts are WA (Wrong Answer), RTE (Run Time Error), TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded) and AC (Accepted, the only verdict to a correct submission).
To impress her secret crush even more, she decided to make a program that counts the submissions for a contiguous range of problems and a contiguous range of contestants, following the order of their IDs. To test her program, she is going to make some queries of ranges to check its response. Can you help her, in the name of love?
The first line consists of two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 500$$$) — the number of contestants and the number of problems, respectively.
The next line consists of a single integer $$$S$$$ ($$$1 \leq S \leq 2 \times 10^5$$$) — the number of submissions.
Each of the next $$$S$$$ lines consists of $$$2$$$ integers $$$C$$$ and $$$P$$$ ($$$1 \leq C \leq N$$$ and $$$1 \leq P \leq M$$$) and a string $$$V$$$ — the contestants ID, the problems ID and the verdict of the submission (WA, RTE, TLE, MLE or AC). The submissions are given in their chronological order. If a contestant gets an AC verdict on a problem, he no longer sends submissions to that problem.
The next line consists of a single integer $$$Q$$$ ($$$1 \leq Q \leq 2 \times 10^5$$$) — the number of queries.
Each of the next $$$Q$$$ lines consists of $$$4$$$ numbers, $$$C_1$$$, $$$P_1$$$, $$$C_2$$$ and $$$P_2$$$ ($$$1 \leq C_1 \leq C_2 \leq N$$$ and $$$1 \leq P_1 \leq P_2 \leq M$$$) — a query to check the number of incorrect submissions until a correct submission from contestant with ID $$$C_1$$$ to contestant with ID $$$C_2$$$ and from problem with ID $$$P_1$$$ to problem with ID $$$P_2$$$.
For each query, print one line with the response of Ana Livia's program.
2 2 7 1 2 AC 2 2 WA 2 2 AC 2 1 RTE 2 1 TLE 2 1 TLE 2 1 AC 2 1 1 2 2 1 2 2 2
4 1
3 3 21 1 3 MLE 1 3 AC 1 2 WA 1 2 WA 1 2 WA 1 2 WA 1 2 WA 1 2 WA 1 2 WA 1 2 AC 2 1 MLE 2 1 MLE 2 1 MLE 2 1 AC 2 2 AC 3 2 TLE 3 2 TLE 3 2 TLE 3 2 TLE 3 1 AC 3 3 AC 2 1 2 3 3 3 1 3 3
8 0