Everything that has a beginning has an ending. My journey has been reaching its ending, and I've been ready to say goodbye to my yesterday. But you, my dear friend, your journey is still thriving here at the 2022 CCPC Guilin Site. We sincerely hope you find a brand new milestone here, and forge ahead in the future with your love and passion.

Lily means a kind of beautiful flower. She usually only blooms once a year, so it could be very precious if you see a lily blooming. However, she is highly toxic to cats, so you must be aware of keeping curious cats away from lovely lilies.

You have $$$n$$$ grids of soil land in a row, for $$$1$$$ to $$$n$$$, some with lilies blooming. We don't want to hurt lilies, as well as cats. You can put some cat food on the grids, but for any grid $$$i$$$ with cat food, grids with indices falling in the range $$$[i - 1, i + 1]$$$ must not contain lily flowers. You love cats and lilies, so you want to maximize the number of grids having cat food.

Design a plan to fulfill the above requirements.

Preparing a reliable programming contest is tricky work. Sometimes, you can make the test set huge (e.g., wrong answer on test 400) instead of guessing how participants will solve the problems. However, huge test sets could be a critical burden to the poorly implemented contest platforms. If the judging process is not parallelled well, the flow time of submission is unacceptable, and you will receive countless complaints about it.

The problem you've made contains $$$n$$$ test cases, and there are $$$m$$$ test solutions written by different testers that you can believe are the most typical solutions. To avoid long judging processes, you want to prune the test set by deleting some test cases and reordering the remaining if needed. After that, it's required to keep the results of every test solution remain unchanged. Your goal is to keep the least number of tests at last.

Take the following snapshot from the contest preparing platform, Polygon, as an example.

Test solutions for Last Warning Of Competition Finance Officer, from the 2022 Shanghai Collegiate Programming Contest

The input data (See section Input) is given as the sheet above. For each solution, it will have a result with its verdict, running time and memory used on each test. The verdicts you should care about include the following, which are all common verdicts except compile error.

• OK: correct
• WA: wrong answer
• TL: time limit exceeded
• ML: memory limit exceeded
• RE: runtime error

After testing on a specific data set, the result including a representing verdict, a peak running time and a peak memory used will be returned to the participant. However, participants will not have information after the first failed test:

• When a solution passes all tests (correct on all test cases), the maximum time and memory will be shown with the correct verdict.
• Otherwise, the first failed test's verdict decides the verdict of the solution, and the maximum time and memory from the first test to the first failed test will be shown.

We can conclude from the above sheet that the verdicts of each solution are shown as follows.

To reduce the size of the test set, you can delete some tests, reorder the remaining ones, and make the results (verdicts, time, memory) of all tester solutions unchanged. Take the above sheet as an example:

• You can keep cases $$$9, 17, 10, 15, 13, 20, 12$$$ to satisfy the requirement, and it can be shown to be an optimal solution.
• You can reorder the cases if you like to – $$$9, 17, 10, 15, 13, 12, 20$$$ is also valid. However, swapping $$$9$$$ and $$$17$$$ is not valid since the solution 'aho_tle.cpp' will have a smaller memory cost.

You are given a test result sheet. Find an optimal way to reduce the test set so that the number of tests remaining is minimum.

Note that if a program is not tested on any test case, the status is undefined and not equal to any valid result, instead of 'correct 0ms/0MB' on some online judges.

Little relyt871 has a magical machine. In each operation, his machine can do one of the following operations to the input array $$$b$$$:

• Generate a copy of $$$b$$$ and concatenate it after $$$b$$$. More formally, the resulting array should be $$$$$$b' = \{b_1, b_2, \dots, b_{|b|}, b_1, b_2, \dots, b_{|b|}\}.$$$$$$
• Generate a copy of $$$b$$$, reverse it, then concatenate it before $$$b$$$. More formally, the resulting array should be $$$$$$b' = \{b_{|b|}, b_{|b-1|}, \dots, b_{1}, b_1, b_2, \dots, b_{|b|}\}.$$$$$$

