Sulfox the fennec fox gives you $$$n$$$ sets $$$S_1,S_2,\ldots,S_n$$$, each containing distinct integers between $$$0$$$ and $$$2^m-1$$$.

You may perform the following operation any number (possibly zero) of times: choose an integer $$$x$$$ with $$$0\le x \lt 2^m$$$, and for every $$$i=1,2,\ldots,n$$$, insert $$$x$$$ into $$$S_i$$$ if it is not already present.

A set $$$S$$$ is called XOR-closed if, for every $$$x,y\in S$$$, we have $$$x\oplus y\in S$$$, where $$$\oplus$$$ denotes the bitwise exclusive-OR operation.

Find the minimum number of operations required to make all $$$S_i$$$ XOR-closed, and construct any sequence of operations achieving this minimum.

Natsu is eating bread at Sensei's café when a piece of bread falls onto the floor and starts rolling.

The fallen bread can be regarded as a convex polygon in a two-dimensional plane. Its $$$n$$$ vertices, listed in counterclockwise order, are $$$A_1,A_2,\ldots,A_n$$$. The vertices are pairwise distinct, and no three vertices are collinear. The floor can be regarded as the horizontal line $$$y=0$$$.

Initially, the bread touches the floor along edge $$$(A_n,A_1)$$$. Let the position of vertex $$$A_n$$$ at this moment be the origin. The bread rolls in the positive direction of the $$$x$$$-axis; that is, $$$A_n=(0,0)$$$ and $$$A_1=(x_1,0)$$$, where $$$x_1 \gt 0$$$. The bread then starts rolling. The rolling process can be abstracted as an infinite sequence of rotations performed in order. In the $$$i$$$-th rotation, the entire bread is rotated clockwise about the current position of vertex $$$A_{((i-1)\bmod n)+1}$$$ until $$$A_{(i\bmod n)+1}$$$ touches the floor for the first time, that is, until its $$$y$$$-coordinate becomes $$$0$$$ for the first time.

As a romantic philosopher, Natsu considers the rolling of the bread to be a coincidental and romantic event. For the sake of this romance, after the $$$k$$$-th rotation, Natsu records the distance $$$L(k)$$$ rolled by the bread and the area $$$S(k)$$$ swept out by the bread. You need to calculate their ratio as $$$k$$$ tends to infinity, namely:

$$$$$$ \lim_{k\to +\infty}\frac{S(k)}{L(k)} $$$$$$

The distance $$$L(k)$$$ rolled by the bread after the $$$k$$$-th rotation is defined as the distance from the origin to the position of vertex $$$A_{(k\bmod n)+1}$$$ when the $$$k$$$-th rotation ends. The area $$$S(k)$$$ swept out by the bread after the $$$k$$$-th rotation is defined as the area of the union of all regions covered by the convex-polygon bread at all moments from the beginning of the first rotation to the end of the $$$k$$$-th rotation.

You are given a tree with $$$n$$$ vertices. Vertex $$$i$$$ has a weight $$$z_i$$$. The $$$n-1$$$ edges are numbered from $$$1$$$ to $$$n-1$$$ in the order they are given in the input.

You have to answer $$$q$$$ independent queries. A query is given by three integers $$$l$$$, $$$r$$$, $$$f$$$ with $$$1 \le l \le f \le r \le n-1$$$. For this query, build a graph on the $$$n$$$ vertices that contains exactly the edges whose index lies in $$$[l, r]$$$, except that edge number $$$f$$$ is deleted. Formally, the edge set is $$$\{\, i : l \le i \le r,\ i \neq f \,\}$$$.

This graph is a forest. The weight of a connected component is the sum of the weights of the vertices it contains (an isolated vertex forms a component of weight equal to its own weight). For each query output the maximum component weight.

Segment tree is a data structure based on the divide-and-conquer algorithm, but this has nothing to do with this problem. It's just to make the title start with D.

For this problem, a segment tree is a perfect binary tree. A segment tree of depth $$$n$$$ has exactly $$$2^{n+1}-1$$$ nodes. Note that the root has depth $$$0$$$, so a segment tree of depth $$$n$$$ has $$$n+1$$$ levels.

