This problem has nothing to do with problem F

Danna has N friends, numbered from $$$1$$$ to $$$N$$$ in a fixed line order. She wants to give $$$X_i$$$ candies to the $$$i$$$-th friend ($$$1 \le i \le N$$$).

A friend $$$i$$$ is defined as an "Absolute Winner" if the number of candies they receive $$$X_i$$$ is strictly greater than the sum of all candies given to every friend standing before them in line (i.e., $$$X_i \gt \sum_{k=1}^{i-1} X_k$$$). Note that by definition, the 1st friend ($$$i = 1$$$) is always an Absolute Winner since the sum of candies before them is 0, so $$$X_1 \gt 0$$$.

However, some friends are very picky. For each friend $$$i$$$, you are given a requirement $$$A_i$$$:

1. If $$$A_i = -1$$$, friend $$$i$$$ is open to receiving any positive integer number of candies.

2. If $$$A_i \gt 0$$$, friend $$$i$$$ demands to receive exactly $$$A_i$$$ candies (i.e., $$$X_i = A_i$$$).

Your task is to determine whether Danna can distribute positive integer amounts of candies $$$(X_1, X_2, \dots, X_N)$$$ such that:

1. Every friend $$$i$$$ is an Absolute Winner ($$$X_i \gt \sum_{k=1}^{i-1} X_k$$$).

2. Every picky friend's requirement is satisfied ($$$X_i = A_i$$$ whenever $$$A_i \neq -1$$$).

3. $$$X_i$$$ is a positive integer ($$$1 \le X_i \le 10^9$$$) for all $$$1 \le i \le N$$$.

If it is possible to satisfy all conditions, print "Yes" followed by any valid assignment of candies $$$X_1, X_2, \dots, X_N$$$. Otherwise, print "No".

Deep within the Stanford archives, Donald Knuth has unveiled a lost volume of The Art of Computer Programming — but its chapters are scattered across an ancient, unrooted tree of cross-references. Each chapter carries a scholarly weight $$$w_i$$$, representing how much intellectual effort a reader must invest to digest it.

Knuth, ever the perfectionist, insists that the codex must be read starting from a single root chapter. Once a root is chosen, every other chapter sits at some depth $$$d_i$$$ — the number of edges on the unique path from the root to chapter $$$i$$$ (the root itself has depth $$$0$$$). The total reading cost of the codex is then defined as:

$$$$$$\mathrm{cost}(r) = \sum_{i=1}^{n} d_i(r) \cdot w_i,$$$$$$

where $$$d_i(r)$$$ is the depth of chapter $$$i$$$ when chapter $$$r$$$ is chosen as the root.

Because Knuth would never tolerate a suboptimal edition, your task is to determine the minimum possible total reading cost over all valid choices of root $$$r \in {1, 2, \dots, n}$$$.

You are given the tree with $$$n$$$ chapters (nodes) and $$$n-1$$$ cross-references (edges), together with the weight $$$w_i$$$ of each chapter. The tree is unrooted: any chapter may serve as the root.

Tony has just returned from an exchange program in Spain. Since he has not practiced competitive programming for a while, Alexis and Iván want to help him remember some topics about trees, so they give him the following problem.

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. Each node has a color, which can be either white or black, and a weight $$$w_u$$$.

Alexis and Iván give Tony $$$q$$$ operations. Each operation is one of the following types:

1. Change the weight of a node.
2. Change the color of every node in a subtree: white nodes become black, and black nodes become white.
3. Find the maximum possible total weight obtained by choosing some white nodes.

For the third type of operation, Tony cannot choose two nodes if one of them is an ancestor of the other. In other words, if Tony chooses a node, he cannot choose any of its ancestors or descendants.

Help Tony process all the operations and answer every query of the third type.

Rem, Alex, José, and Abraham are spending the weekend exploring La Plata in the middle of the Training Camp Argentina. During their trip, they decide to visit an attraction called La República de los Pibitos.

The attraction consists of $$$n$$$ locations, numbered from $$$1$$$ to $$$n$$$. From each location, there is exactly one path leading to another location. Therefore, La República de los Pibitos can be represented as a functional graph: every vertex has exactly one outgoing edge.

The graph is connected if the directions of the edges are ignored. Consequently, it contains exactly one directed cycle. Finding this cycle is one of the main attractions of La República de los Pibitos.

