Alikhan is preparing a Persian New Year party. The main attraction of the party will be a device where guests can add a song to the playlist that will be played for the entire party.

During the party, guest $$$i$$$ approaches the device at time $$$t_i$$$ and chooses a song of duration $$$m_i$$$ that will be added to the end of the playlist.

The device has one problem: the guest can press a button when choosing the song and skip the queue, interrupting the song that is currently playing and immediately starting the playback of the chosen song. The interrupted song will not be played again. Fortunately, if this happens, the rest of the queue remains unchanged.

Alikhan knows that if the song of guest $$$i$$$ is playing and is replaced, this guest will become very sad and will never show up at any of Alikhan's parties again (note that if someone presses the button at the moment when guest $$$i$$$'s song ends, this guest will not be sad). To remedy this situation, Alikhan needs to know all the guests whose songs were interrupted so that he can send a letter of apology the next day.

Mori got tired of living in Brazil and moved directly to Kazakhstan in search of a better life. In Kazakhstan, being a programmer is a thing of the past, and the new trendy profession at the moment is being a lumberjack. Since Mori is no fool, he decided to live the life of a lumberjack in Kazakhstan too!

Mori's new job as a lumberjack requires him to chop down $$$M$$$ trees distributed among the integer points $$$1$$$ to $$$N$$$. As everything is harmonious in the 2D world, all trees have height $$$H$$$ and have their roots on the $$$x$$$-axis, that is, $$$y=0$$$. There are no two trees at the same point.

When Mori chops down a tree located at point $$$a_i$$$, he can choose to fell it to the left, affecting the points $$$x$$$ such that $$$a_i-H \le x \le a_i$$$, or to the right, affecting the points $$$x$$$ such that $$$a_i \le x \le a_i+H$$$. If there are other trees in the affected range, this will trigger a series of chain reactions, knocking down those trees in the same direction as the original tree was felled. After all the trees resulting from chopping down the tree at point $$$a_i$$$ have been felled, Mori removes these trees and continues the process of chopping down trees with the remaining ones.

Mori faces a hindrance while performing his job. His contractor does not own the land corresponding to points $$$0$$$ and $$$N+1$$$. Therefore, during his work, he cannot chop down any trees at these two points.

Since Mori does not yet know where the $$$M$$$ trees are located, he wants to know the probability of being able to complete his work without chopping down trees at points $$$0$$$ and $$$N+1$$$, given that every configuration of $$$M$$$ trees scattered across $$$N$$$ points is equally likely. Print the answer modulo $$$998244353$$$.

Road cycling is one of the sports in which Kazakh athletes excel the most. Thus, to strengthen ties with Kazakhstan, the Brazilian Cycling Society (SBC) decided to organize a cycling marathon on Kazakh territory!

With the intention of attracting the largest number of competitors of all levels, the marathon organized by the SBC is different from the usual ones. The circuit has $$$n$$$ stations where cyclists can stop to rest, drink an energy drink for free, and continue. The stations are arranged in a circular manner. In other words, for $$$1 \leq i \lt n$$$, station $$$i + 1$$$ is immediately after station $$$i$$$, and station $$$1$$$ follows station $$$n$$$. The energy drink available at station $$$i$$$ gives the cyclist $$$b_i$$$ units of energy. The amount of energy required to go from station $$$i$$$ to the next is $$$c_i$$$ units. Thus, a cyclist with $$$x$$$ units of energy can move from station $$$i$$$ to the next only if $$$x \geq c_i$$$. Moreover, he loses $$$c_i$$$ units of energy when doing so.

The SBC is testing different scenarios to decide how to better organize the marathon. Your task is to help them answer 3 different types of queries:

• $$$1$$$ $$$i$$$: Suppose a cyclist with initial energy 0 starts his journey at station $$$i$$$. Tell which is the last station he can reach before stopping. If the cyclist can continue indefinitely, print $$$-1$$$.
• $$$2$$$ $$$i$$$ $$$x$$$: Assign the value $$$x$$$ to $$$b_i$$$.
• $$$3$$$ $$$i$$$ $$$x$$$: Assign the value $$$x$$$ to $$$c_i$$$.

Apples originated in the region of the Tian Shan Mountains of Kazakhstan. The name of the largest city in the country, Almaty, is often translated as "full of apples". After discovering this interesting fact, Harada and Teos, the biggest fans of apples in the world, decided to travel to Almaty. They now need your help preparing their luggage!

They will only take one bag, which can be seen as a 3D box from $$$(0, 0, 0)$$$ to $$$(x, y, z)$$$. Each of them will only put one object in the bag, an apple! Teos has already placed his apple inside the bag. Teos' apple can be seen as a 3D sphere with its center at $$$(tx, ty, tz)$$$ and radius $$$r$$$. Although the apple may be "floating" in the air, it is guaranteed to be entirely contained inside the bag. Now Harada wonders what is the largest apple, i.e., a 3D sphere, that can fit inside the box. Clearly, the two apples can touch each other but must not intersect at any point.