To make the structure of a segment tree easier to describe, we assign indices to its nodes. The root is assigned index $$$1$$$. Every non-leaf node is assigned an index $$$k$$$ satisfying $$$1\leq k \lt 2^n$$$. It has exactly two children: its left child has index $$$2k$$$, and its right child has index $$$2k+1$$$.

Each node of a segment tree also has a value. Let $$$a_k$$$ denote the value of node $$$k$$$. For every non-leaf node $$$k$$$, its value $$$a_k$$$ must be the maximum of the values of its two children; that is, $$$$$$ a_k=\max\{a_{2k},a_{2k+1}\}. $$$$$$

The leaf nodes have indices $$$2^n,2^n+1,\ldots,2^{n+1}-1$$$, and their values must form a permutation of $$$1,2,\ldots,2^n$$$. In other words, the elements of the sequence $$$a_{2^n},a_{2^n+1},\ldots,a_{2^{n+1}-1}$$$ must be pairwise distinct integers, and $$$1\leq a_{2^n+i}\leq 2^n$$$ must hold for every $$$0\leq i \lt 2^n$$$.

There are now $$$q$$$ constraints. The $$$i$$$-th constraint is of the form $$$(u_i,x_i)$$$. Here, $$$u_i$$$ is a node index and $$$x_i$$$ is a specified value; the constraint requires the value $$$a_{u_i}$$$ of node $$$u_i$$$ to be equal to $$$x_i$$$. Calculate the number of segment trees satisfying all $$$q$$$ constraints, or equivalently, the number of distinct valid sequences $$$a_1,a_2,\ldots,a_{2^{n+1}-1}$$$. Output the answer modulo $$$998244353$$$.

The exponent of a group is the least common multiple of the orders of all elements in the group, but this has nothing to do with this problem. It's just to make the title start with E.

Little Ma gives you a positive integer $$$n$$$.

For each integer $$$a$$$ with $$$1 \le a \le n$$$, define $$$\operatorname{ord}_n(a)$$$ as the smallest positive integer $$$x$$$ satisfying:

$$$$$$ a^x \equiv 1 \pmod n $$$$$$

If no such positive integer $$$x$$$ exists, define $$$\operatorname{ord}_n(a)=0$$$.

Compute:

$$$$$$ \sum_{a=1}^{n}\operatorname{ord}_n(a) $$$$$$

Regarding $$$\equiv$$$: $$$\equiv$$$ is the congruence symbol in number theory. For three integers $$$a, b, p$$$, the mathematical expression $$$a \equiv b \pmod p$$$ is equivalent to the existence of an integer $$$k$$$ satisfying $$$a - b = kp$$$.

Ohto Ai has an unrooted tree with $$$N$$$ vertices. Let the current tree be $$$G=(V,E)$$$.

A path in a tree is a sequence of distinct vertices $$$v_1,v_2,\ldots,v_k$$$ such that $$$\{v_i,v_{i+1}\}\in E$$$ for every $$$1\le i \lt k$$$.

A diameter of a tree is a path containing the maximum possible number of vertices.

While $$$|V| \gt 1$$$, Ohto Ai may perform the following fold operation: Choose any diameter $$$d_1,d_2,\ldots,d_k$$$ of the current tree, listed in order from one endpoint to the other.

Define a function $$$f:V\to V$$$ by:

$$$$$$ f(v)= \begin{cases} d_{\min\{i,k-i+1\}}, & \text{if }v=d_i\text{ for some }1\le i\le k\\ v, & \text{otherwise} \end{cases} $$$$$$

The tree after the fold is $$$G'=(V',E')$$$, where:

$$$$$$ \begin{aligned} V'&=\{f(v)\mid v\in V\} \\ E'&= \bigl\{ \{f(u),f(v)\} \mid \{u,v\}\in E,\ f(u)\ne f(v) \bigr\} \end{aligned} $$$$$$

In other words, vertices at symmetric positions on the chosen diameter are merged. Edges whose endpoints are merged into the same vertex disappear, and if multiple edges become edges between the same pair of vertices, only one copy is kept.

It can be shown that $$$G'$$$ is still a tree.

Ohto Ai repeatedly performs fold operations until $$$|V|=1$$$. Find the maximum possible number of operations.

