Danaland is a very typical country: it consists of $$$N$$$ cities, each identified by a distinct number. These cities are connected by $$$M$$$ unidirectional roads, where each road has a name.

Ananna is a bright little girl who lives in Danaland. Unfortunately, she was born with a terrible disease: she can only read backwards. After being a victim of terrible bullying by her peers, or, as Ananna calls them, sreep, she found solace in palindromes: words that are the same when read backwards.

Ananna's mom, Eeve, is trying to help her with her condition. One way she helps is by taking her on road trips. A road trip is a sequence of roads that starts at some city $$$U$$$ and ends at a different city $$$V$$$; the same road may appear more than once.

While on a road trip, Eeve asks Ananna the first letter of each road name, so she can practice looking at the start of words. This is, obviously, a source of great anxiety to Ananna, so to avoid having a kcatta cinap, Eeve always makes sure that the sequence formed by taking the first letter of each road's name, in the order they are traversed, is a palindrome.

Eeve is now looking at a map of Danaland, and she wonders: How many distinct pairs of cities $$$U, V$$$ exist such that Eeve can take a road trip from $$$U$$$ to $$$V$$$?

Alex is coaching the famous Brazilian FootXOR Club. For today's training, they want to organize a match between two teams selected from the $$$N$$$ club members. To ensure a fair match, the two teams must be balanced.

Each club member has a set of abilities represented as a $$$K$$$-digit binary string. Each digit corresponds to a characteristic that the player may or may not have. Surprisingly, it is not the quantity of players having each characteristic that matters when deciding whether two teams are balanced: the important thing is the parity of that quantity.

Two teams are considered balanced if they have the same number of players and the bitwise XOR of the ability strings of all players in the first team is equal to the bitwise XOR of the ability strings of all players in the second team. Of course, each club member can only be assigned to at most one team and, for a match to happen, teams cannot be empty.

Alex is really busy right now. As their coaching assistant, you must determine how to assign players to the two teams. If it is impossible to fulfill the coach's conditions, you must inform the coach accordingly.

It was your first time visiting Salvador, and you made the rookie mistake of sleeping on the beach. You woke up red, sunburned, and frankly, humiliated. Swearing vengeance against the sun and all its terrible consequences, you decided that your next vacation would be somewhere with a real winter – like Yakutsk, Russia, where the average temperature is $$$-42^{\circ}$$$ Celsius.

But you came prepared! You brought a warm, cozy coat. The coat is perfect, it warms you very well. Maybe too well, as you get sweaty and the coat gets dirty after $$$C$$$ days of use. Since your trip lasts more than $$$C$$$ days, you must find a way to avoid walking around smelling bad.

To do so, when the coat gets dirty, you cannot wear it until it is washed, but you may also choose to wash it earlier. On any day you do not wear the coat – whether because it is dirty or being washed – you must endure the day's temperature without its protection. After being washed, the coat is fresh and ready to be worn again. At the start of your trip, the coat is clean.

Given the daily temperatures in Yakutsk for the duration of your trip, you must determine the lowest temperature on a day when you are forced to be without your coat, assuming you schedule wash days optimally to make this temperature as high as possible.

Alice is moving to the city of Nlogonia, and to decide where to live, she is evaluating the safety of the city.

Nlogonia is a planned city with $$$N$$$ intersections, numbered from $$$1$$$ to $$$N$$$, and $$$M$$$ streets. Each street connects two intersections bidirectionally. It is guaranteed that any intersection can reach all other intersections using the streets, and no two streets connect the same pair of intersections.

The government of Nlogonia publishes a danger rating $$$D_i$$$ for each intersection $$$i$$$. However, Alice thinks these ratings are insufficient because she wants to assess the safety of moving through the city, not just where she lives. So, she developed her own way to measure how dangerous the city is.

For any given path in the city, Alice defines its path risk as the maximum danger rating among all intersections on that path, including its endpoints. The risk factor between two intersections $$$U$$$ and $$$V$$$, denoted as $$$f(U,V)$$$, is the minimum possible path risk among all paths connecting $$$U$$$ and $$$V$$$. By definition, the only path from an intersection $$$U$$$ to itself is the trivial path containing only $$$U$$$, so we have $$$f(U, U) = D_U$$$. Finally, she assigns a danger score to each intersection $$$U$$$, denoted as:

