Recently, Colin became addicted to the theory of additive combinatorics, which is about counting additive structures in sets. This theory has seen exciting developments and dramatic changes in direction in recent years, thanks to its connections with areas such as number theory, ergodic theory, and graph theory.

One fundamental problem in additive combinatorics is sumsets. For two sets of integers $$$A,B$$$, we define the sumset of $$$A$$$ and $$$B$$$ to be the set of all sums of an element from $$$A$$$ with an element from $$$B$$$. That is, $$$$$$ A+B=\{a+b:a\in A, b\in B\} $$$$$$ Now Colin gives you three sets $$$A,B,C$$$; could you determine whether $$$C$$$ is the sumset of $$$A$$$ and $$$B$$$?

Azora the corgi loves music but cannot catch the rhythm well, especially when counting beats! After hard research on music theory, Azora found a hidden theorem: There won't be a note crossing the boundary between the beats for modern songs (or for most barking sessions for that matter).

To simplify the problem, we assume that a modern song consists of several sequential notes whose lengths are $$$l_1,l_2,\cdots,l_n$$$ milliseconds. The notes will be played one by one, which means the song will start playing the first note at time $$$0$$$, and the second note at the beginning of the $$$l_1+1$$$ milliseconds, and the third note at the beginning of the $$$l_1+l_2+1$$$ milliseconds, and so on.

If the length of the beat is $$$L$$$ milliseconds, then there should not exist any note that is playing but not starting to play at the beginning of the $$$kL$$$ milliseconds, for any non-negative integer $$$k$$$. Formally, there should not exist any note $$$i$$$ such that $$$\sum_{j=1}^{i-1} l_j \lt kL$$$ but $$$\sum_{j=1}^il_j \gt kL$$$ for any non-negative integer $$$k$$$.

Now Azora has received a new song from her humans, and she wants to practice counting beats before she barks the song back to them. To challenge herself, Azora wants to find the smallest possible length of a beat, such that it satisfies the theorem. Can you help her?

Colin is a first-year Ph.D. student, working hard with many beautiful but unrealistic academic fantasies. He aims to design clever algorithms for essential problems and publish them in top conferences.

There are $$$n$$$ conferences Colin is interested in. The $$$i$$$-th one starts receiving submissions at 8 a.m. on the day $$$r_i$$$ , and the deadline to submit papers is 8 p.m. on the day $$$d_i$$$. After the submitted paper has been reviewed by the experts, the authors will be notified of the result at 2 p.m. on the day $$$t_i$$$. The result is either Accepted or Rejected. In addition, there is an impact factor $$$w_i$$$ for the $$$i$$$-th conference, which represents the reputation of the conference. To simplify the problem, we guarantee that the impact factors of conferences are pairwise distinct.

But recently, he sadly found that his papers were rejected again and again. By summarizing the past data, Colin raised an assumption: the probability of acceptance for a paper is equal to the number of times it has been submitted over the impact factor of the conference. Formally, if Colin submits a paper to the $$$i$$$-th conference now, and it has already been submitted for $$$k$$$ times (including this time), then the probability of acceptance this time is equal to $$$$$$ \min(1, \frac{k}{w_i}) $$$$$$ Now Colin has $$$m$$$ papers he would like to submit, and the $$$i$$$-th paper will be finished at 9 a.m. on the day $$$f_i$$$. We say a conference is available at a time if it has already started receiving papers, but its deadline hasn't passed. Once Colin finishes each paper, if there does not exist any available conference at that time, then he will think this paper is not welcome and won't submit it anymore; if there exists any available conference at that time, he will instantly submit it to one of the available conferences with the highest impact factor. Then Colin will repeat as follows:

On the day of receiving the notification of the result, if the paper is Rejected:

• If any available conference exists at that time, Colin will instantly submit the paper to one of the available conferences with the highest impact factor and wait for the result.
• Otherwise, Colin will be pretty upset about this paper and won't submit it anymore, even if there are some further conferences that haven't started receiving papers.

If the paper is Accepted, Colin will earn reputation points, which are equal to the impact factor of the conference that accepts the paper. He will not submit the paper to other conferences.

Colin would like to ask, if his assumption is valid, what is the expected value of reputation points he can earn from each paper? If a paper is not accepted in the end, then Colin will earn $$$0$$$ reputation points from it. Please find the answer modulo $$$998244353$$$.

Notice that all the times mentioned are in AOE time, and there is no need to consider any issues related to time zones.

Recently, Colin found that DeepSeek is such a useful AI that he can always give it problems he meets and receive lots of good suggestions, especially when Colin turns on the DeepThink option: DeepSeek will show the procedure of thinking, and it makes everything look so clear and convincing!

