"Participate in large regionals if you want to win gold medals; participate in small regionals if you want to get the qualify to WF..."

There will be $$$n$$$ teams participating in the 2024 ICPC Regional Contests numbered from $$$1$$$ to $$$n$$$. Each team can be described by a positive integer represents its comprehensive strength and a string represents the abbreviation of the university it belongs to. In this problem, we guarantee that the abbreviation of each university is unique and the comprehensive strengths of the teams are pairwise distinct. We also assume that the stronger team will always be ranked ahead of the weaker team in any contest.

This year, $$$k$$$ regional contests will be held. For the $$$i$$$-th regional contest, every university can select no more than $$$c_i$$$ teams to join the contest. Meanwhile, each team can select no more than $$$2$$$ regional contests to participate in.

Now, you are asked to calculate the smallest possible rank for each team in the worst case, if they choose the regionals optimally. Note that when a team registers, it does not know the registration strategy of other teams, even if they are from the same university (but the total number of teams in the same university for the $$$i$$$-th regional contest is still limited by the $$$c_i$$$, and we always assume that the team currently under consideration has priority to register).

Please refer to the samples to understand the problem better.

Byte Mountain is a beautiful tourist attraction in Byteland. There are $$$n$$$ areas on the Byte Mountain, labeled by $$$1,2,\dots,n$$$, connected by $$$n-1$$$ undirected roads. There is exactly one path between each pair of different areas. In other words, the map of the mountain is a tree with $$$n$$$ nodes.

Assume today is day $$$0$$$. In each of the next $$$m$$$ days, the map of the mountain will be changed a little. Formally, in the early morning of day $$$i$$$ ($$$1\leq i\leq m$$$), the $$$k_i$$$-th road will be closed forever, and another new road will be built, but the map of the mountain will always be a tree.

You are given the road construction plans for all the next $$$m$$$ days, together with bookings of $$$p$$$ tourists. The $$$i$$$-th tourist will visit the $$$b_i$$$-th area in the afternoon of day $$$a_i$$$, and will leave the mountain that night. You are now wondering about some interesting metrics.

Note that each road is weighted. Let $$$f(u,v)$$$ be the maximum value of weights among all the roads on the unique single path from $$$u$$$ to $$$v$$$ ($$$u\neq v$$$). You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given two integers $$$c_i$$$ and $$$d_i$$$. You are required to calculate the following metric of the $$$d_i$$$-th area on the $$$c_i$$$-th day:

$$$$$$ \sum_{1\leq j\leq p,\,a_j=c_i,\,b_j\neq d_i} f(b_j,d_i) $$$$$$

Ms. Wozzie has a variable-length array $$$S$$$. Initially $$$S$$$ is empty, and the array will be manipulated $$$N$$$ times, each time adding a number to the end of $$$S$$$.

She wants to check the current state of the array when she adds the $$$i$$$-th number $$$S_i$$$, so she will give you a pair of $$$A_i,B_i$$$ at the same time, and wants you to output the current value of $$$\sum_{i=1}^{n} \sum_{j=i}^{i+z_i-1} A_j \times B_i$$$. Define $$$z_i$$$ as the longest common prefix of $$$[S_i ,\dots ,S_n]$$$ and $$$[S_1,\dots,S_n]$$$ where $$$n$$$ is the current length.

Recall that the longest common prefix of $$$[a_1,\dots, a_n]$$$ and $$$[b_1, \dots, b_m]$$$ is the largest $$$L$$$ satisfying: $$$a_i = b_i, \forall 1 \leq i \leq L$$$.

To make sure you answered her question in real time, she will encrypt the number $$$S_i$$$ she is currently adding backward through your last answer, the exact decryption is given in the input format.

Given a rooted tree with $$$n$$$ nodes, where the root is node $$$r=1$$$, each node has an associated weight $$$a_i$$$.

The distance between two nodes in the tree is defined as the number of edges on the shortest path between them.

The subtree of a node $$$x$$$ is defined as the set of all nodes $$$y$$$ such that the shortest path from $$$y$$$ to the root $$$r$$$ passes through $$$x$$$.

You need to support the following three types of operations:

1. Given $$$x$$$, $$$k$$$, and $$$v$$$, for each node $$$y$$$ at a distance exactly $$$k$$$ from $$$x$$$, update $$$a_y$$$ to $$$a_y+v$$$, then output the maximum of $$$a_y$$$.

2. Given $$$x$$$, $$$k$$$, and $$$v$$$, for each node $$$y$$$ at a distance of at most $$$k$$$ from $$$x$$$, update $$$a_y$$$ to $$$a_y+v$$$, then output the maximum of $$$a_y$$$.