Initially, he has an array $$$a$$$ of length $$$n$$$. Then, he wants to operate the machine exactly $$$m$$$ times using the array on his hand while maximizing the sum of all prefix sums of the final array. Since he has a somewhat finite brain, when he adds some integers, he only cares about the sum modulo $$$1\,000\,000\,007$$$. Formally, suppose after all $$$m$$$ operations he has array $$$b$$$ of length $$$n'$$$, he wants to maximize the following value: $$$$$$\Big(\sum_{i=1}^{n'}\sum_{j=1}^{i}b_j\Big) \pmod{1\,000\,000\,007}.$$$$$$

Please note that you should maximize the value after taking the modulo: the array with answer $$$1\,000\,000\,007$$$ before taking the modulo is considered less than the array with answer $$$1$$$.

Alice Margatroid is a skilled magician living in the Forest of Magic, who is good at making and controlling dolls. Today she is selling her self-made dolls to earn some money.

To attract people, Alice does not sell her dolls directly. Instead, she made a sweepstake (lottery) with different types of dolls. For each draw, the customer will get a special doll with a fixed probability $$$\frac a b$$$, a rational number within $$$(0, 1]$$$ (including $$$1$$$ but not $$$0$$$). Otherwise, the customer will get a doll of the usual kind.

By coincidence, Cirno goes to the Forest of Magic today. She finds the special dolls very attractive, but the usual dolls are not. Cirno decides to keep drawing until she gets $$$n$$$ special dolls, but she does not have much money, so she wants to estimate how many times she needs to draw.

Given a non-negative integer $$$m$$$, suppose the times Cirno needs to draw is $$$x$$$. For each non-negative integer $$$k$$$ between $$$0$$$ and $$$m$$$ (both inclusive), Cirno wants to know the expected value of $$$x^k$$$. The answers can be proven to be rational numbers, and you only need to output the answers modulo $$$998\,244\,353$$$, which is a prime number.

The value of a rational number $$$r$$$ modulo a prime $$$p$$$ is defined as follows: suppose $$$r = \frac x y$$$, where $$$x$$$ and $$$y$$$ are non-negative integers, and $$$0 \le x \lt p$$$, $$$1 \le y \lt p$$$. Also suppose there is a non-negative integer $$$z \in [0, p - 1]$$$ such that $$$yz \equiv 1 \pmod p$$$, then $$$r \equiv x z \pmod p$$$, in other words, the value of $$$r \bmod p$$$ is equal to $$$xz \bmod p$$$. It can be proven that there is a unique $$$z \in [0, p - 1]$$$ for each $$$y$$$, so the value is surely determined.

Little Desprado2 is a student of Springfield Flowers Kindergarten. On this day, he had just learned how to draw triangles on grid coordinate paper. However, he soon found it very dull, so he came up with a more interesting question:

He had drawn two integral points of the triangle on the grid paper, and he denotes them $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$. Now, he wanted to know the answer to the following question: where can he draw the third point $$$(x_3,y_3)$$$ so that the area of the triangle is positive but minimized?

Obviously, he can't solve this problem because he is too young and simple. Can you tell him the answer?

Please note that your answer's coordinates must consist of integers because he is drawing on grid paper, and the triangle shouldn't be a degenerated triangle to keep the area positive.

You are given $$$n$$$ non-degenerated circular sectors with the following guarantees:

• The central angle is less than or equal to 180 degrees.
• There are no two sectors with exactly the same radius and center.
• If two collinear radii belonging to two circular sectors exist, they won't share any point.

Please calculate the area of the union of those circular sectors.

No, we don't want group homework. It's the place where $$$1 + 1 \lt 1$$$ can be true. However, you are currently the leader of a group with three members. Luckily, your group members will write everything down for you since you are the prestigious leader. Unluckily, you have to assign the new algorithm homework to your two team members, Mr. Dian and Mr. Beng, who can't understand the ideas of each other correctly and mess up all the details in the cooperation.

The new homework is about a tree: there are $$$n$$$ vertices on the tree with $$$n - 1$$$ bidirectional edges connecting them. Each vertex $$$i$$$ is a problem with a score of $$$a_i$$$. You can assign a tree path to each member, then Mr. Dian and Mr. Beng will solve the problems on their path independently. The final score of the homework is decided by the sum of the scores of the vertices visited by exactly one member — as we mentioned before, if both of them solved one problem independently, they will argue a lot about who is right, and all the effort will be in vain.