Although DeepSeek's thinking procedure does look like a human's, Colin found a phenomenon that always starts with, "Okay, so I want to figure out how to..."

Colin wants to build an extraordinary AI by himself: ColinSeek, but since Colin knows too little about AI, he decides to start by imitating. Now, please help Colin write the very first code for the ColinThink option of ColinSeek:

When the user asks in the format How to xxx?, show the thinking procedure as Okay, so I want to figure out how to xxx. The last part (xxx) is the same as the user's question.

This is the easy version of the problem. The only difference between the versions is the range of $$$n$$$.

Colin likes to play the Happy Eliminate game to kill time. Usually, the player is asked to find a fixed pattern in the given content, then eliminate it. The variety of patterns makes the game rich and exciting.

To research which pattern makes the game most exciting, Colin built a model: The contents given to the user are represented as a string $$$s$$$, and the pattern is another string $$$t$$$. In each turn of the game, the user can do one of the following two operations, and the game will be kept going until $$$t$$$ becomes empty:

• Delete the last character of the pattern $$$t$$$.
• Find a substring of $$$s$$$ that is equal to $$$t$$$, say $$$s[i,j] = t$$$, then delete several characters in the prefix of $$$s$$$ until $$$s[i+1]$$$, i.e., (make $$$s$$$ become $$$s[i+1,|s|]$$$), and then delete the last character of the pattern $$$t$$$.

Colin defines a game's excitement as the maximum number of times the second operation can be performed. He wants to find the best pattern to maximize excitement, but he has no idea how to construct it. Thus, he turned it over to you, the top player of Happy Eliminate.

Recall that $$$|s|$$$ represents the length of the string $$$s$$$, and $$$s[i,j]$$$ represents the substring of the string $$$s$$$, starting from the $$$i$$$-th character to the $$$j$$$-th character (including the $$$i$$$-th and the $$$j$$$-th).

This is the hard version of the problem. The only difference between the versions is the range of $$$n$$$.

Colin likes to play the Happy Eliminate game to kill time. Usually, the player is asked to find a fixed pattern in the given content, then eliminate it. The variety of patterns makes the game rich and exciting.

To research which pattern makes the game most exciting, Colin built a model: The contents given to the user are represented as a string $$$s$$$, and the pattern is another string $$$t$$$. In each turn of the game, the user can do one of the following two operations, and the game will be kept going until $$$t$$$ becomes empty:

• Delete the last character of the pattern $$$t$$$.
• Find a substring of $$$s$$$ that is equal to $$$t$$$, say $$$s[i,j] = t$$$, then delete several characters in the prefix of $$$s$$$ until $$$s[i+1]$$$, i.e., (make $$$s$$$ become $$$s[i+1,|s|]$$$), and then delete the last character of the pattern $$$t$$$.

Colin defines a game's excitement as the maximum number of times the second operation can be performed. He wants to find the best pattern to maximize excitement, but he has no idea how to construct it. Thus, he turned it over to you, the top player of Happy Eliminate.

Recall that $$$|s|$$$ represents the length of the string $$$s$$$, and $$$s[i,j]$$$ represents the substring of the string $$$s$$$, starting from the $$$i$$$-th character to the $$$j$$$-th character (including the $$$i$$$-th and the $$$j$$$-th).

The annual GXCPC (Grand XOR Counting Problem Challenge) is here again! This year, Judge Colin has prepared another super difficult counting problem for the contestants! Can you slay this ultimate counting problem and win the championship?

Eva has two magic parameters $$$k_1$$$ and $$$k_2$$$.

Colin has two integer sequences $$$a_1,a_2,\cdots,a_n$$$ and $$$b_1,b_2,\cdots,b_n$$$.

They want to know how many pairs of indices $$$(i,j)$$$ satisfy:

• $$$1\le i \lt j\le n$$$
• $$$k_1 \oplus a_i \oplus a_j \lt k_2 \oplus b_i \oplus b_j$$$

Where $$$\oplus$$$ represents the bitwise XOR operation.

Colin is a big fan of Hollow Knight. The grand world view of Hollownest and the distinctive bosses deeply attracted him, and fortunately, the second generation, Hollow Knight: Silksong, will be released very soon! Silksong follows Hornet, the former princess of Hollow Knight's fallen kingdom of Hallownest and a supporting character in that game, as she is forced to explore a totally new land.

So many people are excited to play Silksong! There's even a comment in 2020 on bilibili that has become famous: "Actually, I'm pretty lucky. I just got into Hollow Knight 1, and Hollow Knight 2 is about to come out." It has received over 28,000 likes now.