Background. Lately, Iochi Mari has had a small worry on her mind: as Antique Seraphim grows in popularity, her busy performance schedule leaves her little time to visit Schale. Meanwhile, Schale's Sensei misses her just as much. He therefore decides to rearrange her schedule, keeping the group's activities running smoothly while giving her some well-earned rest. Can you help poor Sensei count the schedules satisfying the conditions below?

Consider $$$n$$$ vertices arranged in a cycle and $$$n$$$ distinct edges $$$e_1,e_2,\ldots,e_n$$$. For each $$$1\le i\le n$$$, edge $$$e_i$$$ connects vertex $$$i$$$ to vertex $$$i+1$$$, where vertex $$$n+1$$$ is identified with vertex $$$1$$$. Note that when $$$n=1$$$, $$$e_1$$$ is a self-loop; when $$$n=2$$$, $$$e_1$$$ and $$$e_2$$$ are two distinct parallel edges.

Intervals. For any $$$l,r\in\{1,2,\ldots,n\}$$$, the interval $$$[l,r]$$$ is defined as follows:

• If $$$l \lt r$$$, it covers vertices $$$l,l+1,\ldots,r$$$ and edges $$$e_l,e_{l+1},\ldots,e_{r-1}$$$.
• If $$$l \gt r$$$, it covers vertices $$$l,l+1,\ldots,n,1,2,\ldots,r$$$ and edges $$$e_l,e_{l+1},\ldots,e_n,e_1,e_2,\ldots,e_{r-1}$$$.
• If $$$l=r$$$, it covers only vertex $$$l$$$ and no edges.

For example, when $$$n=4$$$, the interval $$$[3,2]$$$ covers vertices $$$3,4,1,2$$$ and edges $$$e_3,e_4,e_1$$$.

We say interval $$$A$$$ contains interval $$$B$$$ if every vertex and every edge covered by $$$B$$$ is also covered by $$$A$$$.

Valid sets. A set $$$T$$$ of intervals is called valid if no interval in $$$T$$$ contains another interval in $$$T$$$. The empty set is also valid.

Your task is to count valid sets under two different coverage limits. For a valid set $$$T$$$, define: $$$$$$ \begin{aligned} f(T) &= \max_{\text{edge } e} \left|\{I\in T \mid I \text{ covers } e\}\right|\\ g(T) &= \max_{\text{vertex } v} \left|\{I\in T \mid I \text{ covers } v\}\right| \end{aligned} $$$$$$ For the empty set, define $$$f(\varnothing)=g(\varnothing)=0$$$.

For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, compute the following two counts separately:

1. The number of valid sets $$$T$$$ satisfying $$$f(T)\le k$$$.
2. The number of valid sets $$$T$$$ satisfying $$$g(T)\le k$$$.

Output all counts modulo $$$998244353$$$.

This is an interactive problem.

Background. On August 9, Sensei and Seia attend the Hidden Track. Blue Archive 3rd Anniversary Concert in Shanghai. Having arrived late, they are stuck in a remote corner, but Seia knows a hidden route to the second floor. Can you help poor Sensei find the way by following Seia's cryptic query rules?

For each test case, the interactor hides a permutation $$$p=(p_1,p_2,\ldots,p_n)$$$ of $$$\{0,1,\ldots,n-1\}$$$. When $$$n\ge 2$$$, it is guaranteed that $$$p_1 \lt p_n$$$. You may think of it as a hidden path, where $$$p_i$$$ and $$$p_{i+1}$$$ are connected by an edge for every $$$1\le i \lt n$$$. Your task is to find the hidden permutation using queries.

Let $$$k=\lceil\log_2 n\rceil$$$. In each query, you choose two integers $$$m$$$ and $$$v$$$, where $$$0\le m \lt 2^k$$$, and either $$$v=-1$$$ or $$$0\le v \lt n$$$. The integer $$$m$$$ determines a set of vertices: $$$$$$ B(m)= \left\{ x\mid 0\le x \lt n,\ \operatorname{popcount}(x\mathbin{\&}m)\text{ is odd} \right\} $$$$$$