3. Given $$$x$$$ and $$$v$$$, update $$$a_y$$$ to $$$a_y+v$$$ for every node $$$y$$$ in the subtree of $$$x$$$, then output the maximum of $$$a_y$$$.

Sneaker wakes up in a vast maze, and now he wants to escape from it.

Through the map found in every room of the maze, Sneaker learns the structure of the maze. The maze consists of $$$n$$$ rooms, with Sneaker starting in room $$$1$$$, and the exit is in room $$$n$$$. Additionally, there are $$$m$$$ two-way passages in the maze, each connecting two different rooms, and the two directions of each passage are isolated from each other.

It is guaranteed that no two different passages connect the same pair of rooms, and there is no passage that connects a room to itself.

Moreover, it is guaranteed that any two rooms can be reached from each other through a series of passages.

Sneaker also discovers that there are $$$k$$$ slayer robots in the maze. The $$$i$$$-th slayer robot initially stays in room $$$s_i$$$. Obviously, Sneaker does not want and cannot encounter these slayer robots.

If Sneaker starts moving, each slayer robot will move simultaneously. Specifically, Sneaker will choose a passage connected to the room he is currently in and move to the room on the other side of the passage. At the same time, each slayer robot will randomly choose a passage connected to the room it is in and move to the room on the other side of the passage. Every slayer robot will enter and exit the passage at the same time as Sneaker.

All slayer robots will record the passages they pass through. If a slayer robot travels through a passage that is the same as the last recorded passage, it can choose to erase both occurrences of this passage from its record. In other words, the slayer robot can choose to undo a record.

For example, if a slayer robot currently has a record of passages $$$(1,2), (2,7), (7,3)$$$ and is now in room $$$3$$$, it can choose to move through a new passage, say $$$(3,6)$$$, and its record will become $$$(1,2), (2,7), (7,3), (3,6)$$$, with the robot ending up in room $$$6$$$. Alternatively, it can move through passage $$$(3,7)$$$ to return to room $$$7$$$, and its record will become $$$(1,2), (2,7)$$$.

Furthermore, if the slayer robot then chooses to move through a passage back to room $$$2$$$, its record will become $$$(1,2)$$$. However, if it moves from room $$$3$$$ directly to room $$$2$$$, its record cannot become $$$(1,2)$$$; instead, it will become $$$(1,2), (2,7), (7,3), (3,2)$$$.

Additionally, all slayer robots share a same self-destruct parameter $$$d$$$. If a slayer robot arrives in a room and finds that its record of passages exceeds $$$d$$$, it will immediately self-destruct. If Sneaker enters a room and finds that a slayer robot is in the process of self-destructing or has already self-destructed, it is not considered an encounter with the robot.

Now, Sneaker wants to plan a route with the minimum number of passages and ensure that he will not encounter any slayer robot. Can you help him?

Note: If Sneaker is moving from room $$$x$$$ to room $$$y$$$ through a passage, and a slayer robot is moving in the opposite direction, from room $$$y$$$ to room $$$x$$$ through the same passage, Sneaker will not encounter the slayer robot because the two directions of the passage are isolated from each other. The sneaker only knows the initial position of each slayer robot, but does not know their positions at every moment. If both a slayer robot and Sneaker arrive at room $$$n$$$ at the same time, then Sneaker is considered to have encountered the slayer robot and cannot escape from the maze.

On the Codeforces platform, each user has a rating to measure his level. In addition, each user will also have a title based on his rating. Recently, because user Tourist's rating exceeded 4000 points, Codeforces administrators decided to provide a new title, "Tourist", to commemorate this feat.

You also want to get this title, because it's cool to be called a "Tourist"! But your current rating is only $$$1500$$$ points, which is not enough to get this honor. So, you let the GPT predict your rating changes in the next $$$n$$$ contests. Specifically, suppose your rating is $$$b$$$ points before the $$$i$$$-th contest, then after the $$$i$$$-th contest, the GPT predicts that your rating will become $$$b+c_i$$$ points. You want to know after which of those $$$n$$$ contests you will get the title of "Tourist" for the first time, or there is no such contest.

Note that the rating may become negative during this process, and the "Tourist" title will be awarded to users with a rating of at least 4000 points.

Alice and Bob are playing a game. Initially, Alice has $$$x$$$ chips, and Bob has $$$y$$$ chips.

The game proceeds in several rounds. In each round, Alice wins with a probability of $$$p_0$$$, Bob wins with a probability of $$$p_1$$$, and there is a probability of $$$1 - p_0 - p_1$$$ for a draw.

If there is a draw, the game immediately moves to the next round. Otherwise, if the number of the winner's chips is not smaller than the number of the loser's chips, the winner wins the entire game, and the game ends; otherwise, the loser loses an amount of chips equal to the winner's current chips, and the game moves to the next round.