Anyway, the most recent news is that Silksong will be released this year! The most exciting news is that people will have the chance to play the demo in Australia on September 18, 2025.

It cannot be luckier for those who haven't played Hollow Knight ever! So Colin strongly suggested that Eva play Hollow Knight before the second generation was released. To value how lucky Eva is, Colin defines the luckiness to be the number of dates between the first day Eva starts to play and the day of demo-play.

Given the date Eva starts to play Hollow Knight, can you help Colin calculate how lucky Eva is?

Recently, Colin has been learning the relationship between sets and bitmasks. We can use binary numbers (bitmasks) to represent sets, and if some bits are 1 in the bitmask, then it means that the sets include the elements corresponding to the indices of these bits.

Now Colin has $$$n$$$ non-negative integers $$$a_1, a_2, \cdots, a_n$$$ and all these integers are less than $$$2^k$$$. Now Colin tries to use the concept of bitmasks and sets to understand the relationship between these integers.

For a non-negative integer $$$x \in\left[0,2^k\right)$$$, Colin defines that $$$a_i$$$ is feasible with $$$a_j$$$ under the augmentation of $$$x$$$, if and only if the set corresponding to the bitmask $$$a_i+x$$$ is a subset of the set corresponding to the bitmask $$$a_j+x$$$. Then Colin uses $$$f(x)$$$ to represent the number of all the pairs $$$(i, j)$$$ such that $$$a_i$$$ is feasible with $$$a_j$$$ under the augmentation of $$$x$$$.

Now Colin would like to ask you to calculate the sum of all the $$$f(x)$$$, modulo $$$998244353$$$ .

Formally, please calculate

$$$$$$ \left(\sum_{x=0}^{2^k-1} f(x)\right) \bmod 998244353 $$$$$$

Recently, Eva learned several advanced data structure techniques for trees. To show her progress, she asked Colin to give her a challenging problem about tree statistics.

However, Colin just gave her a very typical problem:

Given a tree with $$$n$$$ vertices, and vertex $$$1$$$ is the root. Each vertex has an integer weight $$$w_i$$$.

Let $$$lca(u,v)$$$ represent the lowest common ancestor of the vertices $$$u$$$ and $$$v$$$.

Given two integer sequences $$$a_1,a_2,\cdots,a_x~(1\le a_i\le n)$$$ and $$$b_1,b_2,\cdots,b_y~(1\le b_i\le n)$$$. Define the joint power of these two sequences to be $$$$$$ \sum_{i=1}^x\sum_{j=1}^yw_{lca(a_i,b_j)} $$$$$$

Please calculate the value of this joint power.

Eva thinks this problem is too easy, so she decided to change the problem into an online problem:

First, given the tree and the weight of each vertex. Initially, both sequences are empty.

Then there will be $$$m$$$ operations, each one is of the following two types:

• 1 u : append $$$u~(1\le u\le n)$$$ to the end of the first sequence.
• 2 u : append $$$u~(1\le u\le n)$$$ to the end of the second sequence.

After each operation, you need to output the current joint power of the two sequences.

However, this version of the problem is too hard for Eva, so she added an additional limitation that, after each operation, the sum of values in the first sequence will not exceed $$$10^6$$$. Now Eva turns this problem to you; do you know how to solve it?

Colin is a huge fan of the Kingdom Rush franchise tower defense games. Last year, KR released the latest generation of Kingdom Rush: Kingdom Rush 5: Alliance. As a formidable evil arises in the new generation, an unexpected alliance is taking shape! It will take the finest warriors of Linirea and the relentless Dark Army together to stop it. Therefore, the most attractive feature of the latest generation of games is that you can use two heroes simultaneously!

To measure the power of the double-hero feature, Colin would like to do some simple experiments: Assume that a hero's attack range is a circle on the 2D plane with its coordinates as the center. The path of enemies is a segment on the 2D plane. Colin would like to ask you how long the total length of the enemy's path is that is covered by at least one hero's attack range?

One day, Colin got lost in a complete undirected graph $$$G$$$ with $$$n$$$ vertices, and each vertex $$$i$$$ is associated with a magic parameter $$$c_i$$$. For each pair of vertices $$$(i,j)$$$, there exists an undirected edge connecting them with weight $$$w_{i,j} = \gcd(c_i, c_j) + \text{lcm}(c_i, c_j)$$$.

Can you find the graph's minimum spanning tree $$$G$$$ to save Colin?

Recall that $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$, and $$$\text{lcm}(x, y)$$$ is the least common multiple of $$$x$$$ and $$$y$$$.