$$$$$$S_U = \sum_{V=1}^{N} f(U,V)$$$$$$

In other words, the danger score of an intersection $$$U$$$ is the sum of its risk factors to every intersection in the city.

Computing these danger scores for all intersections is not easy, so Alice asks for your help!

The Treeland subway system consists of $$$N$$$ stations connected by $$$N - 1$$$ bidirectional tunnels. The tunnels are arranged in such a way that it is always possible to travel between any two stations. The system is already considered to be the most efficient in the country: there are trains between every pair of stations in the system.

Alejandro, from the subway improvement department, has been tasked with making the system even better and more attractive for passengers and businesses. To that end, the department collected $$$P$$$ proposals from companies. Each proposal is either to sponsor some station (basically, add a sign with the name of the company on the station), or to open a business at some station (a restaurant, a store, or anything like this). Notice that there is no restriction on the number of proposals that can be accepted for each station.

Companies willing to open businesses in the system, though, informed that they will withdraw their proposals unless the station $$$X$$$ where their business is located, is either a sponsored station or there is a train between two sponsored stations that goes through $$$X$$$. Of course, Alejandro does not want to select proposals that will later be withdrawn. Thus, he will make sure to select a set of proposals such that no proposal in the set will be withdrawn. He calls such a set a valid set of proposals.

The figure below shows sponsored stations in red/dashed circles and businesses in blue/dotted circles. The set of proposals in (a) is valid because the business proposal for station $$$3$$$ is located exactly on the path between the two sponsored stations $$$2$$$ and $$$4$$$. The set of proposals in (b) is also valid, because the business proposal for station $$$1$$$ is located exactly on a sponsored station. On the contrary, the set of proposals in (c) is not valid: even though the business proposal for station $$$3$$$ is located on a path between two sponsored stations, the business proposal for station $$$5$$$ is not.

(a) Valid		(b) Valid		(c) Not valid

To choose a valid set, Alejandro took the $$$P$$$ proposals (each one described on a piece of paper), and numbered them from $$$1$$$ to $$$P$$$. Now he wants to select a contiguous range of proposals that form a valid set. More precisely, he wants to pick two integers $$$i$$$ and $$$j$$$, with $$$1 \leq i \leq j \le P$$$, such that proposals $$${i}, {i+1}, \ldots, {j}$$$ form a valid set; besides, he wants the set to be as large as possible. Alejandro is not sure about which should be the initial proposal $$$i$$$ in the range he will select. Help him compute for each $$$i$$$ from $$$1$$$ to $$$P$$$, the size of the largest contiguous range of proposals that form a valid set, starting at proposal $$$i$$$.

During a festival, advertisement signs are added to and removed from a stage at different moments. Each sign has a rectangular shape and is placed perpendicular to the ground, with one side resting firmly on the ground.

A webcam is livestreaming the festival, showing a 2D image of the stage. In this image, the bottom border corresponds to the ground. Each sign covers a rectangular area in the image. A sign is described by an interval $$$[A,B]$$$ and a height $$$H$$$, meaning it covers all points $$$(x,y)$$$ of the image where $$$A \leq x \leq B$$$ and $$$0 \leq y \lt H$$$.

Note that the sign covers the points on the bottom and side borders of the rectangle, but not the top border. Besides, rectangles representing different signs may overlap.

During the livestream, the manager will make several queries at different moments. Each query specifies an interval $$$[L,R]$$$, and asks for the minimum height $$$y \ge 0$$$ among all uncovered points $$$(x,y)$$$ with $$$L \leq x \leq R$$$, with $$$x$$$ and $$$y$$$ being real numbers.

Your task is to write a program to process a sequence of $$$N$$$ events: sign additions, sign removals, and queries about the minimum uncovered height over a given interval.

As an example, consider the following sequence of $$$N=7$$$ events given in chronological order (see picture below):

• Sign with $$$[A,B]=[2,5]$$$ and $$$H=3$$$ is added.
• Sign with $$$[A,B]=[4,7]$$$ and $$$H=5$$$ is added.
• Query $$$[1,10]$$$ is made. The answer to this query is $$$0$$$. An uncovered point with minimum height within the interval is, for instance, the point with coordinates $$$(1.5, 0)$$$.
• Query $$$[2,7]$$$ is made, with answer $$$3$$$.
• Query $$$[4,5]$$$ is made, with answer $$$5$$$.
• Second added sign is removed.
• Query $$$[4,5]$$$ is made, with answer $$$3$$$. Note that the removal of the second added sign changed the answer of query $$$[4,5]$$$.

