There is a long road of length $$$10^{9}$$$.

There are $$$N$$$ pedestrians crossing the road and $$$M$$$ cars driving on the road. You know, that the $$$i$$$-th pedestrian is going to cross the road from time $$$s_i$$$ to time $$$e_i$$$ at position $$$p_i$$$. You also know that the $$$j$$$-th car will drive from position $$$l_j$$$ to position $$$r_j$$$, starting at time $$$t_j$$$. To prevent car accidents, the following rule is set to regulate cars.

• If a pedestrian is crossing the road at the same position with some cars, then the cars should stop and wait until the pedestrian finishes his/her crossing.

All the cars proceed $$$1$$$ unit of length per unit of time unless it is stopped by the regulation.

To better illustrate the idea, the action of the car is defined as below.

• Let the current time be $$$t$$$ and the current position of the car be $$$x$$$.
• If there exists some $$$i$$$ such that $$$s_i \leq t \leq e_i$$$ and $$$p_i = x$$$, then the car is stopped.
• If there doesn't exist such $$$i$$$, then the car is driving.
• Increase $$$t$$$ and $$$x$$$ based on the status of the car.
• If $$$x = r_j$$$, then the car arrives at it's destination and disappears.

Given all the above information, you now wonder how many unordered pairs of cars would meet each other (formally speaking, there exists some time when the cars share the same position).

Below are some notes to avoid ambiguity, they are helpful but not necessary.

• A pedestrain's crossing time is inclusive, meaning that cars should stop even at time $$$s_i$$$ and time $$$e_i$$$.
• Two cars are counted as meeted each other even at the starting/ending position.
• If a car is stopped by pedestrian $$$i$$$, then the car arrives at position $$$p_i + 1$$$ at time $$$e_i + 2$$$.

There is a huge apple tree in your backyard. After years of growth, the tree is now full of apples. You know that the tree consists of $$$N$$$ nodes, and there are $$$a_i$$$ apples on the $$$i$$$-th node. You also know the length of each edge in the tree. You are planning to harvest the apples on the tree. To do that, you come up with a unique way of harvesting apples. Firstly, you select a set of nodes from which you are going to collect apples. Then you design a route that passes through all the nodes you selected and returns to the starting node (the route can start from any node in the tree). The score of a harvesting plan is defined as the total amount of harvested apples subtracting the total length of the route. Find the highest score among all harvesting plans.

Do you know what a perfect graph is? Before we can talk more about it, let's first define a few terms. Let $$$G$$$ be an undirected simple graph. The set of vertices in $$$G$$$ is denoted as $$$V(G)$$$. The set of edges in $$$G$$$ is denoted as $$$E(G)$$$. The complement of $$$G$$$, denoted as $$$\bar{G}$$$, is a graph containing all edges that do not appear in $$$E(G)$$$. A subgraph $$$G^\prime$$$ of $$$G$$$ is an induced subgraph if all edges $$$(u, v)$$$ such that $$$u, v \in V(G^\prime)$$$ belong to $$$E(G^\prime)$$$. The clique number $$$\omega(G)$$$ is the size of the maximum clique. That is, the size of the maximum subset $$$S$$$ of vertices such that every two vertices in $$$S$$$ are adjacent. The chromatic number $$$\chi(G)$$$, on the other hand, represents the minimum number of colors required to color $$$V(G)$$$ such that for every two adjacent vertices $$$x$$$ and $$$y$$$, $$$x$$$ has a different color than $$$y$$$ does.

One can easily see that $$$\chi(G) \geq \omega(G)$$$ for all graphs $$$G$$$, because you need at least $$$\omega(G)$$$ colors to color the maximum clique. Therefore, graphs that have the property of $$$\chi(G) = \omega(G)$$$ seem special and worth studying. It's tempting to call such graphs perfect. However, you can easily construct a graph $$$G_1$$$ with $$$\chi(G_1) \gt \omega(G_1)$$$ and put it beside a clique $$$G_2$$$ of $$$\chi(G_1)$$$ vertices. This results in a seemingly perfect graph $$$G = G_1 \cup G_2$$$ with $$$\chi(G) = \omega(G)$$$. This is not what we want. Therefore, we instead say that a graph $$$G$$$ is perfect if, for all induced subgraphs $$$G^\prime$$$ of $$$G$$$, the clique number of $$$G^\prime$$$ equals the chromatic number of $$$G^\prime$$$.