Now, you — Mr. Ji — want to maximize the final score (as well as the chance not to drop out of school due to too low GPA). Make a wise choice!

Racing is for high speed usually. However, sloths enjoy hysteretic racing. They believe being slower could be better for exhibiting racers' skills, and all sloths will drive at the same speed. The winner is the one with the best driving skill throughout the journey.

There is the best fit for the figure: the sloth racer and DMV officer called Flash, in the movie Zootopia. However, we use this AI-generated sloth driver instead to avoid legal issues.

The giant race track consists of $$$n$$$ soil grids $$$0, 1, \dots, n - 1$$$ forming a circle, where the next grid of $$$i$$$ is $$$(i + 1) \bmod n$$$. The difficulty of the grid $$$i$$$ is a positive integer $$$d_i$$$, and the grid with lowest difficulty, $$$1$$$, is called a normal grid. The time cost to pass grid $$$i$$$ is defined as follows: if the velocity $$$v$$$ of sloths is higher than $$$\frac 1 {d_i}$$$ (normal grids per second) when entering grid $$$i$$$, the speed is adjusted to $$$\frac 1 {d_i}$$$ due to the laziness of sloths. After that, sloths will take $$$d_i$$$ times more than the normal grid to pass it, i.e., it will cost $$$\frac {d_i} {v}$$$ seconds.

Sometimes, the sloths pay for diligent humans to rebuild the giant race track. There are two kinds of the job that will occur:

• Plow the soil in grids $$$l, (l + 1) \bmod n, \dots, r$$$, add a specific difficulty $$$\Delta$$$ to each grid.
• Ram the soil in grids $$$l, (l + 1) \bmod n, \dots, r$$$, replace each grid's difficulty to a specific difficulty $$$d'$$$.

To begin a racing game, the judge will choose a start grid $$$s$$$ and the game's total time $$$t$$$ seconds, and the game is organized in the following method:

• The sloths will have a velocity of $$$1$$$ initially.
• At the beginning moment of the game, all sloths start entering the grid $$$s$$$.
• After going through a grid, sloths enter the next grid, where "next" is defined above.
• The game ends after $$$t$$$ seconds. All sloths take a sharp brake and stop there.

Since you are not a sloth, you have to do it fast.

Yukari is an elusive youkai (monster) who can manipulate boundaries. Recently Yukari is in a bad temper, and when she hears someone saying something she does not like (for example, "Yukari is thousands of years old"), she will be angry and beat the person from behind. Reimu has been bothered by her for a while because she does not know which words make Yukari unhappy. Even saying some common words like "cooooooooooooooooooooooool", "I want to eat noodles", or "invincible hotwheels" will be beaten by Yukari.

To avoid angering Yukari, Reimu finds out $$$n$$$ possible words Yukari may dislike, numbered from $$$1$$$ to $$$n$$$. Each word is a string containing only lowercase English letters. However, some redundant (unnecessary) words may contain other words. For example, if "iwanttoeatnoodles" and "noodles" are both possible words, then the former is redundant.