The European Union is experiencing an energy crisis. Given this situation, the Ministry of Energy of Kazakhstan wants to redesign the network of routes connecting the country's power plants. Kazakhstan has $$$N$$$ power plants scattered across its territory. The Ministry has information on all the routes that connect these plants, as well as the cost involved in maintaining each route. In particular, the cost of maintaining the $$$i$$$-th route varies over time and depends on three parameters $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$, following the function $$$$$$a_it^2 + b_it + c_i,$$$$$$ where $$$t$$$ represents the time.

To carry out this task, the minister has hired Marcel "the Optimizer" Saito. After analyzing Kazakhstan's geography, Marcel already has a plan to redesign the country's route network. However, as this would involve making significant changes, he needs to demonstrate how effective his plan is. To do this, he wants to calculate the minimum cost of connecting all the power plants using the existing routes at a given time $$$t$$$.

Marcel is very busy preparing his newest apprentice, Daniel "the Dynamic" Ito. Therefore, he has assigned this task to you.

Kazakhstan is a country that takes the problem of global warming very seriously. For this reason, the Kazakh government is implementing Green Economy in the country. To achieve this, it is necessary for all companies in the country to reach carbon neutrality.

There are $$$n$$$ companies in Kazakhstan, and we can model the transactions between them as a directed graph with $$$m$$$ edges. An edge that goes from $$$u$$$ to $$$v$$$ indicates a transaction made from company $$$u$$$ to company $$$v$$$. The Kazakh government needs to make a decision for each of these transactions, which can be modeled as assigning an integer weight $$$-1 \leq w \leq 1$$$ to the corresponding edge. The weight $$$w = 0$$$ indicates that the transaction is prohibited. Weights $$$w = -1$$$ and $$$w = 1$$$ indicate that the transaction absorbs or emits carbon, respectively.

For a company $$$v$$$ to achieve carbon neutrality, it must hold that $$$c^+(v) = c^-(v)$$$, where $$$c^+(v)$$$ indicates the sum of the weights of the edges that leave $$$v$$$ and $$$c^-(v)$$$ indicates the sum of the weights of the edges that enter it. It is clear that, by prohibiting all transactions, the Kazakh government could achieve its Green Economy goal; however, the important transactions cannot be prohibited because the country's economy would collapse! A transaction $$$i$$$ is important if $$$t_i = 1$$$.

Given the description of the transactions between the companies in Kazakhstan, determine if it is possible to implement carbon neutrality in all companies. If it is possible, provide a solution.

The ICPC World Finals in Astana are around the corner, and your team has prepared a list of must-visit places! Your journey starts at your home and spans several key cities and touristic spots across the vast and beautiful landscapes of Kazakhstan before reaching the competition venue in Astana. Along the way, you will pass through several key stops (positions) you must visit, including the bustling city of Almaty, the historical city of Shymkent, and the scenic wonders near Karaganda.

The ICPC, aware that competitors have many places to visit, has created a special teleportation device to help teams complete their touristic duties on time for the competition. You can either travel to the next stop normally or use the special teleportation device. Each time you use a teleport, it is destroyed, and a new teleport point is created at your last stop before teleporting.

To simplify the planning, consider that your home and the first teleport is at point 0 and the touristic spots are arranged in a line. The cost of normal travel is the absolute difference in distance between your current stop and the next stop. The cost of a teleport is the absolute difference in distance between your last teleport position and the next stop.

Your task is to determine the minimum total travel cost to reach the competition venue in Astana from your home using the teleportation device. Note that your teammates put a lot of care and effort into crafting this itinerary and want to visit the touristic spots in order.

Nathan, as usual, went to buy energy drinks to participate in a competition in Astana, Kazakhstan. Since the Kazakh people are health-conscious, energy drinks have become a rarity. For this reason, Nathan has to drive to the only energy drink store in the city and then make his way to the competition location. As always, Nathan didn't plan adequately, and upon arriving at the energy drink store, he realized he might not have enough time to return to the competition. Help Nathan find the shortest time he can reach the competition given that he is at the energy drink store.

The city can be described by a set of $$$M$$$ streets and $$$N$$$ intersections. Each street $$$r_i$$$ is defined by two intersections representing the ends of the street and a traffic light. A traffic light allows or prevents a car from passing through the street it controls, depending on whether it is open or closed. Traffic lights have a known cyclical behavior: the traffic light for street $$$r_i$$$ cycles, being open for $$$x_i$$$ minutes and closed for $$$y_i$$$ minutes. Every traffic light starts its cycle open at time $$$0$$$.

The energy drink store is located at intersection 1, while the competition takes place at intersection $$$N$$$. What is the shortest time Nathan can reach the competition if he starts at the energy drink store at time $$$t$$$?

The time spent driving the car is negligible compared to the waiting time at traffic lights. Since Nathan is not so incapable that he would use a route that makes it impossible to reach the competition, it is guaranteed that there is a way to reach intersection $$$N$$$ starting from intersection $$$1$$$.