Now, the question comes. What types of graphs are perfect and what are not? A simple example of non-perfect graphs is $$$C_5$$$, a cycle of length $$$5$$$: $$$C_5$$$ has clique number $$$2$$$, but in order to color it properly, you need at least $$$3$$$ colors. Obviously, all odd cycles of length at least $$$5$$$ are not perfect for similar reasons. These cycle graphs are called odd holes. Similarly, one can see that the complements of odd holes are not perfect as well. These graphs are called odd antiholes.

In addition to odd holes and odd antiholes, if a graph $$$G$$$ contains an induced subgraph isomorphic to an odd hole or an odd antihole, then $$$G$$$ is not a perfect graph according to the definition. Thus, we've now found some examples of non-perfect graphs. But what about graphs without odd holes and odd antiholes? Will such graphs ever be non-perfect? Mathematician Berge conjectured that these are all the non-perfect graphs in 1961. That is, a graph is perfect if and only if it does not contain an induced subgraph isomorphic to an odd hole or an odd antihole. In 2002, Chudnovsky et al. proved the conjecture and showed that there's no such exception. This phenomenal theorem is what we now know as the Strong Perfect Graph Theorem (the word strong is used to distinguish between the (weak) perfect graph theorem, which states that a graph $$$G$$$ is perfect if and only if its complement $$$\bar{G}$$$ is perfect. It's easy to show that the (weak) perfect graph theorem can be immediately inferred from the strong perfect graph theorem).

Are you still looking for the problem to solve? Here it is. Given a cactus, determine if it's perfect or not. A cactus is a connected simple graph in which every edge belongs to at most one simple cycle.

Given a rooted tree of $$$N$$$ nodes with lowercase English characters on its nodes. Note here that node number $$$1$$$ is always the root of the tree.

There are $$$Q$$$ queries to be processed. Each query gives a node $$$u_j$$$ and a string $$$t_j$$$, asking how many times $$$t_j$$$ appears on the path from the root to $$$u_j$$$. The strings are read from top to bottom if we regard the root as the top-most node. In particular, a string $$$t$$$ is said to appear on the path from the root to a node $$$u$$$ if there exists a sequence of nodes $$$p_1, p_2, \ldots, p_{|t|}$$$ such that

• $$$p_i$$$ is the father of $$$p_{i + 1}$$$, for $$$1 \leq i \lt |t|$$$.
• The character written on $$$p_i$$$ is the same as the $$$i$$$-th character of $$$t$$$, for all $$$1 \leq i \leq |t|$$$.
• $$$p_{|t|}$$$ is an ancestor of $$$u$$$ (including $$$u$$$ itself).

Two appearances are considered different if their corresponding node sequences are different.

Given a prime number $$$P$$$ and a multiset $$$S$$$ containing $$$P - 1$$$ positive integers, please find out whether there is a non-empty multi-subset $$$S'$$$ of $$$S$$$, such that the product of elements in $$$S'$$$ is $$$1$$$ modulo $$$P$$$. That is,

$$$$$$ \prod_{i \in S'} i \equiv 1 \pmod{P} $$$$$$

.

It's Christmas time! There are $$$p$$$ children in the Prime Town, and of course, in Prime Town, $$$p$$$ is a prime number. Santa Claus would like to give each child the same amount of presents. There are two types of gifts available: gift A and gift B. However, Santa Claus cannot buy gift A or gift B arbitrarily. Instead, the only available option is to buy a combo containing $$$x$$$ gifts A and $$$y$$$ gifts B, where $$$x, y \geq p$$$

He wants to make every child equally happy, so he decides to distribute the gifts he buys to the children such that each child gets the same number of gift A and the same number of gift B.

There are only $$$p - 1$$$ combos left in stock. Santa Claus is rich, and as a result, he cares more about the number of wasted gifts than the money he spends on buying them. Therefore, he wants to choose the optimal number of combos to buy, so that after distributing them to the children evenly, the number of remaining gifts is minimized. Of course, he can simply buy nothing, and there will be no waste. However, that would make him an unethical Santa Claus, and thus it's forbidden to do so.

He wonders, what is the minimum number of remaining gifts if he buys the optimal number of gift combos?

Of course, Santa Claus knows some basics of competitive programming, and this problem should have been an easy task for him. Still, you should mind that he is Santa Clauses in $$$T$$$ different parallel universes, having their own $$$x, y, p$$$, respectively.

He has to solve it before Christmas, and there is no time to waste. Desperately, he adds this problem into the problem set so that some contestants might incidentally solve it during the contest.

In AB Factory, two products are manufactured, namely product A and product B. The factory could produce $$$1$$$ unit of product A or $$$1$$$ unit of product B each day. Ian is the director of the factory. He can decide when to change the product to manufacture. To check if the factory is working properly, Ian's boss would come and check if there are enough stocks of some products. Formally speaking, his boss comes to check $$$N$$$ times, the $$$i$$$-th check happens at time $$$t_i$$$, checking if there are at least $$$x_i$$$ units of product $$$p_i$$$. If there are enough desired products, Ian's boss would be happy and gives Ian $$$v_i$$$ dollars as a bonus.

Ian wonders how much money he could make if he plans the manufacturing product optimally. Help him calculate the answer.

A Mario Kart tournament consists of $$$N$$$ games. Each of the games is played by $$$M$$$ players. In each of the $$$N$$$ games, each of the $$$M$$$ players receives a rank according to the order they arrived at the goal. A player's record of the whole tournament could be represented as an array of $$$N$$$ numbers, $$$A = [a_1, a_2, ..., a_N]$$$, meaning that the player got $$$a_i$$$-th rank in the $$$i$$$-th game. To evaluate a player's performance, one could design a function $$$f$$$ satisfying $$$K \geq f(1) \geq f(2) \geq ... \geq f(M) \geq 1$$$, then further represent the player's performance as $$$\sum_{i=1}^{N} f(a_i)$$$. (Note that all $$$f(i)$$$ should be integers.)

For example, if $$$N = 2, M = 3, A = [1, 3]$$$ and $$$f(1) = 6, f(2) = 3, f(3) = 3$$$, then the performance of the player is equal to $$$f(1) + f(3) = 6 + 3 = 9$$$.

Ian just finished a Mario Kart tournament. Before the final result is announced by the judge, he would like to guess his rank in the tournament. However, he doesn't know how other players are performing, and the function $$$f$$$ for calculating the performance. Since there is no way to know his exact rank under this constraint, Ian decides to think about another problem.

Given the ranks he got in each of the games, he wants to calculate how many different ranking arrays could possibly have a strictly higher performance than his.

Two ranking arrays $$$A$$$ and $$$B$$$ are considered as different ranking arrays if and only if there exists some $$$i$$$ such that $$$a_i \not= b_i$$$. Note here that you should also consider the arrays with some $$$i$$$ such that $$$a_i = b_i$$$.

Since the answer could be very large, please output it modulo $$$998244353$$$.

There are $$$N$$$ cities in the NCPC Kingdom, numbered from $$$1$$$ to $$$N$$$. The cities are connected by $$$M$$$ one-way roads, where one can travel from city $$$u_i$$$ to city $$$v_i$$$ directly using the $$$i$$$-th road (but not the other way around).

Due to the new zeta variant of COVID-19, the government of the NCPC Kingdom decides to restrict people from traveling between cities. Specifically, the government wants to reconstruct the $$$M$$$ roads so that for each city $$$x$$$, there are at most $$$K$$$ other cities that can directly travel to city $$$x$$$ using a single road after the reconstruction.

The reconstruction is of course costly. For the $$$i$$$-th road, the government can choose one of the following plan:

• Do nothing.
• Spend $$$a_i$$$ dollars and reverse the road. That is, after the reconstruction, people can travel from city $$$v_i$$$ to city $$$u_i$$$ (but not the other way around).
• Spend $$$b_i$$$ dollars and shutdown the road completely.

Please help the NCPC Kingdom find the most cost-efficient reconstruction plan.

Jason lives in Gotham. This summer, he plays a game called Hot Potato with people there.

The game consisted of $$$n$$$ players numbered from $$$1$$$ to $$$n$$$ and a hot potato. Initially, player $$$1$$$ holds the hot potato. When a player holds the hot potato, he/she must pass it to another player, otherwise, the holder is the loser, and the game ends. Suppose A is the player holding the hot potato and B is any other player. A can only pass the hot potato to B if A knows B and B hasn't touched the hot potato before. Note that A knows B does not imply B knows A.

People of Gotham love chaos, so if there are multiple players A can choose to pass the hot potato, A chooses one uniformly at random. In other words, if there are $$$k$$$ candidates, each of them has the probability of $$$\frac{1}{k}$$$ to be chosen by A.

Jason knows the relationships between players and wants to know the probability of losing the game for each player. Please help him!

Do you know the Skylinebaby game? The game comprises $$$n$$$ positive integers $$$a_1, ..., a_n$$$, and a constant $$$k \gt 1$$$.

Skylinebaby game is a game for two players playing alternately. Each turn the current player can choose one of the integers $$$a_i$$$ and an integer $$$t$$$ satisfying $$$a_i \geq t \geq k$$$, then replace $$$a_i$$$ with $$$\lfloor \frac{a_i}{t} \rfloor$$$. The player who can't make a move loses the game.

Alice and Bob want to play the Skylinebaby game together, but they immediately notice that the game favors the first player a lot.

Alice and Bob want to modify the game so that it can be more even. Therefore, they propose a new idea that the player who moves secondly can decide the constant $$$k$$$ before the game starts. Of course, there should be some additional limitations of this rule, or he can just set $$$k$$$ to a large number, and the first player will not be able to make a single move. After some game testing, they agree on the final version that $$$k$$$ should not exceed any of the integers $$$a_1, \ldots, a_n$$$ ($$$k$$$ still has to be greater than 1).

Now, Alice and Bob want to play the modified version of the Skylinebaby game they just developed. Alice moves first. Given $$$n$$$ and the integers $$$a_1, ..., a_n$$$, determine the winner if both players play optimally.

You, an adventurer, found a strange room inside a dungeon.

The room consists of $$$N^2$$$ sculptures of soldiers arranged in an $$$N$$$ by $$$N$$$ square, where each soldier raises either his left hand or his right hand. You noticed that there is a button on the wall. Out of curiosity, you pressed it. Suddenly, $$$N$$$ sculptures in the same row started to move, and all of them changed their raising hands.

After some investigations, you found a message written on the wall below the button. Each line of the message represents a row or a column of the $$$N$$$ by $$$N$$$ square that the soldiers form. The first line of the message is the next changing row or column. That is, every time you press the button, the soldiers in that specific row or column will change the hand they raise. After that, the first line of the message will disappear and the second line will indicate the next event.

You want to find some properties of the soldiers since it might provide you some insights to beat the boss in the dungeon. It occurred to you that you can view the square of soldiers as a matrix, and you can use $$$0$$$ and $$$1$$$ to represent soldiers raising left hands and right hands. Therefore, the square of soldiers becomes a $$$0$$$-$$$1$$$ matrix.

You believe that the rank of a $$$0$$$-$$$1$$$ matrix is the most crucial property, but it turns out that the rank of a $$$0$$$-$$$1$$$ matrix is not symmetric in terms of $$$0$$$ and $$$1$$$. In particular, you're not sure whether it'd be better to use $$$0$$$ for left hands (and thus $$$1$$$ for right hands) or vice versa, and sometimes interchanging the representation results in matrices with different ranks. As a result, instead of a specific representation, you would like to consider both options and calculate the L-rank — the minimum value between the ranks of these two matrices.

Now, you know the first $$$Q$$$ lines of the message on the wall, and you want to calculate the L-rank of the soldier matrix after each of the $$$Q$$$ events.