Here, $$$\mathbin{\&}$$$ denotes the bitwise AND operation, and $$$\operatorname{popcount}(x)$$$ denotes the number of $$$1$$$-bits in the binary representation of $$$x$$$.

The query set $$$S$$$ is constructed as follows.

First, let $$$S=B(m)$$$.

If $$$v=-1$$$, do nothing; otherwise, toggle whether $$$v$$$ belongs to $$$S$$$: remove $$$v$$$ if $$$v\in S$$$, and add $$$v$$$ otherwise.

The interactor then counts the edges of the hidden path with exactly one endpoint in $$$S$$$. Let this number be: $$$$$$ c(S)= \left| \left\{ i\mid 1\le i \lt n,\ \left|\{p_i,p_{i+1}\}\cap S\right|=1 \right\} \right| $$$$$$

The interactor returns $$$c(S)\bmod 3$$$.

For each test case, you may make at most $$$nk$$$ queries, with $$$k=\lceil\log_2 n\rceil$$$ as defined above. You must reconstruct the hidden permutation $$$p$$$ within this query limit.

The interactor is non-adaptive: the hidden permutation for each test case is fixed before the interaction begins and does not change throughout the interaction.

For each test case, you may perform the following two types of operations. The number of queries must not exceed $$$nk$$$, with $$$k=\lceil\log_2 n\rceil$$$ as defined above.

Query: Output a line of the form ? m v, where $$$0 \le m \lt 2^k$$$, and either $$$v=-1$$$ or $$$0 \le v \lt n$$$. Here $$$m,v$$$ must be integers. Then read an integer $$$r\in\{0,1,2\}$$$, whose value is $$$c(S) \bmod 3$$$.

Answer: Output a line of the form ! $$$q_1\ q_2\ \ldots\ q_n$$$, where $$$(q_1,q_2,\ldots,q_n)$$$ must be exactly equal to the hidden permutation $$$(p_1,p_2,\ldots,p_n)$$$.

Only operations of the form ? count toward the query limit. If the interactor returns $$$-1$$$ at any point, your program must terminate immediately. Continuing the interaction after receiving $$$-1$$$ may result in an arbitrary verdict.

After printing a query or the answer, do not forget to output the end of the line and flush the output. Otherwise, your submission may receive any verdict. To do this, use: $$$\texttt{fflush(stdout)}$$$ or $$$\texttt{cout.flush()}$$$ in C++; $$$\texttt{System.out.flush()}$$$ in Java; $$$\texttt{flush(output)}$$$ in Pascal; $$$\texttt{stdout.flush()}$$$ in Python.

An ancient island suffered divine punishment, and the roads connecting its various regions were shattered.

The island can be regarded as an undirected graph containing $$$n$$$ vertices, numbered $$$1,2,\ldots,n$$$.

Initially, the roads on the island form an ordered rooted tree rooted at vertex $$$1$$$. The children of each vertex have a fixed left-to-right order, which is given in the input. In particular, the root has at least two children.

Starting from the root, perform a depth-first search, always recursively visiting the children of each vertex from left to right. Suppose there are $$$k$$$ leaf vertices. In the order in which they are first visited, they are $$$p_1,p_2,\ldots,p_k$$$. Here, a leaf vertex means a vertex of degree $$$1$$$; since the root has at least two children, it cannot be a leaf vertex.

Besides the $$$n-1$$$ roads in the tree, there are also $$$k-1$$$ roads built between consecutive leaves. For every $$$1\leq i \lt k$$$, the $$$i$$$-th road connects leaf vertex $$$p_i$$$ and leaf vertex $$$p_{i+1}$$$. That is, all leaves are connected consecutively into a chain in the above DFS order, and there are $$$n+k-2$$$ roads on the island in total.

When the divine punishment occurs, each road is independently destroyed with probability $$$\frac{1}{2}$$$, or retained with probability $$$\frac{1}{2}$$$, while all vertices still exist. The vertices and the remaining roads form several connected components. Let $$$X$$$ be the number of connected components of the island. Please calculate the expected value of $$$X$$$. Here a connected component is defined as a maximal connected subgraph. Note that an isolated vertex also counts as a component.