Note that after each round of the game, no one's chips will increase.

You are asked to find the probability that Alice will ultimately win the entire game.

There are $$$n$$$ points $$$p_1,p_2,\dots,p_n$$$ on the 2D plane. The $$$i$$$-th point $$$p_i$$$ is located at $$$(x_i,y_i)$$$ with weight $$$w_i$$$.

Consider a query with parameters $$$(a,b,c)$$$, let $$$S(a,b)=\{p_i|x_i\leq a\land y_i\leq b\}$$$. The query denotes "Is it possible to select a subset $$$T$$$ from $$$S$$$ such that $$$(\sum_{p_i\in T}w_i)\bmod n=c$$$?" ($$$T\subseteq S$$$)

Let $$$\text{query}(a,b,c)=\text{True/False}$$$ be the answer to the query with parameters $$$(a,b,c)$$$. You are required to answer all possible queries. Instead of printing $$$O(n^3)$$$ lines, you only need to compute the following value:

$$$$$$ ans=(\sum_{a=1}^n\sum_{b=1}^n\sum_{c=1}^{n-1} a\cdot b\cdot c\cdot[\text{query}(a,b,c)=\text{True}])\bmod 2^{64} $$$$$$

A normal binary decomposition can be represented as $$$n=\overline{a_{31}a_{30}\cdots a_0}$$$, where $$$a_i \in \{0,1\}$$$.

Now, there is a strange binary decomposition, still represented as $$$n=\overline{a_{31}a_{30}\cdots a_0}$$$, but it needs to satisfy:

1. For $$$i=0,1,\cdots,31$$$, $$$a_i \in \{-1,0,1\}$$$.
2. For $$$i=0,1,\cdots,30$$$, $$$a_i$$$ and $$$a_{i+1}$$$ cannot both be 0, i.e., $$$a_i^2 + a_{i+1}^2 \neq 0$$$.
3. $$$$$$ \sum_{i=0}^{31} a_i 2^i = n $$$$$$

Given a non-negative integer $$$n$$$, find the above binary decomposition of $$$n$$$, or determine that it cannot be decomposed.

You are a grocery store owner, and there are $$$n$$$ goods in your store. Each good $$$i$$$ has an associated weight $$$w_i$$$, initial volume $$$v_i$$$, and compression coefficient $$$c_i$$$.

You stack all the goods into one pile to keep the store tidy. Because goods can be compressed, assuming that the sum of the weights of the items above the goods $$$i$$$ is $$$W$$$ (Not including itself), then after stacking, the actual volume of the goods $$$i$$$ will become $$$v_i-c_i\times W$$$.

The space in your store is really limited, so you want to know the minimum possible value of the sum of the actual volumes of the items.

Given two sequences $$$a$$$ and $$$b$$$ of length $$$n$$$, a bipartite graph is generated in the following manner:

The nodes of the bipartite graph are divided into two parts: the left side and the right side. There are $$$n$$$ nodes on both sides. An edge exists between the i-th node on the left side and the j-th node on the right side if and only if $$$a_i \oplus b_j \geq k$$$, where $$$\oplus$$$ denotes the bitwise XOR operator.

For each $$$x$$$ in the range $$$[1,n]$$$, output the number of matchings of size $$$x$$$ in the bipartite graph, with the result modulo $$$998244353$$$.

Welcome to the Internet Connection Practice Competition (ICPC) this year! In the competition, you and your teammates will fight against the Obstacle Maker System (OMS) to connect to the server successfully! Be careful with every refresh operation, as the system may assign you unknown obstacles.

To simplify the problem, we model the competition process into the following form:

Each team has a timer during the competition, and the goal is to get the remaining time to $$$0$$$ as quickly as possible. At the beginning of the $$$0$$$-th second, the OMS will uniformly and randomly generate an integer $$$t_0$$$ in $$$[1, T]$$$ and initialize the remaining time of your timer to $$$t_0$$$ seconds. Next, at the end of each second (starting with the $$$0$$$-th second), the following events occur in order:

• The remaining time of the timer will be decreased by $$$1$$$. If the remaining time of the timer is zero at this time, the number of seconds from the start of the competition to this moment is your penalty.
• Otherwise, you can do nothing after this or use the refresh operation on OMS once. If you choose to refresh your timer, OMS will uniformly and randomly generate a new integer $$$t'$$$ in $$$[1, T]$$$ and set the remaining time of your timer to $$$t'$$$.

Your goal is to minimize your penalty. Please calculate the expected penalty using the optimal strategy. During the contest, you always know the remaining time of the timer, and the value of $$$T$$$.