You are a trader at an investment company. One day, you discover that the stock you're responsible for trading follows an exactly repeating daily pattern: the day is divided into $$$n$$$ equal time intervals, and the stock's price during the $$$i$$$-th interval is always $$$a_i$$$. As the $$$n$$$-th interval of one day concludes, the first interval of the next day immediately follows, with the price shifting from $$$a_n$$$ to $$$a_1$$$. This is a once-in-a-lifetime opportunity — if you can just buy and sell according to this pattern you've already figured out, during your working hours, there's a guaranteed way to profit!

Your working hours vary, and a working period may extend past midnight. You are given $$$q$$$ working periods. The $$$i$$$-th period starts at slot $$$l_i$$$ and ends at slot $$$r_i$$$, including both endpoints. The slots in chronological order are:

• $$$l_i,l_i+1,\ldots,r_i$$$ if $$$l_i\le r_i$$$;
• $$$l_i,l_i+1,\ldots,n,1,2,\ldots,r_i$$$ if $$$l_i \gt r_i$$$.

In each working period, you may complete at most $$$k$$$ transactions. Each transaction consists of buying one share and selling it in a later time slot, with profit equal to the sale price minus the purchase price. You may hold at most one share at a time, so you must sell your current share before buying another. All purchases and sales must take place within that working period and follow the chronological order above. You may also make no transactions, earning a profit of $$$0$$$.

For each working period, independently find the maximum total profit you can earn.

You have a fair six-sided die with positive integer face values $$$a_1,a_2,\ldots,a_6$$$. Construct another fair six-sided die with positive integer face values $$$b_1,b_2,\ldots,b_6$$$ whose sum is exactly $$$k$$$. Face values may repeat on either die.

Roll each die once, independently. The new die wins if and only if its value is strictly greater than the original die's value; a tie is not a win. Determine whether you can make it win at least $$$19$$$ of the $$$36$$$ equally likely pairs of faces (that is, with probability strictly greater than $$$50\%$$$). If so, construct such a die.

EPS.AC is the problem-setting team for this contest. Its members are Colin, Claris, and Little_Sheep_Yawn.

They have prepared $$$n$$$ candidate problems for this contest. Each member ranks the $$$n$$$ problems from easiest to hardest according to their own judgment. To balance the contest's difficulty and distinguish contestants of different levels, they want to divide these problems into difficulty tiers, ordered from easiest to hardest. Every problem must belong to exactly one tier. Problems within the same tier are not ordered by difficulty, and each tier must contain at least one problem.

Arrange the tiers from left to right, from easiest to hardest. For a boundary between two consecutive tiers, the left side contains all problems in the tiers before it, and the right side contains all problems in the tiers after it. A member supports this boundary if every problem on its left appears before every problem on its right in that member's ranking.

A division into tiers is valid if every boundary has the support of at least two members. Different boundaries may have different supporters.

More difficulty tiers mean better problem setting. To help them create a good contest, find the maximum possible number of tiers.

You need to guide a night butterfly through the darkness. Its starting point is the common center of six radial tracks, numbered clockwise from $$$0$$$ to $$$5$$$. Track $$$0$$$ is the main track; the other five are auxiliary tracks.

Only certain intervals on the tracks are lit. The main track has one set of lit intervals, while all five auxiliary tracks share another set. All lit intervals are closed, and their endpoints represent distances from the center.

Before each flight, you may choose a positive real speed $$$d$$$, which remains fixed throughout the flight. The butterfly starts at the center at time $$$0$$$. At every positive integer time $$$t$$$, it is on track $$$(t\bmod 6)$$$ at a distance $$$t\cdot d$$$ from the center. Thus, it visits tracks $$$1,2,3,4,5,0,1,2,\ldots$$$ in this order.

You are given $$$q$$$ queries, each specifying a target distance $$$T$$$. You want the butterfly to reach the main track at some time $$$k$$$, at a distance $$$T$$$ from the center. Thus, $$$k$$$ must be a positive multiple of $$$6$$$, and $$$k\cdot d=T$$$. At every integer time $$$1,2,\ldots,k$$$, the butterfly must be within a lit interval on its current track, or it will fall into darkness and lose its way. There are no restrictions at other times, including time $$$0$$$.