The Baikonur Cosmodrome, located in Kazakhstan, is the world's oldest space launch facility. Many historical flights lifted off from Baikonur: the first human-made satellite, Sputnik 1, in 1957; the first crewed spaceflight by Yuri Gagarin, in 1961; and the flight of the first woman in space, Valentina Tereshkova, in 1963. Today, one more historical rocket is lifting off, humanity is going to Mars!

You are an alien employee of the company Astronauts Coming to Mars (ACM) and want to make sure the rocket has enough space for a safe landing. Right now, the place where the humans will land is occupied by $$$n$$$ mountains, each with height $$$a_i$$$. You must destroy them all before the humans arrive.

You are allowed to do the following two operations:

• Select a subset $$$S$$$ and decrease the height by one of every mountain in $$$S$$$;
• Select a subset $$$S$$$ and change $$$a_i$$$ to $$$a_i \% 2$$$ (the remainder when $$$a_i$$$ is divided by 2) for every mountain in $$$S$$$.

What is the minimum number of operations to make all mountains have height zero?

Moretev is a Kazakh born in Astana who moved to Salvador and fell in love with Acarajé, a major highlight of Brazilian cuisine. Because of this, he decided to start his own Acarajé stand. However, upon starting his sales, he faced a significant problem: he is required to set the price of the product before advertising it.

"How absurd! In the bazaars of my hometown, this doesn't happen!"

You have been hired to help Moretev set the price of his Acarajé in order to maximize his profits. To assist him, he conducted a survey and provided the following sample: a list of $$$N$$$ consumers, where consumer $$$i$$$ will only buy the Acarajé if the price is less than or equal to $$$p_i$$$.

Based solely on this list, determine the price that Moretev should set for his Acarajé and what his revenue would be in this sample.

Yan "the globe-trotter" Soares is traveling through Central Asia. In the city of Almaty, one of Kazakhstan's largest metropolises, he stumbled upon a curious arcade that is open 24 hours. As he enjoys games in general, he decided to enter the arcade and found a very peculiar claw machine.

Inside this machine, there are $$$N$$$ stuffed animals arranged in a row. Additionally, the claw used to grab the stuffed animals is also unique. This claw has two prongs, left and right. The distance between the prongs is exactly the width of $$$W$$$ stuffed animals (all stuffed animals have the same width).

Here's how the claw operates: Initially, the claw is above the stuffed animals. The player chooses the position of the left prong (the right prong is $$$W$$$ stuffed animals to the right of it). The claw descends until the prongs touch the row. Finally, the right prong moves to the left until it touches a stuffed animal (if there are $$$W$$$ stuffed animals between the two prongs, the right prong does not move). The claw then removes all the stuffed animals between the two prongs. The remaining stuffed animals stay in the same position, so the row will have gaps after using the claw. Note that the left prong cannot move to the left of the first stuffed animal, and the right prong cannot move to the right of the last stuffed animal in the row.

Yan has assigned a preference value $$$p_i$$$ to each stuffed animal in the row (this value can even be negative). He also has $$$M$$$ coins to play. Since he doesn't want to waste these coins, he asked for your help to determine the maximum total preference value he can achieve if he uses the claw up to $$$M$$$ times (he can choose not to use any coins at all). Help Yan find this maximum value!

Willian is traveling in Kazakhstan to take a break from work and college, exhausted from handling numerous server issues at his company. One night, he decided to leave the hotel to enjoy the area and appreciate the beautiful local scenery, visiting landmarks such as the Baiterek Tower, the Hazrat Sultan Mosque, and other places. As he looked up at the sky in front of the mosque, Willian noticed how it was filled with stars, framed by the illuminated minarets of the mosque. The stars twinkled and faded against the dark sky, while clouds passed over them in the darkness. That evening, Willian looked at the stars and, after studying so much geometry, doing numerous lists, and programming exercises, he wondered:

— Which pair of stars produces the largest absolute value of the slope if connected by a line?

A line can be algebraically described by linear equations such as $$$y = ax+b$$$, where $$$x$$$ is the independent variable of the function $$$y = f(x)$$$, the constant $$$a$$$ is the slope, and the constant $$$b$$$ is the $$$y$$$-intercept of the line. The absolute value is defined by a function $$$y = |x|$$$, where if $$$x \lt 0$$$, then $$$|x| = - x$$$, and if $$$x \geq 0$$$, then $$$|x| = x$$$.

Willian continued to enjoy the view of the sky and soon realized that the phenomenon of stars being covered by clouds could be represented as follows. Initially, there is a configuration of $$$N$$$ stars. After that, there are $$$Q$$$ events, where the events are characterized by:

1. A star appears at $$$(X_i, Y_i)$$$.
2. A star disappears at $$$(X_i, Y_i)$$$.

In the initial configuration of the stars and after each of the events, we want to determine the largest absolute value of the slope among all pairs of stars.