Welcome to the CCPC Qinhuangdao Site!

Qinhuangdao is a beautiful coastal city full of charm, integrating historical heritage and modern civilization. It was named after the Emperor QinShiHuang's east tour in 215 BC for seeking immortals.

The infiltration of more than 2000 years of history has left a rich cultural treasure here. Bo Yi, Shu Qi, Qi Jiguang, Cao Cao, and Mao Zedong, Many Heroes throughout the ages have endowed Qinhuangdao with the thousand-year cultural context, the unique and precious heritage, and the profound historical memory.

Pleasant natural scenery has shaped her beautiful appearance. Thousands of miles of Yan Mountains, the Great Wall, and the vast seas are miraculously met here. The blue sky, green land, blue sea, and golden sand gather together to welcome guests.

To toast your arrival, Alex prepared a simple problem to help you warm up.

Alex has $$$r$$$ red balls and $$$b$$$ blue balls. Then, Alex randomly chose two of these balls with equal probability. What is the probability that he chose two red balls?

Output the required probability in the form of irreducible fraction.

Alex is a professional computer game player.

These days, Alex is playing a war strategy game. His land is a rectangular grid with $$$n$$$ rows by $$$m$$$ columns of cells. He wants to build a bounding wall to protect some vital materials.

The bounding wall is a frame of $$$a \times b$$$ rectangle whose width is $$$1$$$. It occupies $$$a$$$ rows and $$$b$$$ columns, and its coverage area is $$$a\cdot b$$$. Note that $$$a=1$$$ or $$$b=1$$$ is also allowed. Each cell has a state, wet or dry. It is impossible to build a bounding wall across a wet cell.

He will also have several queries about building a bounding wall. The only two possible formats about queries are listed as follows.

• 1 x y : the state of cell $$$(x,y)$$$ changes.
• 2 x y : Alex wants to build a bounding wall across the cell $$$(x,y)$$$ such that the coverage area is as large as possible. Answer the maximum coverage area.

Alex is a professional computer game player.

These days, Alex is playing a war strategy game. His city can be regarded as a rectangle on the Cartesian plane. Its lower-left corner is $$$(0,0)$$$, and its upper-right corner is $$$(n+1,n+1)$$$.

Alex builds $$$n$$$ defensive towers to protect the city. The defensive tower $$$i$$$ is located at $$$(x_i,y_i)$$$, and its direction is $$$d_i$$$. The defensive towers with different directions protect different areas:

• if $$$d_i = 1$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \ge x_i, b \ge y_i\}$$$;
• if $$$d_i = 2$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \le x_i, b \ge y_i\}$$$;
• if $$$d_i = 3$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \le x_i, b \le y_i\}$$$;
• if $$$d_i = 4$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \ge x_i, b \le y_i\}$$$.

If Alex launches $$$e$$$ defensive towers, he will consume $$$e$$$ energy per hour. He wants to launch as few defensive towers as possible so that all points $$$(x,y)\ (x,y\in \mathbb{R},0 \le x,y \le n+1)$$$ in his city can be protected. Can you find the optimal strategy?

Professor Alex is preparing an exam for his students now.

There will be $$$n$$$ students participating in this exam. If student $$$i$$$ has a good mindset, he/she will perform well and get $$$a_i$$$ points. Otherwise, he/she will get $$$b_i$$$ points. So it is impossible to predict the exam results. Assume the highest score of these students is $$$x$$$ points. The students with a score of no less than $$$x \cdot p\%$$$ will pass the exam.

Alex needs to know what is the maximum number of students who can pass the exam in all situations. Can you answer his question?

Professor Alex will organize students to attend an academic conference.

Alex has $$$n$$$ excellent students, and he decides to select some of them (possibly none) to attend the conference. They form a group. Some pairs of them are friends.

The friendly value of the group is initially $$$0$$$. For each couple of friends $$$(x,y)$$$, if both of them attend the conference, the friendly value of the group will increase $$$1$$$, and if only one of them attends the conference, the friendly value of the group will decrease $$$1$$$. If $$$k$$$ students attend the conference, the friendly value of the group will decrease $$$k$$$.

Alex wants to make the group more friendly. Please output the maximum friendly value of the group.

Alex loves numbers.

Alex thinks that a positive integer $$$x$$$ is good if and only if $$$\lfloor \sqrt[k]{x} \rfloor$$$ divides $$$x$$$.

Can you tell him the number of good positive integers which do not exceed $$$n$$$ ?

Alex is proud of the holy sequence.

Alex thinks that a sequence $$$a_1,a_2,\cdots, a_n$$$ is $$$n$$$-holy if and only if

• For each $$$i \in [1,n]$$$, $$$a_i \in \{1,2,\cdots, n\}$$$ ;
• For each $$$i \in [1,n]$$$, $$$p_i - p_{i-1} \le 1$$$ ($$$p_k = \max\{a_1,a_2,\cdots, a_k\}$$$, $$$p_0=0$$$).

