The military command structure at the Institute of Many Experts (also known as IME) is one of the most renowned in its neighborhood! As such, the people that compose it must also maintain quite a high level of intellectuality, but since it's been over twenty years since they've been in power, it's time for a change! Luckily, since you're really good at doing computer stuff, the old guard has chosen you to help them figure out how to do it.
They give you the following information: there are $$$n$$$ colonels to choose from, and the command is composed of $$$k$$$ highly specialized people. In addition to this, you receive the IQ values from each of these $$$n$$$ colonels, as there's a special restriction to maintain this high standard: the sum of the IQs of the $$$k$$$ chosen colonels must not exceed $$$100$$$. Because of this, there are many ways to choose these $$$n$$$ colonels, and the current commander becomes too numb from the options to figure out what to do. As such, you're now tasked to figure out how many ways you can choose the $$$k$$$ colonels that fit the criteria. Note that due to their mental prowess, some may have negative IQ values!
Such are the inner-workings of someone part of the command. The first line contains two integers, $$$n$$$, $$$k$$$, $$$(1 \leq n \leq 66)$$$, $$$(1 \leq k \leq n)$$$ — the amount of colonels to choose from and the size of the command structure.
The second line contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-100 \leq a_i \leq 100)$$$ — the IQ of the $$$i^{th}$$$ colonel.
Output a single integer: the amount of ways to choose the $$$k$$$ colonels!
10 530 40 -10 23 58 29 44 -100 -70 10
200
7 3-100 -100 -100 -100 -100 -100 -100
35
Asp Of R/2 Braga is eager to graduate from the Institute of Mysterious Experiments, also known as IME, and he realized that there are only 193 days until graduation!
Also, he realized something even more interesting:
$$$193$$$ is prime.
There are $$$43$$$ prime numbers in the range $$$[2, 193)$$$.
$$$43$$$ is prime.
There are $$$13$$$ prime numbers in the range $$$[2, 43)$$$.
$$$13$$$ is prime.
There are $$$5$$$ prime numbers in the range $$$[2, 13)$$$.
$$$5$$$ is prime.
There are $$$2$$$ prime numbers in the range $$$[2, 5)$$$.
$$$2$$$ is prime, and the sequence is finished now as $$$2$$$ is the lowest prime number.
His brain is melting with this fascinating discovery and he decided to call this day beautiful.
Now he wonders which days could also be considered beautiful. So he asks you $$$q$$$ questions, each of them a number $$$n$$$, wondering if $$$n$$$ can be considered a beautiful day or not.
The first line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the amount of questions that Braga asks.
The next $$$q$$$ lines will contain a single integer $$$n$$$ $$$(2 \leq n \leq 10^7)$$$ — the day that Braga wonders is beautiful or not.
For each question, print out YES if it's a beautiful day and NO otherwise.
You may output each letter in any case (lowercase or uppercase). For example, the strings yEs, yes, Yes, and YES will be accepted as a positive answer.
711815519334357
YES NO YES NO YES YES NO
Colonel Tree, one of the most renowned teachers at the Institute of Meticulous Engineering, commonly referred to as IME, is currently facing a rather serious conundrum: he has been given a student list with names he doesn't recognize! Luckily, he somehow remembers the original names of the students, and so he must figure out potential students who could have altered his list. He decides that they'll be those whose names appear incorrectly in the list given to him. When a student has supposedly altered a name, they'll swap some characters around, remove some, or even add some. Of course, there are no students whose names are the same, and if a student edits a name on the list, they make sure that it won't conflict with any other name on the list.
However, since his wife has decided that he has been spending too much time in the institute babbling about computers, he has to leave and has chosen you to help him out. Once he comes back to the institute, he'd like to know the names of the suspects! Given both the original list and the altered one, help him out, please!
The first line contains an integer $$$n$$$, $$$(1 \leq n \leq 10^4)$$$ — the number of students in the list.
Each of the next $$$n$$$ lines will contain a string $$$s$$$ $$$(3 \leq |s| \leq 30)$$$ — the name of the students in the list.
Each of the next $$$n$$$ lines will contain a string $$$s$$$ $$$(3 \leq |s| \leq 30)$$$ — the names present on the altered list.
These strings will contain only lowercase letters of the English alphabet and may contain spaces only between letters.
Output the number $$$k$$$ — the number of students that are potential suspects.
On each of the next $$$k$$$ lines, print the original names of the suspected students. You must print these names in lexicographical order and they need to be separated by a line, as Colonel Tree likes to be very organized with his stuff.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
- $$$a$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$.
- In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter of $$$b$$$.
6pedro bulcaojoao cameloebert henriquelaxecalheirosivo linivo linkemellebert balaopedro balcaolaxscarvalheiros
5 calheiros ebert henrique joao camelo laxe pedro bulcao
At the Institute of Maximum Efficiency, otherwise known as IME, we must honor those who come before us as they have built the path through which we walk. The person of highest honors, of course, is the general of the institution, who is the one responsible for making the toughest decisions in order to run the institution with maximum efficiency. As he is oh so important, there have to be certain references to him in every minute detail in this grandiose institute!
Suddenly, on one fine Wednesday afternoon, at around $$$14:00$$$, the general decided to run a contest: let's figure out who can make the most beautiful graph of all time! Some random criteria were established that fit his own needs; however, there were too many graphs submitted for the contest as everyone at the institute voluntarily participated in this event. As such, he decides, for some reason, that you're the most fit person to help him filter out the graphs. One of the criteria that you think will filter out the largest amount of graphs is doing the g inside of a graph. That being, if a graph has a g as a subgraph, then it will be automatically passed on to the next phase of this contest. Of course, only a select amount of students at the institute will have the intellectual power to create such a graph.
A graph has a g as a subgraph if you're able to find a simple cycle of length 4 and then have a tail of size $$$2$$$, because the general saw that if you rearrange these edges in a certain way, it looks like a g, a g for general, of course! A tail in this case is a path of length $$$2$$$ that starts in any vertex of the cycle and doesn't intersect it.
Here you can see two graphs; the one on the left has done the g, while the one on the right hasn't. The first line contains an integer $$$t$$$, $$$(1 \leq t \leq 100)$$$ — the number of graphs that the general will give to you.
The first line of each test case consists of two integers, $$$n$$$, $$$m$$$ $$$(1 \leq n \leq 3 \times 10^3)$$$ $$$(0 \leq m \leq \min(10^6, \frac{n \times (n - 1)}{2}))$$$ — the amount of nodes and edges in the given graph.
The next $$$m$$$ lines of each test case consist of two integers, $$$a$$$, $$$b$$$ $$$(1 \leq a, b \leq n)$$$, $$$(a \neq b)$$$ — indicating that nodes $$$a$$$ and $$$b$$$ are connected. Note that the graphs do not contain multi-edges nor loops.
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3000$$$.
For each test case, print out YES if you're able to do the g and NO otherwise.
You may output each letter in any case (lowercase or uppercase). For example, the strings yEs, yes, Yes, and YES will be accepted as a positive answer.
28 101 21 32 42 54 55 62 33 63 77 88 121 21 31 42 32 43 45 65 75 86 76 87 8
YES NO
Mr. Cokeman is a terrifying figure who roams the halls of the Institute of Mysterious Experiments (IME). It is said that he does unspeakable things to those who stand in his way, but nothing enrages him more than seeing someone in the corridors without their IME badge. If he catches you without it, he'll unleash an ancient forbidden curse known as FATD, and you'll perish instantly.
IME is a rectangular grid of size $$$N \times M$$$ represented by a matrix $$$A$$$. Each element $$$a_{ij}$$$ of the matrix $$$(1 \leq i \leq N, 1 \leq j \leq M)$$$ is an ASCII character and represents the tile $$$(i,j)$$$ of the grid. You start at tile $$$(1, 1)$$$ and must reach the exit at $$$(N, M)$$$. Unfortunately, you left your badge behind at some tile $$$(X, Y)$$$.
Mr. Cokeman walks through IME on a known, fixed route — a connected path of adjacent* tiles, where each tile appears only once in the path. While you don't know where he is at any given moment, stepping on any tile from his route without your badge is certain death. With the badge, you're safe.
You have two options:
- Go straight to the exit, avoiding any tile on Cokeman's route.
- Retrieve your badge at $$$(X, Y)$$$ first, and then proceed safely to the exit—this allows you to walk through his route.
Considering each move to an adjacent tile takes exactly 1 second, determine the time of the path with minimum time to reach the exit safely. If it's not possible, print -1.
Note that the path of minimum time until the exit must not contain tiles located out of IME's grid.
______________________________
* Two tiles $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$ are considered adjacent if and only if $$$|i_1 - i_2| + |j_1 - j_2| = 1$$$.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) — the number of rows and columns.
The next $$$N$$$ lines each contain a string of length $$$M$$$ representing IME's grid. The $$$j$$$-th character of the $$$i$$$-th string contains the corresponding character of the tile $$$(i,j)$$$.
Each character is either:
- . — a floor tile you can walk on
- # — a wall tile you cannot walk through
- B — the tile where the badge is located (also treated as floor)
- X — a tile that is part of Mr. Cokeman's route where there is at most one B tile and X tiles form a path of adjacent tiles.
Output a single integer — the minimum time in seconds to safely reach the exit at $$$(N, M)$$$ from $$$(1, 1)$$$, considering the rules. If it is not possible, output -1.
5 5...B..X...#X###.X........
12
5 5...B..X....X###.X........
8
5 5.X..B.X...#X###.X........
-1
At the Institute of Messy Etiquette, known more commonly as IME, people have been suspecting that some fraud has been occurring since the commander has for some time been announcing several budget cuts to his own faculty while at the same time funding his own expensive vanity projects. You quickly mention this one time to some people well connected with the higher ups, and on one fine Wednesday afternoon, the two most respected colonels of the entire institute go have a quick word with you.
Dwart and Delphine figure out that if they cahoot against the commander and figure out something fishy, then a power shift can happen. Turns out that they have been binging the YouTube channel Numberphile quite a lot recently and stumbled upon a video about Benford's Law. The law is an observation that in many real-life data sets of numerical data, the leading digit is likely to be small. Upon further research, they see that Wikipedia states that: Based on the plausible assumption that people who fabricate figures tend to distribute their digits fairly uniformly, a simple comparison of first-digit frequency distribution from the data with the expected distribution according to Benford's law ought to show up any anomalous results.
Now possessed with this knowledge, both colonels have been able to somehow get their hands on a dataset containing $$$n$$$ numbers pertaining to costs associated with running the institute. They feel as if they've done too much, and now they rely on your help in order to figure out whether the suspicions are true. Given the dataset, figure out whether it's plausible that some fraud is occurring. Since they just want to know if it can be ruled out or not, you need to figure out, within this data set, whether the number $$$1$$$ appears as the leading significant digit more than any other digit.
The first line of the input contains a single integer, $$$n$$$ $$$(1 \leq n \leq 2 \times 10^6)$$$ — the amount of elements in the dataset.
The second line contains $$$n$$$ integers $$$a_i$$$ $$$(-10^{18} \leq a_i \leq 10^{18})$$$ — numbers present in the dataset.
If you think that it's plausible that the dataset was manipulated, output suspicious in a single line; otherwise, output unfortunately not.
599999999999 999999999999999 -99999999999 9999999999 420
suspicious
1038123 2118328 11273 -44884 18381238 99484832 -664361 87372 777372 -588382
unfortunately not
Lieutenant Bigolin is a true mathematical prodigy and cannot comprehend those who don't understand polynomials. He was soon assigned to be the leader of the fifth year students at the Institute of Methodical Extortion, also referred to as IME. In this position, he did something mischievous: he converted every student record into algebraic challenges!
However, you are found to be torando (which in Brazilian military jargon means sleeping, but can also mean something else...) when Captain Icarus Mandrade wakes you up shouting. Since you are torando, you are now assigned to be the leader of the fifth year students and must take into account everything that Bigolin was doing.
You have 4 seconds to hand me a list of every student's aim-correction angle or you'll be toast!, shouted the Captain.
Panicking, you open the only file available (a plain-text note) and find $$$t$$$ monic polynomials written line after line. In an instant, you realize that the real roots of these $$$t$$$ polynomials are precisely every student's aim-correction angle (in degrees). You remember also from the aiming lesson that each angle is in the range $$$[-30^\circ, 30^\circ]$$$ and that no two students' angles were more than $$$0.5^\circ$$$ close.
Figure this out before you are toast!
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the amount of polynomials found in the notepad.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 8)$$$ — the degree of the polynomial.
The second line of each test case contains $$$n + 1$$$ real numbers $$$(a_0, a_1, ..., a_n)$$$ $$$(-10^{17} \leq a_i \leq 10^{17})$$$ — the coefficients of the polynomial from the lowest degree $$$0$$$ to the highest degree $$$n$$$. Each real number will be given up to 8 decimal digits. That is, the polynomial is equal to the sum of $$$a_i \times x^i$$$ for $$$i$$$ from $$$0$$$ to $$$n$$$. It is guaranteed that the roots fall within the range $$$[-30, 30]$$$ and that the roots are at least $$$0.5$$$ apart.
For each test case, output $$$n$$$ sorted real numbers in a single line — the roots of the polynomial. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$, that being if your answer is $$$a$$$ and the jury's is $$$b$$$, then the judge will check if $$$\frac{|a - b|}{max(1, b)} \leq 10^{-6}$$$.
22-5 -13 404942 -9398 -939 81 8
-0.22660959 0.55160952 -10.99056762 -10.01322889 0.09925818 10.77953821
257138.2900 1927.17 -2082.05 -500.245 -3.141592 2.718282-589.241 29.2085 69
-9.25042868 -5.46170789 -1.74924898 1.88924450 15.72786874 -3.14159149 2.71827978
Pedro Vieira is a very dedicated student, and of course calculus is his favorite subject due to the eloquence of his teacher — Mr. Calvodecria. One of the many things he learned about during class was about the heaviside step function, a very important part of differential calculus. One day, Vieira is bored during class and begins messing around with a really large random number generator and for some reason he decides that he wants to know the value of the heaviside function of this number.
Note: The heaviside function is defined as follows: if $$$x \geq 0$$$, then $$$H(x) = 1$$$, otherwise $$$H(x) = 0$$$.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the amount of numbers that Vieira generates.
The next $$$t$$$ lines will contain a single integer $$$x$$$ $$$(-10^{1000} \lt x \lt 10^{1000})$$$ — the number that Vieira randomly generated.
For each number, print out the value of the heaviside function per line.
440-2-2295581114772677443166103318377836
1 1 0 0
Mr. G is a mindful visionary who has led the International Merchandising Enterprise (IME) for many years with great success. Now, under the ambitious IME1000 expansion project, he plans to open a new branch in one of the cities across the country.
There are $$$N$$$ cities connected by $$$M$$$ bidirectional roads. The IME headquarters is located in city $$$1$$$, and all other cities (from $$$2$$$ to $$$N$$$) are candidates for the new branch. If IME opens a branch in some city $$$i$$$, Mr. G will profit $$$v_i$$$.
However, travel isn't free. Every road has a tax $$$w_i$$$ charged per traversal. Fortunately, Mr. G is not just a businessman; he's also a master of reputation management. Every time Mr. G successfully enters a new city and pays the road tax, the citizens and local officials admire his discipline and honor. This admiration manifests as 1 unit of reputation. Thus, each taxed road he passes through increases his total reputation by $$$+ 1$$$.
Once his reputation reaches $$$k$$$, he becomes so respected and trusted that now he has the option to deceive the tax collectors and pass through some road without paying any tax at all, or he can decide to continue paying taxes and increase his reputation normally. However, the moment he uses this "reputation bypass," the news of his deception spreads, and trust is lost. Then his total reputation resets to $$$0$$$, and he must start rebuilding it from scratch by paying taxes again.
However, Mr. G's reputation plays a role not only in reducing travel costs but also in expanding his business. He can only open a new IME branch in a city if he arrives there with a reputation of at least $$$k$$$. If his reputation is lower upon arrival, the local officials remain unconvinced of his trustworthiness, and the opportunity is lost.
Your task is to determine which city (among cities $$$2$$$ to $$$N$$$) Mr. G should choose to open the new branch in order to maximize his net profit. The net profit is calculated as the city's profit value $$$v_i$$$ minus the total amount of taxes paid to reach that city from headquarters (city $$$1$$$), using the optimal use of reputation bypasses along the way. If there is no city that Mr. G can reach with a positive net profit and a reputation of at least $$$k$$$, output $$$-1$$$.
The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$2 \leq N \leq 10^5, 1 \leq M \leq min(10^5,\frac{n \cdot (n-1)}{2}), 1 \leq K \leq 20$$$) — the number of cities, the number of roads, and the required reputation to open a branch.
The second line contains $$$N - 1$$$ integers $$$v_2, v_3, ..., v_N$$$, where $$$v_i$$$ is the profit Mr. G will obtain by opening a branch in city $$$i$$$ ($$$2 \leq i \leq N$$$) ($$$0 \leq v_i \leq 10^9$$$)
Each of the next M lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq N, 1 \leq w_i \leq 10^9$$$) — indicating a bidirectional road between cities $$$u_i$$$ and $$$v_i$$$ with a tax cost of $$$w_i$$$.
Print a single integer — the maximum positive net profit Mr. G can obtain by opening a branch in a city reachable from city $$$1$$$ with reputation $$$\ge K$$$. The net profit is calculated as the city's profit value minus the total tax paid along the path.
If there is no such city, print -1.
6 9 210 10 50 50 501 2 31 3 102 3 62 4 93 4 63 5 154 5 54 6 45 6 8
38
6 9 25 5 10 10 101 2 31 3 102 3 62 4 93 4 63 5 154 5 54 6 45 6 8
-1
Lieutenant Johannes and Hamilton are one of the most well decorated math students in their entire country! They somewhat enjoy discussing very particular algorithms with each other, and on one fine Wednesday afternoon, they decided to play some nerdy game. It goes like this: Lieutenant Johannes gives Hamilton an array and decides to ask a couple of questions about it. Each question has a similar structure; he asks Hamilton to figure out the value of the largest subarray sum of some particular range that he chooses of the original array. Seems easy, doesn't it? In order to challenge Hamilton even further, in between questions, he'll remember that the original array is a bit different and modifies a certain element within it.
However, recently Hamilton has been feeling very sick and so isn't able to think very straight, so he asks you to think for him as these types of games, in his opinion, are too trivial to expend energy thinking about.
The first line of the input contains two integers, $$$n$$$ and $$$q$$$, $$$(1 \leq n \leq 10^6)$$$, $$$(1 \leq q \leq 10^6)$$$ — the size of the array and the amount of questions Johannes asks.
The second line contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-10^{12} \leq a_i \leq 10^{12})$$$ — the elements that Johannes gives to you.
The next $$$q$$$ lines will contain information about the $$$i^{th}$$$ question done by Johannes. Each line will start with an integer $$$t_i$$$, $$$(1 \leq t_i \leq 2)$$$ — the type of query.
- For $$$t_i = 1$$$, 2 integers, $$$p$$$ and $$$x$$$, $$$(1 \leq p \leq n)$$$, $$$(-10^{12} \leq x \leq 10^{12})$$$ — the position where Johannes modifies the array and the value that replaces it.
- For $$$t_i = 2$$$, 2 integers, $$$l$$$ and $$$r$$$, $$$(1 \leq l \leq r \leq n)$$$ — the range in which Johannes wants to figure out what is the largest subarray sum within it. It is guaranteed that there's at least one query of this type.
For every query in which $$$t_i = 2$$$, print out the largest subarray sum in the range $$$[l, r]$$$.
7 317 9 4 -2 0 -12 382 3 71 5 32 2 6
38 14
The auditorium of the Institute of Mathematical Enlightenment, commonly known as IME, is the place where the greatest minds come together in order to provide exceptional lectures to the unwashed masses. Of course, the one who expels the greatest knowledge per word is our dear leader, the commander, who is one whose maximum happiness must be achieved.
So what happens is the following: over the course of the commander's exceptionally short one hundred year reign, he gives out $$$m$$$ lectures to his own dear students. At the end of each lecture, two students (not necessarily distinct) out of the $$$n$$$ watching the lecture are voluntarily chosen to ask a question at the end of the fabulous lecture and to thank him for the once-in-a-lifetime opportunity of being the recipients of such critical information.
We can say that the happiness of the commander is directly related to these two students who are chosen at the end; it is known for a fact that each student has a happiness value associated with them, and the commander's happiness is the values of the two students multiplied. As multiple lectures happen along his tenure, his total happiness ends up being the sum of his happiness after each one. However, it is also known that the commander really dislikes when the same ordered pair of students is chosen twice, so if a pair $$$(i, j)$$$ is chosen to respectively ask and thank, they can't be chosen in the same order again in a later lecture, but if the pair $$$(j, i)$$$ is chosen, then the commander won't notice the difference and as such won't dislike, unless, of course, $$$i$$$ and $$$j$$$ are the same person.
Under these circumstances, given all of this information in advance, you must figure out the maximum happiness of the commander at the end of his term.
This is a mere illustration of something. The first line contains two integers $$$n$$$, $$$m$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$ $$$(1 \leq m \leq n^2)$$$ — the amount of students watching the lectures and the amount of lectures.
The next line contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(1 \leq a_i \leq 10^{4})$$$ — the happiness value associated with each student.
Output a single integer — the maximum happiness value that the commander can have after the $$$m$$$ lectures.
8 1019 23 11 14 3 8 1 44
8361
Clearly, the $$$10$$$ best pairs to choose are:
$$$(a_8, a_8)$$$ –> $$$44 \times 44 = 1936$$$
$$$(a_8, a_2)$$$ –> $$$44 \times 23 = 1012$$$
$$$(a_2, a_8)$$$ –> $$$23 \times 44 = 1012$$$
$$$(a_8, a_1)$$$ –> $$$44 \times 19 = 836$$$
$$$(a_1, a_8)$$$ –> $$$19 \times 44 = 836$$$
$$$(a_8, a_4)$$$ –> $$$44 \times 14 = 616$$$
$$$(a_4, a_8)$$$ –> $$$14 \times 44 = 616$$$
$$$(a_2, a_2)$$$ –> $$$23 \times 23 = 529$$$
$$$(a_8, a_3)$$$ –> $$$44 \times 11 = 484$$$
$$$(a_3, a_8)$$$ –> $$$11 \times 44 = 484$$$
The sum of the products is $$$8361$$$.
It was a bright morning at the Institute of Monkey Entertainment (also known as IME) when your favorite instructor of the Center of Annoyance (CA) selected you (through a totally random and unquestionably fair selection process) as the new Duty Scheduler.
For the next $$$T$$$ days, you're responsible for scheduling the daily duty roster: the schedule that determines which unfortunate student must pull duty and stand watch over some mysterious and highly classified location known as Ala.
There are $$$N$$$ students, numbered from $$$1$$$ to $$$N$$$.
- On day $$$1$$$, student $$$1$$$ pulls duty.
- On day $$$2$$$, student $$$2$$$ pulls duty.
- On day $$$N + 1$$$, it wraps back.
Hey, I'm baixado now and can't pull duty for the next $$$x$$$ days. Take me off the list!
If someone gets baixado on day $$$d$$$ for $$$x$$$ days, they are taken off from the list immediately, and their turn is skipped to the next person still on the list. Then, on day $$$d + x$$$, they return to their original position on the list. Keep in mind someone can still stay baixado after the period of $$$T$$$ days, and everyone can be baixado at the same time, so the list would be empty. It is guaranteed only active people will ask to become baixado. If the list is empty (because too many people were baixado) and if some people return to the list on the same day, it'll restart normally beginning with the student with the lowest identification number.
You must now manage this chaos for the next $$$T$$$ days of scheduling while also handling $$$Q$$$ unpredictable queries from people who think you're a walking calendar. Your goal is to determine, for each day from $$$1$$$ to $$$T$$$, which person is going to pull duty on that day.
Will you rise to become the Legendary Duty Scheduler of CA? Or will you break down like every poor soul before you?
The first line contains three integers $$$N$$$, $$$T$$$, and $$$Q$$$ $$$(1 \leq N, T, Q \leq 2 \cdot 10^5, Q \leq \lfloor T/2 \rfloor \cdot N)$$$ — the number of students and the number of queries. The next $$$Q$$$ lines describe the queries in the following format:
- $$$d$$$ $$$p$$$ $$$x$$$: On day $$$d$$$, student $$$p$$$ tells you they cannot pull duty for the next $$$x$$$ days, starting from day $$$d$$$ $$$(1 \leq d \leq T, 1 \leq p \leq N, 1 ≤ x ≤ 10^9)$$$.
Output $$$T$$$ integers in a single line, indicating the student that is going to pull duty on each day. If there is no student to pull duty on such a day, print -1.
5 5 21 2 22 3 1
1 4 5 1 2
5 15 37 3 15002 2 51 1 20000
2 3 4 5 3 4 5 2 4 5 2 4 5 2 4
10 30 106 4 38 8 34 7 56 1 911 4 52 5 616 1 39 2 311 3 39 9 3
1 2 3 4 6 8 9 10 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 1 2 3 4 5
In the first sample, 2 is off from day 1 to day 2 and 3 is off only on day 2. So the list starts with but on the second day the next available is 4 and then 5 on day 3. It cycles back to 1 and then 2 on day 5.
On the second sample case, 3 is off from day 7 to day 1500, meaning he is not returning on any day until day 15. 2 will be off from day 2 to day 6, and 1 will be off on all days until 15. The list cycles without 1 until day 5, in which 2 is out. Then the list goes on until day 8, in which 3 is out too. Here, 2 is already back and the list repeats the cycle [2, 4, 5] until the end of day 15.