It can be proven that the answer is a rational number. Suppose the answer in lowest terms is $$$\frac{a}{b}$$$. You only need to output a nonnegative integer $$$x$$$ satisfying $$$0\leq x \lt 998244353$$$ and $$$bx\equiv a\pmod {998244353}$$$, namely, the answer modulo $$$998244353$$$.

As the chief judge of The 2026 ICPC Asia EC Regionals Online Contest (II), Mr. J has diligently finished preparing and reviewing all the problems. Today, the contest is finally about to begin!

Since last year's contest was harshly criticized, Mr. J cares greatly about this year's reputation. Therefore, he has set himself a goal: this year's contest should not receive too many negative reviews. To quantify the negative impact of these reviews, Mr. J assigns a score to each type of negative review:

$$$$$$ \begin{array}{|l|c|} \hline \text{Type of negative review} & \text{Score} \\ \hline \text{WrongProblem}X & 100 \\ \text{SameProblem}X & 30 \\ \text{UnreasonableProblemArrangement} & 10 \\ \text{UnreasonableLimitForProblem}X & 5 \\ \text{WeakTestsForProblem}X & 3 \\ \text{BadProblem}X & 1 \\ \hline \end{array} $$$$$$

If a negative review does not match any of the negative-review types in the table, its score is $$$0$$$. Matching is case-sensitive, and the string must exactly match the corresponding form in the table. For a type containing $$$X$$$, $$$X$$$ is a placeholder; when matching, it must be replaced by exactly one uppercase English letter from $$$\{\texttt{A},\texttt{B},\ldots,\texttt{L}\}$$$.

If you need to copy the concrete string corresponding to a type of negative review, we recommend referring to the first test case in the sample.

Mr. J has an expected total negative-review score $$$P$$$ in mind. If the total score of all negative reviews is greater than $$$P$$$, Mr. J is a Joker; otherwise, Mr. J remains a qualified Judger. You have now collected all $$$n$$$ negative reviews. Determine whether Mr. J is a Joker or a Judger.

Let $$$a$$$ be an array of length $$$n$$$. Define $$$\operatorname{mex}(a)$$$ as the smallest non-negative integer that does not appear in $$$a$$$. For example:

• $$$\operatorname{mex}([4, 0, 2, 1]) = 3$$$
• $$$\operatorname{mex}([-2, -4, 3]) = 0$$$

Define a $$$k$$$-transformation as follows: for each index $$$i$$$ ($$$1 \leq i \leq n$$$), independently choose to either keep $$$a_i$$$ unchanged or replace it with $$$k - a_i$$$. After all choices are made, we obtain a new array $$$a'$$$.

Define $$$k$$$-$$$\operatorname{mex}(a)$$$ as the maximum possible value of $$$\operatorname{mex}(a')$$$ among all arrays $$$a'$$$ that can be obtained from $$$a$$$ via a $$$k$$$-transformation.

You must answer $$$q$$$ queries. Each query provides a non-negative integer $$$k$$$; compute $$$k$$$-$$$\operatorname{mex}(a)$$$ for each query.

To reduce the output size, you are only required to output the bitwise XOR (exclusive-OR) of the answers over all $$$q$$$ queries.

You have fallen into a Loop trap. To escape from the Loop trap, you need to solve the following puzzle:

You are given an integer sequence $$$a_0,a_1,\ldots,a_{n-1}$$$ of length $$$n$$$.

Construct an $$$n\times n$$$ grid, with both row and column indices starting from $$$0$$$. The $$$0$$$-th column, from top to bottom, is $$$a_0,a_1,\ldots,a_{n-1}$$$. Starting from the $$$1$$$-st column, each column is obtained by cyclically shifting the previous column down by one cell.

Formally, if the number in row $$$i$$$ and column $$$j$$$ is $$$b_{i,j}$$$, then

$$$$$$ b_{i,j}= \begin{cases} a_i & j=0 \\ b_{(i+n-1)\bmod n,j-1} & j \gt 0 \end{cases} $$$$$$

You are at the upper-left corner $$$(0,0)$$$. In each step, you may only move right or down, until you reach the lower-right corner $$$(n-1,n-1)$$$. Every grid cell visited by the path is counted, including the starting and ending cells.

Please find the minimum possible sum of the weights of the grid cells visited by the path.