If you've ever played Tetris for long enough, you might have experienced the Tetris effect – seeing falling blocks even after you have stopped playing. To stay focused on solving problems and avoid such distractions, we will consider a simplified version of the game.

The game is played on a board composed of square cells arranged in a grid. Columns of the grid are numbered sequentially from left to right. The board is infinite to the right and to the top. Each cell is either empty or filled, and initially, all cells are empty.

A sequence of $$$N$$$ rectangular pieces is given, and the pieces are dropped onto the board one at a time. Pieces have different sizes. A piece of size $$$L$$$ is either vertical ($$$L \times 1$$$ cells) or horizontal ($$$1 \times L$$$ cells). When a piece is dropped at a specified column, it starts at a location above all the currently filled cells and falls straight down until it either reaches the bottom of the board or lands on top of an already filled cell. Once a piece lands, it fills its final set of cells.

Each time a piece lands, the game is considered safe if no empty cell has a filled cell above it; otherwise the game is unsafe, the offending piece is removed from the board, and the game continues with the next piece as if it had never been dropped.

In the example below, corresponding to the first sample input, the game becomes unsafe once the second piece lands, hence the piece is removed and the next pieces keep the game safe.

Given the sequence of pieces and their drop positions, your task is to determine, for each piece, whether it makes the board unsafe after landing.

Ricardo is a restaurant critic, which means he spends his time eating at restaurants and giving them a rating. Each rating is an integer number of stars between $$$0$$$ and $$$3$$$, inclusive. Thus, there are exactly four possible ratings.

During his visit to Cheapland, he must review $$$N$$$ restaurants. Unfortunately, all of them are terrible, and if left to his honest opinion, Ricardo would give $$$0$$$ stars to every restaurant. However, the government of Cheapland can bribe Ricardo to increase the rating of any restaurant.

Each restaurant has its own bribe costs, which depend both on the restaurant itself and on the number of stars awarded. Bribing Ricardo to give a restaurant $$$3$$$ stars is always more expensive than bribing him for $$$2$$$ stars, which in turn is more expensive than bribing him for $$$1$$$ star. Naturally, no payment is required for a $$$0$$$-star rating.

As one might imagine, the Cheapland government wants to spend as little as possible while making their gastronomic scene look as strong as possible. To plan their strategy, they need to determine the minimum cost required to achieve a total of $$$k$$$ stars among all the $$$N$$$ restaurants, for every integer value $$$k$$$ between $$$1$$$ and $$$3N$$$, inclusive.

However, since bribe costs vary from restaurant to restaurant, calculating these values isn't straightforward – which is why they need your help.

A subarray of an array $$$B$$$ is a contiguous sequence of elements taken from $$$B$$$. For example, if $$$B=[3,1,4,1,5]$$$, then $$$[3,1,4]$$$, $$$[4,1]$$$, the empty array $$$[\ ]$$$ and the whole array $$$B$$$ are subarrays of $$$B$$$ (among others), while $$$[3,4,5]$$$ and $$$[1,3]$$$ are not subarrays of $$$B$$$.

We also define $$$C^m$$$ as the array obtained by the concatenation of $$$m$$$ copies of the array $$$C$$$. For example, if $$$C=[3,2]$$$ then $$$C^1=[3,2]$$$, $$$C^2=[3,2,3,2]$$$ and $$$C^{\infty}=[\ldots,3,2,3,2,3,2,\ldots]$$$.

In this problem you are given an array $$$P$$$ containing no repeated numbers, and you have to process a sequence of events that occur in order. The events can be of three types:

• Delete: a number present in $$$P$$$ must be deleted. For example, if $$$P=[2,3,4]$$$ and the number $$$3$$$ has to be deleted, once the event is processed $$$P$$$ will become $$$[2,4]$$$.
• Insert: a number not present in $$$P$$$ must be inserted into $$$P$$$ before some other number present in $$$P$$$. For example, if $$$P=[4,3,2,1]$$$ and the number $$$9$$$ must be inserted before the number $$$1$$$, once the event is processed $$$P$$$ will become $$$[4,3,2,9,1]$$$.
• Query: the length of the longest common subarray between $$$P^\infty$$$ and $$$A^\infty$$$ must be computed, where $$$A$$$ is an array given in the query. For example, if $$$P=[1,2,3,4]$$$ and $$$A=[3,2]$$$, then the longest common subarray between $$$P^\infty$$$ and $$$A^\infty$$$ is $$$[2,3]$$$, so the answer to the query is $$$2$$$.