For each $$$t = 1,2, \cdots, n$$$, Alex wants to know $$$$$$ \sum_{p \in S_n} \mathrm{cnt}(p,t)^2, $$$$$$ where $$$S_n$$$ is the set of all $$$n$$$-holy sequences and $$$\mathrm{cnt}(p,t)$$$ is the occurrence number of $$$t$$$ in sequence $$$p$$$.

As the results can be very large, output it modulo $$$m$$$.

Alex is a professional computer game player.

These days, Alex is playing an interstellar game. This game is played in an infinite 2D universe, and Alex's spaceship starts at $$$(0,0)$$$ in the beginning. Because the distances between different galaxies are too long (conventional thrusters cannot reach the destination in an acceptable amount of time), movement can only be done by "jump". If his spaceship has jump skill $$$(a,b)$$$ and he is located at $$$(x,y)$$$, he can reach $$$(x+a,y+b)$$$ or $$$(x-a,y-b)$$$ immediately. He can use jump skills continuously at any time, and the jump skills will not disappear.

In the game, the following $$$Q$$$ events, which have two types, will happen in order.

• $$$1\ x_i\ y_i$$$: Alex will acquire jump skill $$$(x_i,y_i)$$$.
• $$$2\ x_i\ y_i\ w_i$$$: There will be a reward mission in $$$(x_i,y_i)$$$. Alex can decide to go there immediately for $$$w_i$$$ rewards or just ignore it.

Alex wonders how many rewards he can get if he plays optimally.

Alex is a private jewel collector.

Recently, he purchased a piece of jewelry, a bunch of $$$n$$$ gemstones. The gemstones have $$$26$$$ different types, labeled from a to z. He wants to split the jewelry and combine them into a jewel matrix.

Alex will choose $$$d \in \{1,2,\cdots, n\}$$$, the width of the jewel matrix. Then, he will split the jewelry and get $$$\left\lfloor \frac{n}{d} \right\rfloor$$$ bunches of gemstones with length $$$d$$$ and a bunch of length $$$n \bmod d$$$ if $$$d$$$ doesn't divide $$$n$$$. All $$$\left\lfloor \frac{n}{d} \right\rfloor$$$ bunches with length $$$d$$$ will be permuted as rows of the jewel matrix.

Alex wonders how many different jewel matrix he can get. Two jewel matrix are considered different if and only if they have different width, or it is at least one row different.

As the results can be very large, output it modulo $$$998244353$$$.

Alex is a professional computer game player.

These days, Alex is playing a war strategy game. The kingdoms in the world form a rooted tree. Alex's kingdom $$$1$$$ is the root of the tree. With his great diplomacy and leadership, his kingdom becomes the greatest empire in the world. Now, it's time to conquer the world!

Alex has almost infinite armies, and all of them are located at $$$1$$$ initially. Every week, he can command one of his armies to move one step to an adjacent kingdom. If an army reaches a kingdom, that kingdom will be captured by Alex instantly.

Alex would like to capture all the kingdoms as soon as possible. Can you help him?

Professor Alex is an expert in the study of ancient buildings.

When he was surveying an ancient temple, he found ruins containing several fallen stone pillars. There are $$$n$$$ stone pillars in the ruins, numbered $$$1,2,\cdots,n$$$. For each $$$i \in \{1,2,\cdots,n-1\}$$$, the $$$(i+1)^{\rm th}$$$ stone pillar is next to the $$$i^{\rm th}$$$ stone pillar from west to east. As time went on, some stone pillars were badly destroyed.

Each stone pillar can be regarded as a series of continuous cubic stones, and we label the cubic stones $$$1,2,3,\cdots,10^9$$$ from south to north. Every two east-west adjacent cubic stones have the same label. The $$$i^{\rm th}$$$ stone pillar remains cubic stones $$$l_i,l_i+1,\cdots,r_i$$$.

Here is an example: $$$n = 4, \{l_i\} = \{4,2,3,3\}, \{r_i\} = \{5,5,6,4\}$$$,

Whenever a year goes by, the outer cubic stone will be destroyed by acid rain. In the above example, those blue squares will disappear one year later. Alex wants to know when the all of cubic stones of the $$$i^{\rm th}$$$ stone pillar will disappear for each $$$i = 1,2,\cdots, n$$$. Assume that the $$$i^{\rm th}$$$ stone pillar will disappear $$$f_i$$$ years later. You need to output the answer: $$$$$$ \mathrm{answer} = \sum_{i=1}^{n} f_i \cdot 3^{i-1} \bmod 998244353 $$$$$$ Since the number of stone pillars can be very large, we generate the test data in a special way. We will provide five parameters $$$L,X,Y,A,B$$$, and please refer to the code (written in C++) below:

typedef unsigned long long u64;

u64 xorshift128p(u64 &A, u64 &B) {
	u64 T = A, S = B;
	A = S;
	T ^= T << 23;
	T ^= T >> 17;
	T ^= S ^ (S >> 26);
	B = T;
	return T + S;
}
	
void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) {
	for (int i = 1; i <= n; i ++) {
		l[i] = xorshift128p(A, B) % L + X;
		r[i] = xorshift128p(A, B) % L + Y;
		if (l[i] > r[i]) swap(l[i], r[i]);
	}
}