!%?#$@ and Z-tube cat are watching seagulls.
In a grid with multiple rows and columns, there are initially $$$n$$$ seagulls and $$$n$$$ pieces of food, each located in a distinct cell.
You may direct the seagulls to find food. In each command, you must select one seagull in the grid and choose a direction: up (row index decreases, column index unchanged), down (row index increases, column index unchanged), left (row index unchanged, column index decreases), or right (row index unchanged, column index increases). The selected seagull will then fly in that direction to the nearest empty cell. When a seagull lands on a food-containing grid, it consumes the food and leaves the grid, meaning both the seagull and the food immediately disappear from the grid.
Please execute exactly $$$n$$$ commands to make all seagulls consume food and leave the grid, or report no solution.
Each test contains multiple test cases. The first line gives an integer $$$T(1\leq T\leq 10^3)$$$, indicating the number of test cases.
For each test case: The first line contains an integer $$$n(1\leq n\leq5000)$$$, representing $$$n$$$ seagulls, $$$n$$$ pieces of food, and $$$n$$$ commands to execute.
The next $$$n$$$ lines each contain two integers $$$r_i, c_i (1 \leq r_i, c_i \leq 5000)$$$. The two integers $$$r_i, c_i$$$ on the $$$i$$$th line indicate that the seagull with number $$$i$$$ initially occupies the cell at row $$$r_i$$$ and column $$$c_i$$$.
The next $$$n$$$ lines each contain two integers $$$r_i, c_i(1 \leq r_i, c_i \leq 5000)$$$, indicating that a piece of food initially occupies the cell at row $$$r_i$$$ and column $$$c_i$$$.
It is guaranteed that the initial positions of all seagulls and food items are distinct.
The total sum of $$$n$$$ across all test cases in each test is guaranteed not to exceed $$$5000$$$.
For each test case:
Output Yes or No on the first line, indicating whether the problem has a solution or not.
If a solution exists, output the following $$$n$$$ lines, each containing an integer $$$u_i$$$ and a character $$$c_i$$$ ($$$c_i \in \{U, D, L, R\}$$$) separated by a space. The integer $$$u_i$$$ in the $$$i$$$th line indicates you selected seagull $$$u_i$$$ in the $$$i$$$th command step, and the character $$$c_i$$$ is $$$\text{U}$$$, $$$\text{D}$$$, $$$\text{L}$$$, or $$$\text{R}$$$ representing the flight direction up, down, left, or right, respectively. If multiple command sequences are valid, output any one of them.
Note: Do not output any extra spaces.
5 4 2 1 4 1 1 4 3 3 1 1 5 1 1 3 3 4 4 1 3 2 2 2 3 3 3 1 2 2 1 3 2 4 3 1 1 1 1 3 4 2 3 3 2 3 3 2 2 2 4 3 1 4 3 1 2 2 2 2 1 1 1 3 1 2
Yes 1 U 2 D 3 L 4 R Yes 1 D 3 L 4 L 2 U No Yes 4 U 3 D 1 R 2 L No
You have a keyboard with the numeric keys $$$0,1,2,\cdots,9$$$.
For any positive integer $$$m$$$, you can obviously always type a positive integer that is a multiple of $$$m$$$.
Now, $$$k$$$ of your positive integer keys have been knocked off, but you still want to type a positive integer that is a multiple of $$$m$$$.
Each test contains multiple test cases. The first line contains an integer $$$T(1 \leq T \leq 5 \times 10^4)$$$, representing the number of test cases.
For each test case:
The first line contains two positive integers $$$m, k(1 \leq m \leq 10^7, 0 \leq k \leq 9)$$$, indicating that after $$$k$$$ keys are removed, you need to press a sequence of keys to produce a positive integer that is a multiple of $$$m$$$.
The second line gives $$$k$$$ distinct positive integers $$$p_i(1\leq p_i \leq 9)$$$, representing the removed keys.
For each test case:
If a solution exists, output your operations as a sequence of multiple "press digit $$$a$$$ for $$$b$$$ times" operations: The first line outputs an integer $$$n$$$, where $$$1 \leq n \leq 100$$$, representing the number of operations required.
The next $$$n$$$ lines each output two integers $$$a,b$$$ ($$$0 \leq a \leq 9, 1 \leq b \leq 10^{18}$$$), representing one operation "press digit $$$a$$$ for $$$b$$$ times".
If no solution exists, output a single line containing $$$-1$$$.
2 37 7 2 3 5 6 7 8 9 7 9 1 2 3 4 5 6 7 8 9
2 1 3 0 1 -1
For the first test case in the example, the positive integer output is $$$1110$$$. Since $$$1110 = 37 \times 30$$$, it is a multiple of $$$37$$$.
The following image shows the logo for the DUT XCPC designed by Z-tube Cat.
The amount of paint required to color this logo (in grams) is $$$a$$$. The currently available amount of paint is $$$b$$$. Please determine whether the current amount of paint is sufficient for coloring this logo.
Each line contains two quantities separated by a space, representing the amount of paint required to complete the painting and the current amount available, respectively. Each paint quantity consists of a three-digit number immediately followed by g. The three-digit number is an integer within the range $$$[100,999]$$$.
An integer $$$0$$$ or $$$1$$$. $$$0$$$ indicates insufficiency, $$$1$$$ indicates sufficiency.
123g 333g
1
123g 123g
1
333g 123g
0
Z-tube Cat recommends you play Ballance. In the game, players take control of a ball with variable material properties, guiding it through a vast and intricate maze of road surfaces and mechanisms. Along the way, you must avoid traps, activate mechanisms, and solve puzzles to ultimately reach the finish line.
Ballance has $$$3$$$ material types (paper ball, wooden ball, stone ball). During gameplay, the ball must pass through $$$n$$$ mechanisms, each of which can only be passed by balls of specific material types. Initially, you must spend $$$1$$$ unit to select one material type for the ball. Before passing each mechanism, you may spend $$$1$$$ unit to switch the ball to another material type or choose to keep the current material at no cost.
You may freely arrange the order of passage through the mechanisms. Determine the minimum cost required for the ball to pass through all $$$n$$$ mechanisms.
The first line contains an integer $$$n (1 \le n \le 100)$$$, the number of mechanisms.
Each of the next $$$n$$$ lines contains three integers $$$a_{i,1}, a_{i,2}, a_{i,3} \in \{0, 1\}$$$.
For the $$$i$$$-th mechanism, $$$a_{i,j} = 1$$$ indicates that the $$$j$$$-th ball type is allowed to pass, while $$$a_{i,j} = 0$$$ indicates it is prohibited.
It is guaranteed that for each mechanism, not all $$$a_{i,j}$$$ are zero.
One line containing an integer, representing the minimum cost required for the ball to pass through these $$$n$$$ mechanisms, achieved by rationally arranging the sequence of passage and the material costs.
5 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1
3
Given an array of positive integers of length $$$n$$$, determine how many non-empty subarrays $$$^{\text{*}}$$$ satisfy the following condition: the sum of the elements in the subarray is divisible by the largest digit $$$^{\text{†}}$$$ appearing in the subarray.
$$$^{\text{*}}$$$ An array $$$a$$$ is a non-empty subarray of array $$$b$$$ if and only if $$$a$$$ can be obtained by deleting zero or more elements from the beginning of $$$b$$$ and zero or more elements from the end of $$$b$$$, and $$$a$$$ contains at least one element.
$$$^{\text{†}}$$$ A digit refers to any of the numbers $$$0,1,2,3,4,5,6,7,8,9$$$ that compose a number. For example, the array $$$[213]$$$ contains the digits $$$1,2,3$$$, so the largest digit is $$$3$$$; the array $$$[2025,11,15]$$$ contains the digits $$$0,1,2,5$$$, so the largest digit is $$$5$$$.
Each test contains multiple test cases. The first line contains an integer $$$T(1 \le T \le 10^4)$$$, indicating the number of test cases.
For each test case:
The first line gives an integer $$$n(1\le n\le 10^5)$$$, representing the array length.
The second line contains $$$n$$$ positive integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$), representing the array.
It is guaranteed that the sum of all $$$n$$$ values across all test cases does not exceed $$$10^5$$$.
For each test case, output one line containing an integer representing the number of non-empty subarrays that satisfy the condition.
2 3 213 12 21 7 314 880 246 170 493 474 129
4 7
Z-tube Cat invites our old friends Alice and Bob to play their favorite stone-taking game again! This time, the rules for taking stones and generating initial configurations are based on prefixes and suffixes.
In a single game, the configuration consists of a row of $$$m$$$ piles of stones, numbered from $$$1$$$ to $$$m$$$ from front to back. Alice and Bob take turns removing stones, with Alice moving first.
In one turn, the player first chooses two non-negative integers $$$get_{\text{pre}}$$$ and $$$get_{\text{suf}}$$$. Then, they remove one stone from each of the first $$$get_{\text{pre}}$$$ non-empty piles (from the front) and one stone from each of the last $$$get_{\text{suf}}$$$ non-empty piles (from the back). However, at most one stone may be removed from a single pile during the same turn.
The player who, on their turn, removes zero stones loses the game; the other player wins.
Alice and Bob will play $$$n$$$ games. Let $$$a_{i,j}$$$ denote the number of stones in the $$$j$$$-th pile at the beginning of the $$$i$$$-th game. Given two non-negative integers $$$put_{\text{pre}}, put_{\text{suf}}$$$ (with $$$put_{\text{pre}} + put_{\text{suf}} \le m$$$) and the initial configuration of the first game $$$a_{1,1}, \dots, a_{1,m}$$$.
For $$$i \in [2, n]$$$, the initial configuration of the $$$i$$$-th game is generated from that of the $$$(i-1)$$$-th game as follows: take the suffix sums of the first $$$put_{\text{pre}}$$$ piles, take the prefix sums of the last $$$put_{\text{suf}}$$$ piles, and leave the remaining piles unchanged.
More formally,
$$$$$$a_{i,j}=\begin{cases} \sum\limits_{k=j}^{put_{pre}}a_{i-1,k} & j\in[1,put_{pre}] \\ a_{i-1,j} & j\in[put_{pre}+1,m-put_{suf}] \\ \sum\limits_{k=m-put_{suf}+1}^{j}a_{i-1,k} & j\in[m-put_{suf}+1,m] \end{cases}$$$$$$
Both Alice and Bob play optimally. For each of the $$$n$$$ games, determine the winner.
Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.
For each test case:
The first line contains four integers $$$n, m, put_{\text{pre}}, put_{\text{suf}}$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 10^6$$$, $$$put_{\text{pre}} \ge 0$$$, $$$put_{\text{suf}} \ge 0$$$, $$$put_{\text{pre}} + put_{\text{suf}} \le m$$$), representing the total number of games, the total number of piles in the initial configuration, and the two non-negative integers used to generate the initial configurations, respectively.
The second line contains $$$m$$$ integers $$$a_{1,1}, a_{1,2}, \dots, a_{1,m}$$$ ($$$1 \le a_{1,j} \le 10^9$$$), where $$$a_{1,j}$$$ denotes the number of stones in the $$$j$$$-th pile at the beginning of the first game.
It is guaranteed that, within each test, the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output $$$n$$$ lines, each containing a string.
For the $$$i$$$th line, outputs Alice if Alice wins the $$$i$$$th game; otherwise (if Bob wins the $$$i$$$th game), outputs Bob.
2 3 7 3 2 1 3 1 2 1 2 2 2 6 0 6 7 3 8 3 5 10
Alice Alice Bob Alice Alice
For the first test case in the sample:
The initial configuration of the first game is $$$1, 3, 1, 2, 1, 2, 2$$$.
Below is a possible gameplay process between Alice and Bob:
- Alice chooses $$$get_{\text{pre}} = 4$$$, $$$get_{\text{suf}} = 0$$$, removing $$$4$$$ stones. The configuration becomes $$$0, 2, 0, 1, 1, 2, 2$$$ (i.e., considering only non-empty piles: $$$2, 1, 1, 2, 2$$$).
- Bob chooses $$$get_{\text{pre}} = 1$$$, $$$get_{\text{suf}} = 2$$$, removing $$$3$$$ stones. The configuration becomes $$$1, 1, 1, 1, 1$$$.
- Alice chooses $$$get_{\text{pre}} = 2$$$, $$$get_{\text{suf}} = 3$$$, removing $$$5$$$ stones. Now all piles become empty.
- Bob chooses $$$get_{\text{pre}} = 0$$$, $$$get_{\text{suf}} = 0$$$, removing $$$0$$$ stones. Bob loses this game, and Alice wins.
The initial configuration of the second game is $$$5, 4, 1, 2, 1, 2, 4$$$. The initial configuration of the third game is $$$10, 5, 1, 2, 1, 2, 6$$$.
For the second test case in the sample, the initial configuration of the second game is $$$7, 10, 18, 21, 26, 36$$$.
The input and output for this problem are large. Please use efficient I/O methods.
Finally, Alice and Bob are tired of playing. Let's hope they never play another stone-taking game again…
Z-tube Cat said: "No more counting dollars, we'll be counting stars……"
Given $$$n$$$ nodes, where node $$$i$$$ has a weight $$$a_i$$$.
A generalized star graph is defined as a labeled unrooted tree satisfying: the number of nodes with degree $$$1$$$ is greater than or equal to the weight of the node with the maximum degree. If there are multiple nodes with the maximum degree, take the largest weight among them.
Please count the number of generalized star graphs $$$^{\text{*}}$$$ that can be formed by these $$$n$$$ nodes, modulo $$$998244353$$$.
Excessive modulo operations may cause severe performance overhead. Please reduce unnecessary modulo operations!
$$$^{\text{*}}$$$ Two labeled unrooted trees are considered different if and only if there exists at least one pair of labels $$$(u, v)$$$ such that they are connected by an edge in one tree but not in the other.
Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 50$$$), the number of test cases.
For each test case:
The first line contains an integer $$$n$$$ ($$$3 \le n \le 250$$$), the total number of nodes.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ denotes the weight of node $$$i$$$.
It is guaranteed that, within each test, the sum of $$$n$$$ over all test cases does not exceed $$$250$$$.
For each test case, output a single integer on a line — the number of generalized star graphs that can be formed by these $$$n$$$ nodes, modulo $$$998244353$$$.
3 6 5 5 5 5 5 5 4 2 3 2 4 10 5 4 10 3 10 1 5 8 8 1
6 5 31108248
For the first test case in the sample, all generalized star graphs formed by these $$$6$$$ nodes are shown below:
For the second test case in the sample, all generalized star graphs formed by these $$$4$$$ nodes are shown below:
Country A is renowned for its picturesque landscapes. It consists of $$$n$$$ cities, each with its unique charm, forming a vast and splendid nation. However, due to the financial crisis, the national budget is tight. As a result, there are only $$$n-1$$$ bidirectional roads connecting the $$$n$$$ cities. These $$$n-1$$$ roads ensure that it is possible to travel from any city to any other.
The administrative structure of Country A is well-organized: City $$$1$$$ is the capital. Every other city has a superior city. Specifically, for city $$$i$$$ ($$$i \ge 2$$$), there is a road connecting it to its superior city $$$fa_i$$$ ($$$1 \le fa_i \lt i$$$), and the length of this road is $$$w_i$$$.
A city $$$y$$$ is called an indirect subordinate of city $$$x$$$ if and only if the superior city $$$fa_y$$$ of $$$y$$$ is $$$x$$$, or $$$fa_y$$$ is an indirect subordinate of $$$x$$$.
Let $$$\mathrm{dist}(x, y)$$$ denote the length of the shortest path between city $$$x$$$ and city $$$y$$$.
Due to the rugged terrain and frequent natural disasters in Country A, the central command needs precise coordination and must balance the total workload of the fire rescue forces across cities.
The workload of the fire rescue force in city $$$i$$$ is defined as $$$a_i$$$. When the fire rescue force of city $$$i$$$ is dispatched to city $$$x$$$ for a mission, the workload increases by $$$\mathrm{dist}(i, x)$$$, i.e., $$$a_i \leftarrow a_i + \mathrm{dist}(i, x)$$$. Initially, the workload of every city is $$$0$$$.
The central command issues $$$q$$$ instructions in total:
- $$$1\ x\ y$$$: Mission execution — A disaster occurs in city $$$y$$$. The fire rescue forces of city $$$x$$$ and all its indirect subordinates are dispatched to city $$$y$$$ to provide support, each performing one mission to city $$$y$$$.
- $$$2\ x$$$: Workload query — Query the sum of workloads of the fire rescue forces of city $$$x$$$ and all its indirect subordinates.
The first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 5 \times 10^5$$$), the number of cities and the number of instructions, respectively.
The next $$$n-1$$$ lines each contain two integers $$$fa_{i+1}, w_{i+1}$$$ ($$$1 \le fa_{i+1} \lt i+1$$$, $$$1 \le w_{i+1} \le 100$$$), where the two integers on the $$$i$$$-th line represent the superior city of city $$$i+1$$$ and the length of the road connecting them.
The next $$$q$$$ lines each contain one instruction in one of the following forms:
- $$$1\ x\ y$$$ ($$$1 \le x, y \le n$$$): a type-1 instruction — mission execution;
- $$$2\ x$$$ ($$$1 \le x \le n$$$): a type-2 instruction — workload query.
For each type-2 instruction, output a single integer on a line — the total workload.
5 4 1 3 1 2 2 1 2 2 1 5 1 2 1 1 2 3 2 2
5 23
Z-tube Cat is studying how to efficiently activate the "Rat" skill in the board game Legends of the Three Kingdoms.
Rat: You may choose another player whose number of cards is greater than yours, and then take one card from them.
There are $$$n$$$ players in total, and you are player $$$1$$$. Initially, player $$$i$$$ has $$$a_i$$$ cards.
Determine the maximum number of cards you can have after activating Rat any number of times (possibly zero).
Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.
For each test case:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the number of players.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the initial number of cards of player $$$i$$$.
It is guaranteed that, within each test, the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output a single integer on a line — the maximum number of cards you can have after activating Rat any number of times.
2 3 0 3 1 4 0 2 3 0
2 2
In the Principle of Computer Organization lab course, the instructor has arranged $$$n$$$ experiments for students to choose from.
Subsequently, $$$m$$$ events occur in chronological order. Each event takes one of the following two forms:
- $$$1\ i\ x$$$: A student with student ID $$$x$$$ chooses experiment $$$i$$$. If this student is the $$$j$$$-th student to choose this experiment, then their index in this experiment is $$$j$$$.
- $$$2\ i_1\ j_1\ i_2\ j_2$$$: The student with index $$$j_1$$$ in experiment $$$i_1$$$ and the student with index $$$j_2$$$ in experiment $$$i_2$$$ swap experiments. More precisely, if before the swap, the student with index $$$j_1$$$ in experiment $$$i_1$$$ has student ID $$$x_1$$$, and the student with index $$$j_2$$$ in experiment $$$i_2$$$ has student ID $$$x_2$$$, then after the swap, the student with index $$$j_1$$$ in experiment $$$i_1$$$ will have student ID $$$x_2$$$, and the student with index $$$j_2$$$ in experiment $$$i_2$$$ will have student ID $$$x_1$$$.
After all $$$m$$$ events have occurred, the instructor needs to print the course roster. Finally, for each experiment, you need to output the number of students, followed by the IDs of the students in this experiment, in ascending order of index.
The first line contains two integers $$$n, m$$$ ($$$1 \le n, m \le 3 \times 10^5$$$), representing the number of experiments and the number of events, respectively.
The next $$$m$$$ lines describe each event in chronological order, following one of the two formats below:
- $$$1\ i\ x$$$: Student with ID $$$x$$$ selects the $$$i$$$th experiment. It is guaranteed that all values are integers, $$$1\le i\le n,10^{8}\le x \lt 10^{9}$$$, and this student has not selected any experiment before.
- $$$2\ i_1 \ j_1 \ i_2\ j_2$$$: Student $$$j_1$$$ (assigned to experiment $$$i_1$$$) swapped experiments with student $$$j_2$$$ (assigned to experiment $$$i_2$$$). It is guaranteed that all given values are integers, $$$1\le i_1,i_2\le n$$$ and $$$i_1\not= i_2$$$. Student $$$j_1$$$ is assigned to experiment $$$i_1$$$, and student $$$j_2$$$ is assigned to experiment $$$i_2$$$.
Output $$$n$$$ lines.
For the $$$i$$$-th line, first output the number of students who have chosen experiment $$$i$$$. If this number is non-zero, then output the student IDs of the students in experiment $$$i$$$ in ascending order of index. Adjacent integers on the same line should be separated by a single space.
3 4 1 1 250000001 1 3 250000006 2 3 1 1 1 1 1 250000003
2 250000006 250000003 0 1 250000001
4 9 1 3 835745037 1 3 927149742 1 2 468012503 1 4 314360098 2 3 1 4 1 1 4 501201700 1 3 271374639 2 4 2 2 1 1 3 678882127
0 1 501201700 4 314360098 927149742 271374639 678882127 2 835745037 468012503
I'm having a long, unending dream—
a dream I've had since long, long ago,
where I gaze upon the streets through the seasons,
hoping to meet again someone who never returns,
searching for something long forgotten, even by myself.
So much time, so many years have flowed past me.
In the endless night, I have waited alone—
waiting for the final dawn that finally arrives.
In the following discussion, we establish the following conventions:
- String indices start from $$$1$$$.
- For a string $$$s$$$, $$$s[l:r]$$$ denotes the string formed by concatenating $$$s_l, s_{l+1}, \cdots, s_r$$$ in order.
- $$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$ in binary.
- $$$\bigoplus\limits_{i=1}^n a_i = a_1 \oplus a_2 \oplus \cdots \oplus a_n$$$.
In Ayu's dream, there is a string $$$s$$$ of length $$$n$$$, consisting only of the digits $$$0$$$ and $$$1$$$. She needs to partition it into $$$k$$$ non-empty substrings $$$s[1:p_1], s[p_1+1:p_2], \cdots, s[p_{k-1}+1:n]$$$, where $$$1 \le p_1 \lt p_2 \lt \cdots \lt p_{k-1} \lt n$$$.
For each substring, she decides to treat its leftmost character as the most significant bit, interpreting it directly as a binary number.
Formally, if she partitions a substring $$$s[l:r]$$$, this substring is regarded as the binary representation of the decimal number $$$\sum\limits_{i=l}^r (2^{r-i} \times s_i)$$$. Leading zeros are permitted.
Ayu now defines the weight of a partitioning scheme as the bitwise XOR sum of these binary numbers. She wants to know, among all partitioning schemes, what the maximum possible weight is, and the number of schemes that achieve exactly this maximum weight.
However, Ayu has forgotten the value of $$$k$$$, so she needs the corresponding answers for each $$$k = 1, 2, \cdots, n$$$.
But she is just a little girl who struggles even with solving cubic equations, so she comes to Yuuichi—that is, you—for help.
Each test contains multiple test cases.
The first line contains an integer $$$T(1 \leq T \leq 10^4)$$$, indicating the number of test cases.
For each test case, a single line is given containing a string $$$s$$$ composed solely of $$$0$$$ and $$$1$$$.
It is guaranteed that the total length of all strings in each test does not exceed $$$3 \times 10^6$$$.
For each test case, to avoid excessive output, the following format is required.
(This format is for output reduction only; a correct solution works without it)
Let $$$p_1, p_2, \cdots, p_n$$$ be the maximum values (taken modulo $$$998244353$$$) for $$$k = 1, 2, \cdots, n$$$, and let $$$q_1, q_2, \cdots, q_n$$$ be the counts of schemes that achieve the maximum weight (also modulo $$$998244353$$$). Output four integers $$$A, B, C, D$$$ on a single line, separated by spaces, defined as follows:
$$$$$$ \begin{aligned} A&=\bigoplus_{i=1}^np_i\\ B&=\bigoplus_{i=1}^nq_i\\ C&=\bigoplus_{i=1}^n(p_i\times i)\\ D&=\bigoplus_{i=1}^n(q_i\times i)\\ \end{aligned} $$$$$$
Note: The modulo operation applies only to the individual $$$p_i$$$ and $$$q_i$$$ values. Do not apply modulo when computing $$$A, B, C, D$$$.
5 110 11010 1011010 101111011 11010101101
5 2 0 6 19 3 24 9 101 4 109 30 405 7 382 33 1225 6 1144 53
Atlansert encountered a leak, and the Z-tube Cat said there were stories hidden there.
Given a positive integer $$$n$$$ and two permutations $$$^{\text{*}}$$$ $$$r,c$$$ of length $$$n$$$.
Find a matrix satisfying all the following conditions:
- The matrix has $$$n$$$ rows and $$$n$$$ columns, with all elements being integers in the range $$$[0,n]$$$.
- The MEX$$$^{\text{†}}$$$ value of the element in the $$$i$$$th row is $$$r_i$$$.
- The MEX value of the $$$i$$$th column element is $$$c_i$$$.
It can be proved that such a matrix exists.
$$$^{\text{*}}$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in an arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation of length 5, but $$$[1,2,2]$$$ is not a permutation($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation($$$n=3$$$ but there is $$$4$$$ in the array).
$$$^{\text{†}}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:
- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not.
Each test contains multiple test cases. The first line contains an integer $$$T(1 \le T \le 10^3)$$$, indicating the number of test cases.
For each test case:
The first line gives a positive integer $$$n(1\le n\le2\times 10^3)$$$.
The second line provides a permutation of length $$$n$$$: $$$r_1, r_2, \ldots, r_n$$$.
The third line provides another permutation of length $$$n$$$: $$$c_1, c_2, \ldots, c_n$$$.
It is guaranteed that the sum of all $$$n$$$ values across all test cases does not exceed $$$2 \times 10^3$$$.
For each test case, output $$$n$$$ lines, each containing $$$n$$$ integers representing a matrix that satisfies all conditions of this problem. If multiple such matrices exist, output any one of them.
2 4 2 1 3 4 3 4 1 2 5 2 1 4 3 5 1 4 2 5 3
0 0 4 1 2 3 4 0 1 2 0 1 0 1 2 3 0 0 0 0 1 0 0 0 2 0 2 3 3 1 0 2 1 0 4 2 0 2 1 3 4
Capoo likes Codeforces Rounds, but he is picky - he only likes to take part in rounds with difficulty no lower than his current rating.
Suppose Capoo's rating is $$$x$$$. Initially, $$$x=0$$$.
There are $$$n$$$ CF rounds. For the $$$i$$$-th round, its difficulty is $$$a_i$$$, and it has a hidden score $$$b_i$$$. One round can only be participated in once.
Capoo will participate in a round only if $$$x \leq a_i$$$. After participating, Capoo's rating will be reset to $$$\max(b_i, x)$$$.
You may freely arrange the order of the rounds. How many rounds can Capoo participate in at most?
The first line contains an integer $$$n(1 \leq n \leq 10^6)$$$.
The next $$$n$$$ lines each contain two integers $$$a_i, b_i(0 \leq a_i, b_i \leq 10^{18})$$$, representing the difficulty and hidden value of the $$$i$$$-th round, respectively.
A line containing an integer, representing the maximum number of CF rounds that Capoo can participate in.
10 19 18 6 15 5 8 4 20 18 3 16 9 0 7 5 17 2 13 15 17
5