Are you ready for this challenge?

The year is 2432, and after millennia of looking at the sky, astronomers have found all the stars. This arduous journey, which started with the discovery of the Sun in 450 BC, has finally come to an end. Since scientists can never be content, they have turned to the next best thing, and decided to find planets instead.

A passionate group, the Planet Discovery Aficionados (PDA), has already started working on it! To find new planets, they have built the Large Astronomical Telescope of Amazing Might (LATAM) – a telescope that is extremely sensitive to light and thus can see even the tiniest planets.

When pointed to the sky, LATAM's field of view encompasses the portion of space enclosed strictly by a circular cone, with the vertex located at the Earth and extending infinitely away from it. The angle of the cone corresponding to the viewing area of LATAM can be adjusted by the members of PDA, and it ranges from $$$0^{\circ}$$$ when the cone collapses to a line, to $$$90^{\circ}$$$ when it encompasses a full half-space.

Sadly, because LATAM is so sensitive to light, if there are any stars in its field of view the picture will be a bright mess, and PDA won't be able to see any planets. They ask for your help to determine the largest possible viewing angle that does not include any stars. PDA has enough money to travel anywhere on Earth, so you are allowed to point LATAM in any direction in the sky.

Because the universe is sufficiently large, PDA considers that all the stars and the Earth are fixed 3D points, with the Earth located at $$$(0,0,0)$$$. The group will give you the coordinates of all the stars in the universe. They hope that with this information, you will be able to complete your task.

Bob is playing a card game where he must defeat a monster. Before the game starts, Bob's power is set to $$$P$$$, the monster's health is set to $$$H$$$, and Bob receives a deck of $$$N$$$ cards in his hands.

Each card in the deck belongs to one of the following types:

• Multiply: a card of this type has a number $$$X$$$ written on it. Playing it multiplies Bob's current power by $$$X$$$.
• Add: a card of this type also has a number $$$Y$$$ written on it. Playing it increases Bob's current power by $$$Y$$$.
• Attack: a card of this type allows Bob to attack the monster. Playing it reduces the monster's current health by Bob's current power.

The game is played in turns. In each turn, Bob must play exactly one card from his hand, after which the card is moved to a discard pile. If Bob has no cards left in his hand at the end of a turn, he retrieves all cards from the discard pile and can use them again in any order.

The monster is beaten as soon as its health reaches $$$0$$$ or less. Is it possible for Bob to beat the monster? If so, what is the minimum number of turns required?

A LED counter is a device having $$$N$$$ positions arranged in a single row. Each position is able to display a digit from $$$0$$$ to $$$9$$$, and is made of seven LEDs, as this picture shows.

$$$0$$$	$$$1$$$	$$$2$$$	$$$3$$$	$$$4$$$	$$$5$$$	$$$6$$$	$$$7$$$	$$$8$$$	$$$9$$$

By turning on the appropriate LEDs in each of the $$$N$$$ positions of the counter, the device is able to display $$$10^N$$$ distinct values, from $$$00\cdots0$$$ ($$$N$$$ zeros) to $$$99\cdots9$$$ ($$$N$$$ nines). Note that leading zeros are displayed.

Astro Void has owned a LED counter for quite some time, and so the device might have some malfunctioning LEDs. While a good LED turns on or off when needed, a malfunctioning LED is always turned on or always turned off, independently of the intended value of the counter.

Given the description of the state of each LED in Astro Void's LED counter (good LED that is turned on, good LED that is turned off, always-on LED, or always-off LED), you must tell the intended value of the counter, indicating which positions cannot be determined without ambiguity. As an example of a LED counter with $$$N=3$$$ positions, consider the picture below. If all the LEDs are good, then the intended value of the counter is of course $$$056$$$. If the bottom LED of the first position is an always-on LED, then the intended value of the counter is still $$$056$$$, because no other value would be displayed as the picture shows. However, if the bottom-left LED of the second position is an always-off LED, then the second position of the counter cannot be determined without ambiguity, since $$$056$$$ and $$$066$$$ would be displayed as shown.