For each query, find the earliest time $$$k$$$ at which the butterfly can safely reach its target, or print -1 if it cannot. The queries are independent, and you may choose $$$d$$$ separately for each query.

For a permutation of $$$1,2,\ldots,n$$$, let $$$s_i$$$ be the length of the shortest contiguous subarray containing all values $$$1,2,\ldots,i$$$.

Let $$$\operatorname{pos}_p(x)$$$ be the position of $$$x$$$ in the permutation; we have

$$$$$$ s_i=\max_{1\le x\le i}\operatorname{pos}_p(x)-\min_{1\le x\le i}\operatorname{pos}_p(x)+1. $$$$$$

For each $$$i$$$, an interval constraint $$$[l_i,r_i]$$$ is given.

Please count the permutations satisfying $$$l_i\le s_i\le r_i$$$ for every $$$i$$$. Print the answer modulo $$$998244353$$$.

This is a communication problem. Your program will be run twice for each test, in two independent processes.

First Run

You are given a permutation $$$p=(p_1,p_2,\ldots,p_n)$$$ of $$$1,2,\ldots,n$$$.

Output an $$$n\times n$$$ matrix $$$A$$$ such that each row is a permutation of $$$1,2,\ldots,n$$$ and all rows are pairwise distinct.

Second Run

Before the second run, the judge randomly shuffles the rows of $$$A$$$ to obtain a matrix $$$B$$$. The order of the elements within each row remains unchanged. You are given $$$B$$$ and must recover the original permutation $$$p$$$ from the first run.

Your program must recover $$$p$$$ for every possible ordering of the rows. No process state is preserved between the two runs; the shuffled matrix is the only information passed from the first run to the second. The time and memory limits apply to each run separately.

Given an integer $$$n$$$, find three integers $$$a, b, c$$$ satisfying

• $$$|a|,|b|,|c|\le 10^{18};$$$
• $$$n=ab(a+b)+bc(b+c)+ac(a+c).$$$

If no such triple of integers exists, report that there is no solution.

You need to schedule $$$n$$$ jobs on a pipeline. The jobs form a sequence, and job $$$i$$$ has workload $$$a_i$$$. The pipeline consists of $$$m$$$ stages in series.

Before processing begins, you may choose an integer $$$t$$$ ($$$0\le t\le n$$$). This moves the first $$$t$$$ jobs to the end without changing their relative order, obtaining $$$a_{t+1},a_{t+2},\ldots,a_n,a_1,a_2,\ldots,a_t.$$$ Choosing $$$t=0$$$ or $$$t=n$$$ leaves the sequence unchanged.

Next, you need to partition the resulting sequence into at most $$$k$$$ nonempty contiguous segments, each forming a batch. The workload of a batch is the sum of the workloads of its jobs.

The batches then enter the pipeline in order. Each batch passes through stages $$$1,2,\ldots,m$$$ in this order, taking time equal to its workload at each stage. Each stage processes at most one batch at a time, following the batches' left-to-right order in the sequence. After finishing at one stage, a batch may wait for the next stage to become available. While it waits, it no longer occupies the previous stage, which may process the next batch. Different stages may process different batches simultaneously.

The pipeline starts processing at time $$$0$$$. Choose the prefix to move and the partition into batches so that all jobs finish as early as possible.

You enjoy exploring the world by car. Today, you have arrived in a new country consisting of $$$n$$$ cities, numbered $$$1$$$ to $$$n$$$.

You wish to drive to the capital city, $$$t$$$. Unfortunately, the country's communication network is outdated, so your navigation system does not always have a signal. However, the road network forms a weighted directed acyclic graph where the weight of each edge represents the time required to traverse it, and every city has a path to the capital city $$$t$$$ via the road network.

Upon arriving at any city other than $$$t$$$, you choose the next road according to the following rules:

• If there is a signal, the navigation system randomly selects one of the shortest paths from the current city to $$$t$$$ with equal probability, and directs you to take the first edge of that path;
• If there is no signal, you randomly select one of the city's outgoing edges with equal probability.

Consequently, in cities with a signal, the probability of selecting a specific outgoing edge is proportional to the number of shortest paths that begin with that edge; the probabilities of selecting different outgoing edges are not necessarily equal. A new choice is made after traversing each edge to reach the next city. All random choices are independent, and the journey ends immediately upon reaching the capital city $$$t$$$.

You want to determine, for each starting city $$$s$$$, the expected total time required to reach the capital city $$$t$$$, modulo $$$998244353$$$.

A system contains $$$n$$$ types of programs, indexed from $$$1$$$ to $$$n$$$. Once an instance of program type $$$k$$$ starts, it generates a log entry every $$$k$$$ seconds—specifically, at times $$$k,2k,3k,\ldots$$$ relative to its start time.

At time $$$0$$$, the system executes $$$m$$$ commands simultaneously: the $$$i$$$-th command launches one instance for each program type with an index in the range $$$[l_i, r_i]$$$. Note that if the ranges of multiple commands overlap, multiple instances of the same program type may be launched, and each instance generates logs independently.

The system records all log entries generated at times $$$1,2,\ldots,n$$$. Each record contains only the index of the program type corresponding to the instance that generated the log.

Your task is to design an algorithm to compress these logs: you must assign a non-empty binary string as an identifier to all the $$$n$$$ program types, ensuring that no identifier is a prefix of another. The cost of encoding a single record is the length of the identifier assigned to the corresponding program type, and the total cost is the sum of the costs of all records. Find the minimum possible total cost.

You are given an integer sequence $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$x$$$.

Define a subsequence of the sequence as follows: for any non-empty set of indices $$$\{i_1,i_2,\cdots,i_m\}\ (i_1 \lt i_2 \lt \cdots \lt i_m)$$$ chosen from $$$1,\ldots,n$$$, taking $$$a_{i_1},\ldots,a_{i_m}$$$ in their original order is a subsequence. Define its median as follows: sort the $$$m$$$ chosen values into $$$v_1\le v_2\le\cdots\le v_m$$$, then:

• if $$$m$$$ is odd, the median is the middle value $$$v_{(m+1)/2}$$$;
• if $$$m$$$ is even, the median is the average of the two middle values, $$$\dfrac{v_{m/2}+v_{m/2+1}}{2}$$$ (this average need not be an integer, but the problem only cares whether it is exactly equal to $$$x$$$).

Find the number of subsequences whose median is exactly $$$x$$$. Since this number can be very large, output it modulo $$$998244353$$$.

Note: even if two different index sets happen to pick out the exact same multiset of values (possible since the sequence may contain repeated numbers), they are still counted as two distinct subsequences. It is the index set itself, not the multiset of chosen values, that distinguishes subsequences. The empty index set is not a subsequence and is never counted.

To enhance the suspense and spectator appeal of the contest, the CCPC has introduced a new format featuring a "dynamic scoreboard/balloon-awarding" system. Under this format, the specific problem numbers solved by each team are not displayed immediately during the contest; instead, the scoreboard is revealed dynamically.

Introduction to the new CCPC rules

According to the rules, the scoreboard status for a specific problem "unfreezes" when any one of the following three conditions is met:

1. The number of teams that have solved the problem is greater than or equal to $$$\mathbf{50}$$$.
2. The number of teams that have solved the problem is greater than or equal to $$$\mathbf{20\%}$$$ of the total number of participating teams (not necessarily an integer).
3. The contest enters the "scoreboard freeze" period. Specifically, the time is represented by a string in the format "HH:MM" indicating the elapsed contest time; the freeze period begins at the $$$\mathbf{240}$$$-minute mark (inclusive).

Although the new format has not yet been officially finalized and is not used in the online contest, please implement this new rule for this problem to better prepare for the upcoming on-site contests.

Given a contest with $$$n$$$ participating teams, a problem solved by $$$m$$$ teams, and the current time, please determine whether the problem currently meets the criteria for unfreezing.