Abraham has already seen the map and knows which locations belong to the cycle. However, Rem, Alex, and José have not. Instead of showing them the map, Abraham challenges them to determine all the vertices of the cycle using at most $$$3n$$$ hints.

For each hint, they may choose two integers $$$u$$$ and $$$k$$$ ($$$1 \le u \le n$$$, $$$1 \le k \le n$$$). Starting at vertex $$$u$$$, consider the sequence of vertices visited while following the unique outgoing edge exactly $$$k$$$ times. Thus, the sequence contains the starting vertex and the $$$k$$$ vertices reached after each step.

Abraham will answer whether some vertex appears more than once in this sequence, or whether all visited vertices are distinct.

Using at most $$$3n$$$ such hints, Rem, Alex, and José must determine exactly which vertices belong to the unique directed cycle of La República de los Pibitos.

You can ask Abraham at most $$$3n$$$ hints.

To ask a hint, output a line in the following format: "? $$$u$$$ $$$k$$$", where $$$u$$$ is the starting vertex and $$$k$$$ ($$$1 \le k \le n$$$) is the number of edges that will be traversed by repeatedly following the unique outgoing edge.

After each hint, the evaluator will provide a single line containing:

• "Yes", if some vertex is visited more than once among the starting vertex and the $$$k$$$ vertices reached after each step;
• "No", if all these $$$k+1$$$ visited vertices are distinct.

Once you have determined all the vertices that belong to the unique directed cycle, output a line in the following format: "! $$$m$$$ $$$v_1$$$ $$$v_2$$$ $$$\dots$$$ $$$v_m$$$", where $$$m$$$ is the number of vertices in the cycle and $$$v_1,v_2,\dots,v_m$$$ are exactly the vertices that belong to it, in any order.

The graph is guaranteed to be a connected functional graph, meaning every vertex has exactly one outgoing edge and the underlying undirected graph is connected. Therefore, the graph contains exactly one directed cycle.

After printing each line, do not forget to output the end of the line and flush the output buffer. Otherwise, you will receive the "Idleness limit exceeded" verdict. To flush, use:

• "fflush(stdout)" or "cout.flush()" in C++;
• "System.out.flush()" in Java;
• "flush(output)" in Pascal;
• "stdout.flush()" in Python.

The interactor is adaptive. This means that the functional graph is not necessarily fixed before the interaction starts. Instead, the interactor may determine the hidden graph based on the queries made by your program, as long as all answers given during the interaction are consistent with at least one connected functional graph.

After competing virtually in all CodeForces rounds of the past three years, Geosé finally mastered graph problems. Graph coloring became his favorite topic in graph theory. While looking for a problem that combines this topic and geometry, he came up with the following problem:

You are given a convex polygon with $$$n$$$ vertices. For each pair of vertices, a line segment connecting them is drawn. Note that $$$\binom{n}{2}$$$ segments are drawn in total.

You must assign a color to each segment. A coloring is said to be valid if it satisfies the following condition:

• If two segments do not intersect, they must have different colors.

Two segments are considered to intersect if they share at least one common point, including endpoints. In particular, segments that share a vertex are also considered intersecting.

The problem asked to determine the minimum number of colors required to obtain a valid coloring. The first approach that Geosé tried was to write down the number of lines that are drown when $$$n$$$ vertices are given. Help Geosé to verify that the numbers that he wrote down are correct. Given $$$n$$$, print the number of lines that are drown.

This problem has nothing to do with problem A

Danna is the owner of "Dulce Alfajor", a renowned traditional Argentine sweets company. Due to her immense success, her factory has expanded into a massive complex with strict safety protocols.

The factory layout can be modeled as a directed acyclic graph with $$$n + 1$$$ rooms and $$$m$$$ directed halls, numbered from $$$0$$$ to $$$n$$$. Room $$$0$$$ is the main entrance, while rooms $$$1$$$ through $$$n$$$ are covered in sticky candy and need to be cleaned.

Danna needs to assign a color preference $$$C_i$$$ to each room $$$i$$$ ($$$1 \le i \le n$$$) each room needs to have one asigned color. She will then hire exactly one worker for each unique color used. The cleaning process operates under the following rules:

• Room $$$0$$$ contains all colors, so any worker can start their cleaning route there.
• Each worker is assigned a specific color $$$c$$$ and will only enter and clean rooms assigned color $$$c$$$.
• A worker assigned color $$$C_w$$$ starts at room $$$0$$$ and traverses a directed path $$$0 \to v_1 \to v_2 \to \dots \to v_m$$$ where for every room ($$$1 \lt = j \lt = m$$$) the color is the same as the color of the worker ($$$C_w = C_{v_j}$$$), cleaning every room along that path.
• Every room assigned color $$$c$$$ must be visited at least once and cleaned by that worker in a single route.
• Every room from $$$1$$$ to $$$n$$$ must be visited and cleaned by exactly one worker.
• Workers will always choose the path that maximizes the amount of rooms they can clean

It is guaranteed that there is a direct corridor from Room $$$0$$$ to every room $$$v \in [1, n]$$$, and no room $$$v \in [1, n]$$$ has a corridor leading to Room $$$0$$$.

Note that a worker can visit a room even if it has already been cleaned.

Help Danna determine the minimum number of unique colors $$$K$$$ required to clean the entire factory, and output a valid color assignment $$$C_1, C_2, \dots, C_n$$$ ($$$1 \le C_i \le K$$$) for rooms $$$1$$$ through $$$n$$$.

Charles is a big fan of minecraft-coins and a wise investor in this kind of currency. He has $$$n$$$ coins to invest, and he decides to invest each one of them separately.

The minecraft-coin market is Bubbaloo, but Charles knows it well: he knows that there are exactly $$$s$$$ possible returns $$$v_1, v_2, \dots, v_s$$$, all distinct from one another, and that a single investment yields the return $$$v_a$$$ with probability $$$p_a$$$. The returns of his $$$n$$$ investments are independent of each other and all follow this same distribution.

Let $$$X$$$ be the sum of the returns of all his investments. For some strange reason, Charles is interested in knowing the expected value of $$$X^k$$$. Please help Charles find out this piece of information.

Since the result may not be an integer, you must report it modulo $$$998244353$$$.

The Legendary Huron was trying to access huronforces.com, his favorite website for solving competitive programming problems. However, the website detected some suspiciously fast mouse movements and decided that he might actually be a very talented robot.

To prove that he is a real ferret, the website presented him with a CAPTCHA. Unfortunately, instead of asking him to identify traffic lights or bicycles, the CAPTCHA gave him a combinatorics problem.

He is given three integers $$$n$$$, $$$m$$$, and $$$k$$$. Consider all possible solutions to the following sum:

$$$$$$ \sum_{i=1}^{n} x_i=k. $$$$$$

where every $$$x_i$$$ is a non-negative integer.

For each such solution, the CAPTCHA computes the following product:

$$$$$$ \prod_{i=1}^{m} x_i. $$$$$$

The Legendary Huron must find the sum of this value over all possible solutions of the equation. Help the Legendary Huron solve the CAPTCHA so he can finally access huronforces.com. Since the answer may be huge, print it modulo $$$676767639049076737$$$.

Ikuyo Kita, better known as ¡Ya llegué, vámonos!, was declared Protectora de la Soberanía after the CIA captured Maduro.

In her first decree, Kita designed a system to provide internet access to everyone. She can place up to two base stations and coverage is provided within a circular radius around each central. Kita wants to minimize the sum of these two radii while ensuring that every person is covered by at least one central.

Problem E looks so hard...

Magaly and Danna are competing in a game called "Choose Then Win". The game is played with an ordered list of $$$n$$$ boxes, numbered from $$$1$$$ to $$$n$$$.

For a chosen integer $$$k$$$ ($$$1 \le k \le n$$$), a player selects a sequence of $$$k$$$ distinct boxes. Once selected, the chosen boxes are opened strictly in increasing order of their original indices, $$$i_1 \lt i_2 \lt \dots \lt i_k$$$.

When opening the $$$j$$$-th chosen box ($$$1 \le j \le k$$$), the box with index $$$i_j$$$ awards a score of $$$x_{i_j}$$$ with probability $$$\frac{p_{i_j} \cdot j}{q_{i_j}}$$$ Otherwise, it awards $$$0$$$ score.

Magaly wants to beat Danna by maximizing her total expected score. Assuming Magaly selects her $$$k$$$ boxes optimally, determine the maximum expected score she can obtain for every integer $$$k$$$ from $$$1$$$ to $$$n$$$.