Reimu wants to estimate how many redundant relations are among the $$$n$$$ words. Formally, let $$$s_i$$$ denotes the $$$i$$$-th word. Reimu wants to know that, how many tuples of $$$(i,\ j,\ k)$$$ ($$$1\le i,\ j,\ k\le n$$$; $$$i, j, k$$$ are pairwise distinct) satisfying following contidions: $$$s_i$$$ is a substring of $$$s_j$$$, and $$$s_j$$$ is a substring of $$$s_k$$$. Also, there must not be another $$$j'$$$ which is not equal to $$$i, j$$$ or $$$k$$$, such that $$$s_i$$$ is also a substring of $$$s_{j'}$$$, and $$$s_{j'}$$$ is also a substring of $$$s_k$$$.

Reimu asked you for help her calculating the number of such tuples.

Little relyt871 is solving a puzzle. The key to the puzzle is a permutation containing numbers $$$1 \dots n$$$. The values at some positions of the permutation are already fixed, and relyt871 needs to fill numbers into the remaining positions.

Besides, little relyt871 has gathered $$$m$$$ extra requirements about the permutation. Let the solution be represented as $$$p_1,p_2,...,p_n$$$, each clue is a pair of indices $$$(u_i,v_i)$$$, which means that $$$p_{u_i} \lt p_{v_i}$$$ should be satisfied in the solution.

Little relyt871 wonders if all requirements may be satisfied at the same time. Write a program to find a valid solution when there is one.

Chinese children have more or less heard of the word "barrel theory" — the barrel's capacity is determined not by the longest wooden bars but by the shortest, as illustrated below.

Teachers and parents prefer to use this theory to tell the importance of all-round development, quality education, or collectivism. However, Little Desprado2 and Foolish Timsei disagree with this theory. In their opinion, a good barrel depends not only on large capacity but also on attractive looking.

According to barrel theory, if a barrel consists of $$$n$$$ wooden bars of with positive integral length $$$a_1,\ a_2,\ ...,\ a_n$$$ , the capacity of the barrel is $$$\min_{i=1}^n a_i$$$. They define the ugliness of the barrel is $$$a_1 \oplus a_2 \oplus ... \oplus a_n$$$. Here $$$\oplus$$$ denotes bitwise XOR (exclusive-or). They consider a barrel good if and only if its ugliness is less than its capacity.

Now Foolish Timsei and Little Desprado2 have a long wooden bar of length $$$m$$$, and they want to cut it into an $$$n$$$-pieces good barrel while the total length remains unchanged. Help them find a good scheme!

$$$n$$$ players are playing a game. They are to choose a number from $$$1, 2, \dots, m$$$ at the same time, and the game result should be analyzed as follows:

• If there exists a number that exactly $$$1$$$ player chooses, then the player with the largest such number wins and scores $$$1$$$ point; the other players score $$$-1$$$ point.
• Otherwise, the game is declared no winner; everyone is rewarded with a $$$0$$$ point.

The game plays only one round. To keep the game fair, the judge comes up with a new playing method for this game. Instead of giving a simple action, every player should submit their strategy to the judge, which should be a $$$m$$$-dimensional vector $$$s = (p_1, p_2, \dots, p_m)$$$, where $$$\sum_{i = 1} ^ m p_i = 1$$$ must hold. After that, the judge starts to roll the dice. For player $$$i$$$, the judge will sample a result uniformly at random according to $$$s_i$$$: with probability $$$s_{i, j}$$$, the number $$$j$$$ is chosen. After sampling $$$n$$$ numbers, the game concludes by the above rules.

The Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. To be more precise, we can define the term Nash Equilibrium on this game: given $$$n$$$ vectors of each player's strategy, if for each player, their strategy is the best response to the other players' strategies, we call it a Nash equilibrium. In other words, one can not earn a higher expected score in a Nash equilibrium by peeping at others' strategies and making some changes to their strategy.

Now, we'd like you to find a Nash equilibrium given $$$n$$$ and $$$m$$$. Note that you don't have to maximize or minimize anything related to scores, but you should guarantee that no one can take advantage by changing strategy on the spot.

Finales are born to be exciting. Performers play hard to draw audiences' attention and then take a perfect curtain call. As the last problem and the finale of the problem set, however, we want you to recall a simple algorithm. Like me, it may be the first algorithm you've learned, called Bubble Sort.

void bubble_sort(int a[], int n) { // 0-based, sort from lowest to highest
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        } // after i-th inner iteration, a[n - i] is correct
    }
}

Given a permutation of length $$$n$$$, as you might know, Bubble Sort runs in $$$\Omega (n ^ 2)$$$ in the worst case. It's quite a traditional idea to count the number of calls of "swap" in the algorithm. As you are stronger now, you want to count that number in a dynamic permutation with the following events that might happen:

• Reverse the permutation, meaning that the permutation is replaced with $$$$$$ p' = \{p_n, p_{n - 1}, \dots, p_2, p_1\}.$$$$$$
• Shift the permutation to the left by $$$1$$$, meaning that the permutation is replaced with $$$$$$ p' = \{p_2, p_3, \dots, p_n, p_1\}.$$$$$$

All you need to do is to output the number of "swap" that would be called if we sort the permutation with the above Bubble Sort code after each operation.