Leonardo Javier "El Chicharito" Toral Hernández had always wanted to watch his beloved Cruz Azul play. Unfortunately, that year Mexico was hosting the World Cup, forty years after the previous tournament held there in 1986. Jorge convinced Leonardo that supporting Mexico had to come before supporting Cruz Azul, so he invited him to the FanFest to watch Mexico play against England.

Everyone was enjoying the match, which Mexico seemed to dominate. However, England eventually took the lead, and Leonardo even wanted to enter the field in place of Memote Martínez. Jorge stopped him—although perhaps he should not have.

The FanFest was divided into $$$n$$$ rows, numbered from $$$1$$$ to $$$n$$$. Initially, row $$$i$$$ contained $$$a_i$$$ fans wearing Mexico jerseys.

During the event, more fans could join the celebration. In one operation, the organizers brought $$$x$$$ new fans to every row from $$$l$$$ to $$$r$$$.

For promotional pictures, the organizers could select a range of rows from $$$l$$$ through $$$r$$$ and ask the fans to perform a routine called "Quiere Volar". In each selected row, all fans had to be divided into groups of size $$$g$$$. The same value of $$$g$$$ had to be used for every selected row. Fans from different rows could not be mixed, and no fan could be left out.

For every promotional picture query, determine the maximum possible value of $$$g$$$.

Miguel and Misael have a weighted tree with $$$n$$$ vertices. They are very proud of their tree and believe that its structure is already perfect. Aaron, however, disagrees. He thinks that the tree would be better if its connected components had smaller diameters, so he decides to modify it by removing some of its edges. For each integer $$$k$$$ from $$$1$$$ to $$$n-1$$$, Aaron wants to remove exactly $$$k$$$ edges from the tree. After doing so, the tree is divided into $$$k+1$$$ connected components.

The diameter of a connected component is the maximum distance between any pair of its vertices, where the distance between two vertices is the sum of the weights of the edges on the unique path connecting them. The diameter of the resulting forest is defined as the maximum diameter among all its connected components.

For every $$$k$$$ from $$$1$$$ to $$$n-1$$$, determine the minimum possible diameter of the resulting forest that Aaron can obtain after removing exactly $$$k$$$ edges.

Jorge, as a mathematics enthusiastic, likes to learn about fractals. He learned recently about the Vicsek Fractal. The Vicsek fractal, also known as the Vicsek snowflake, is a self-similar fractal named after the Hungarian physicist Tamás Vicsek. It is generated by repeatedly arranging smaller copies of the same figure according to a fixed pattern. Despite this simple construction rule, increasingly complex patterns emerge as the process is repeated.

In this problem, Jorge represents the Vicsek fractal using * and . characters.

The fractal of level $$$0$$$ consists of a single *:

*

For every $$$n \ge 1$$$, the fractal of level $$$n$$$ is constructed from the fractal of level $$$n-1$$$. Since the previous fractal has size $$$3^{n-1} \times 3^{n-1}$$$, consider a $$$3 \times 3$$$ arrangement of square blocks, where each block has size $$$3^{n-1} \times 3^{n-1}$$$. Place an exact copy of the level $$$n-1$$$ fractal in the four corner blocks and in the center block. Every position in the remaining four blocks is filled with . characters. In other words, if F represents the complete fractal of level $$$n-1$$$, and E represents an equally sized block containing only . characters, the construction is:

F E F
E F E
F E F

where adjacent blocks are printed without spaces between them.

For example, the fractal of level $$$1$$$ is:

*.*
.*.
*.*

and the fractal of level $$$2$$$ is:

*.*...*.*
.*.....*.
*.*...*.*
...*.*...
....*....
...*.*...
*.*...*.*
.*.....*.
*.*...*.*

This construction is applied recursively for every higher level. More precisely, to construct the fractal of any level $$$n \ge 2$$$, divide its $$$3^n \times 3^n$$$ grid into nine equal square regions of size $$$3^{n-1} \times 3^{n-1}$$$. The regions in the top-left, top-right, center, bottom-left, and bottom-right positions must each contain an exact copy of the level $$$n-1$$$ fractal. The top-center, middle-left, middle-right, and bottom-center regions contain only . characters. Thus, every level is completely determined by the previous one, and the resulting fractal of level $$$n$$$ always has exactly $$$3^n$$$ rows and $$$3^n$$$ columns.

Given an integer $$$n$$$, help Jorge to print the Vicsek fractal of level $$$n$$$.