VNOI CUP 2025 - Vòng loại thứ nhất
Points: 500
Upin and Ipin are two twin brothers. They are very close and often play together when they are not studying. Today, they are playing a game to see who has a better memory. They create a string ~s~ consisting only of the characters U and I. They need to choose a substring~^*~ ~t~ of ~s~, such that ~t~ contains at least one character U and at least one character I, and proceed to play the game on string ~t~.
According to their strengths, Upin has an advantage in remembering the characters U and Ipin has an advantage in remembering the characters I. If we denote ~cnt_\texttt{U}~ and ~cnt_\texttt{I}~ as the number of characters U and I in the substring ~t~, then the result of the game will be determined as follows:
if ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~, Upin will win,
if ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~, Ipin will win,
if neither wins, the result of the game is a draw.
Upin and Ipin have entrusted their friend Tpin with the task of being the referee. Tpin needs to choose the substring ~t~. To make the game decisive, Tpin must ensure that the result of the game is not a draw.
Help Tpin find a substring ~t~ of the given string ~s~ that satisfies this condition, or indicate that every way of choosing the substring ~t~ results in a draw. If there are multiple ways to choose the substring ~t~, find any valid way.
————————————————————————
~^*~ A string ~t~ is called a substring of ~s~ if ~t~ can be formed by deleting (zero or more) characters from the beginning of ~s~, and deleting (zero or more) characters from the end of ~s~.
Input
The first line contains an integer ~q~ (~1 \leq q \leq 10\,000~) — the number of games. The data for each game is described as follows.
The first and only line of each game contains a string ~s~ (~|s| \le 10^5~) consisting only of the characters I and U – describing the string chosen by Upin and Ipin for the ~i~-th game.
The data guarantees that the total length of all strings ~s~ in all games does not exceed ~10^5~.
Output
For each game round, print NO if all substrings ~t~ result in a draw.
Otherwise, print YES and two integers ~l, r~ ~(1 \leq l \leq r \leq |S|)~ describing how to choose ~t = s_l s_{l + 1} s_{l + 2} \ldots s_r~.
If there are multiple ways to choose, print any valid choice.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
Scoring
The total score for this problem is ~500~.
Sample Input 1
4
UUUIIIUIIUI
UU
IUUIIUUI
IU
Sample Output 1
Yes 3 11
No
Yes 2 7
No
Notes
In the first game, Tpin chooses the substring ~t~ = "UIIIUIIUI" with ~cnt_\texttt{I} = 6~ and ~cnt_\texttt{U} = 3~. Ipin will win because the condition ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~ is satisfied.
In the second game, Tpin cannot find a valid substring ~t~.
In the third game, Tpin chooses the substring ~t~ = "UUIIUU" with ~cnt_\texttt{I} = 2~ and ~cnt_\texttt{U} = 4~. Upin will win because the condition ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~ is satisfied.
In the fourth game, Tpin cannot find a valid substring ~t~.
Points: 1250
Given two positive integers ~n~ and ~m~. You are allowed to perform the following operation (zero or more times):
- Choose any number ~x~ ~(1 \le x \le m)~, then assign ~n \leftarrow n \times \gcd(n,x)~. Here, ~\gcd(n, x)~ is the greatest common divisor of ~n~ and ~x~.
The people on the planet Arrakis have always passed down a prophecy that whoever finds a way to transform the number ~n~ into ~m~ using the fewest operations will become the savior of the kingdom, The Messiah. The one who takes on this challenge must provide a sequence of operations to transform the number ~n~ or indicate that there is no way to transform ~n~ into ~m~ using the given operation.
Arrakis is in danger, a holy war is about to break out, so try to solve the challenge and see if you are the chosen one!
Input
Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 100~).
Each test case consists of a single line containing two positive integers ~n, m~ (~1 \leq n, m \leq 10^9~).
Output
For each test case, if there is no way to transform the number ~n~ into ~m~ using the given operation, print ~-1~. Otherwise, print on one line the integer ~k~ (~1 \le k \le 200~) — the minimum number of steps to transform ~n~ into ~m~, followed by ~k~ integers ~x_1, x_2, \ldots, x_k~ — the integers chosen for each step in order.
If there are multiple sequences of operations with the minimum number of steps to transform ~n~ into ~m~, print any of the sequences.
It can be shown that if it is possible to transform from ~n~ to ~m~, there will exist a sequence of transformations with no more than ~200~ operations.
Scoring
The total score for this problem is ~1250~.
Sample Input 1
5
2 2
1 6
6 216
2 12
4 2
Sample Output 1
0
-1
2 6 6
-1
-1
Notes
In the first test case, ~n = m = 2~, so no further operations are performed.
In the second test case, ~n = 1~. We can only choose ~x = 1~, and then assign ~n \gets \gcd(1, 1) = 1~. The operation cannot change ~n~, so there is no valid sequence of operations.
In the third test case, ~n = 6~, ~m = 216~. Coincidentally, ~216 = 6^3~, we can choose 2 operations with ~x~ both equal to ~6~. It can be shown that there is no sequence of operations to transform ~n = 6~ into ~m = 216~ with just 1 operation.
In the fifth test case, ~n = 4~, ~m = 2~. Since ~n > m~, and the operations cannot decrease the number ~n~, there is no sequence of operations that satisfies the condition.
After completing his studies, Kuroni started a business and founded the time management company OURO. After 1000 years of operation, OURO has grown from a small company to a multi-universe scale enterprise. Recently, the company has released a new type of stock with profits forecasted to soar straight to the moon.
There are ~n~ shareholders who want to invest in this stock. The shareholders are numbered from ~1~ to ~n~. Initially, all shareholders have no stocks, and their accounts have a balance of ~0~. There will be ~q~ events that occur, which belong to one of the following types:
~\texttt{1} \; p \; x~ — Shareholder ~p~ buys ~x~ shares (if ~x \ge 0~), or sells ~|x|~ shares (if ~x < 0~);
~\texttt{2} \; v~ — The company is profitable and receives dividends of ~v~. Every shareholder who owns shares will receive an amount proportional to the number of shares they hold. Specifically, let ~s~ be the number of shares a shareholder owns, then the amount credited to that shareholder's account will increase by ~s \cdot v~.
~\texttt{3} \; p~ — Shareholder ~p~ will withdraw the entire amount currently in their account. After the withdrawal, the balance in shareholder ~p~'s account will return to ~0~.
For each event of type ~3~, please report the amount that the shareholder will receive. Since the answers can be very large, you may print the answer after taking the modulus with ~10^9 + 7~.
Input
The first line contains two integers ~n~ and ~q~ (~1 \le n, q \le 5 \cdot 10^5~) — the number of shareholders and the number of events.
The ~i~-th line in the following ~q~ lines describes the ~i~-th event in the format as described in the problem statement.
~\texttt{1} \; p \; x~ (~1 \le p \le n~, ~-10^9 \le x \le 10^9~) — describes an event of type 1. It is guaranteed that after each of these events, no shareholder will have a negative number of shares.
~\texttt{2} \; v~ (~1 \le v \le 10^9~) — describes an event of type 2.
~\texttt{3} \; p~ (~1 \le p \le n~) — describes an event of type 3.
Output
For each event of type ~3~, print the amount that the shareholder receives, modulo ~10^9 + 7~.
Scoring
The total score for this problem is ~1500~.
Sample Input 1
3 8
1 1 5
2 3
1 2 10
2 2
3 1
2 4
3 2
3 1
Sample Output 1
25
60
20
Sample Input 2
1 8
1 1 1000
2 1
1 1 -100
2 2
3 1
1 1 -200
2 3
3 1
Sample Output 2
2800
2100
Notes
In the first example, there are ~n = 3~ shareholders. Only shareholders ~1~ and ~2~ make investments.
The table below describes the events related to shareholder ~1~.
# | Event | Description | Shares | Account Balance |
---|---|---|---|---|
Initial time | ~0~ | ~0~ | ||
1 | 1 1 5 | Shareholder invests | ~0 + 5 = 5~ | ~0~ |
2 | 2 3 | The company receives a dividend of ~3~ | ~5~ | ~0 + 5 \cdot 3 = 15~ |
4 | 2 2 | The company receives a dividend of ~2~ | ~5~ | ~15 + 5 \cdot 2 = 25~ |
5 | 3 1 | Shareholder profits with the amount of ~25~ | ~5~ | ~0~ |
6 | 2 4 | The company receives a dividend of ~4~ | ~5~ | ~0 + 5 \cdot 4 = 20~ |
8 | 3 1 | Shareholder profits with the amount of ~20~ | ~5~ | ~0~ |
The table below describes the events related to shareholder ~2~.
# | Event | Description | Shares | Account Balance |
---|---|---|---|---|
Initial time | ~0~ | ~0~ | ||
3 | 1 2 10 | Shareholder invests | ~0 + 10 = 10~ | ~0~ |
4 | 2 2 | The company receives a dividend of ~2~ | ~10~ | ~0 + 10 \cdot 2 = 20~ |
6 | 2 4 | The company receives a dividend of ~4~ | ~10~ | ~20 + 10 \cdot 4 = 60~ |
7 | 3 2 | Shareholder profits with the amount of ~60~ | ~10~ | ~0~ |
In the second example, there is ~n = 1~ shareholder. The table below describes the events of the second example.
# | Event | Description | Shares | Account Balance |
---|---|---|---|---|
Initial time | ~0~ | ~0~ | ||
1 | 1 1 1000 | Shareholder invests | ~0 + 1000 = 1000~ | ~0~ |
2 | 2 1 | The company receives a dividend of ~1~ | ~1000~ | ~0 + 1000 \cdot 1 = 1000~ |
3 | 1 1 -100 | Shareholder sells shares | ~1000 - 100 = 900~ | ~1000~ |
4 | 2 2 | The company receives a dividend of ~2~ | ~900~ | ~1000 + 900 \cdot 2 = 2800~ |
5 | 3 1 | Shareholder profits with the amount of ~2800~ | ~900~ | ~0~ |
6 | 1 1 -200 | Shareholder sells shares | ~900 - 200 = 700~ | ~0~ |
7 | 2 3 | The company receives a dividend of ~3~ | ~700~ | ~0 + 700 \cdot 3 = 2100~ |
8 | 3 1 | Shareholder profits with the amount of ~2100~ | ~700~ | ~0~ |
Points: 2250
Surely anyone studying computer science is familiar with the following puzzle when learning about recursion.
Given a board of size ~2^k \times 2^k~ and L-shaped tiles made up of 3 squares. The tiles can be rotated freely. Find a way to place the tiles on the board so that, except for the cell ~(r, c)~, all cells on the board are covered by exactly one tile.
The key to solving this puzzle is to realize that we can create larger L-shaped tiles from smaller ones and use the larger tiles to cover the board. To help you remember, a summary of the general algorithm to solve this puzzle will be described in the notes section below.
After teaching you this algorithm, the teacher was amazed to see that you understood and could apply it very quickly. The teacher then had to assign additional exercises related to this algorithm. Given a board of size ~2^k \times 2^k~, the rows are numbered ~0, 1, 2, \ldots, 2^k - 1~ from top to bottom, and the columns are numbered ~0, 1, 2, \ldots, 2^k - 1~ from left to right. Initially, the board has been covered with L-shaped tiles such that the cell ~(0, 0)~ is the uncovered cell according to the algorithm you have learned.
Then the teacher has ~q~ consecutive small puzzles. For the ~i~-th puzzle, the teacher wants to change the board from the state just before this puzzle to the state where the cell ~(r_i, c_i)~ is uncovered. To do this, the teacher allows you to perform the following operation (zero or more times):
- Choose an L-shaped tile that is adjacent to 2 edges of the uncovered cell. Rotate this tile 90 degrees in the direction you want. It can be seen that after this operation, a new cell will become the uncovered cell.
It can be shown that, with the initial tiling according to the algorithm you have learned, there is always a sequence of operations to rotate the tiles to change the uncovered cell from one cell to another.
Below is an illustration of how to perform the operation for the ~2^2 \times 2^2~ board. The teacher has posed three puzzles, each requiring the uncovered cell to be transformed as follows:
From cell ~(0, 0)~ to cell ~(2, 1)~, with 3 operations.
From cell ~(2, 1)~ to cell ~(0, 3)~, with 4 operations.
From cell ~(0, 3)~ to cell ~(0, 0)~, with 5 operations.
The teacher wants you to solve the puzzles as quickly as possible. Therefore, for each puzzle, you want to find out the minimum number of operations needed to answer that puzzle.
Input
The first line contains two integers ~k~ and ~q~ (~1 \le k \le 60~, ~1 \le q \le 10^5~). The parameter ~k~ indicates that the size of the board is ~2^k \times 2^k~, and the teacher will ask you ~q~ puzzles.
The ~i~-th line in the following ~q~ lines contains two integers ~r_i~ and ~c_i~ (~0 \le r_i, c_i < 2^k~) – the uncovered cell after the ~i~-th puzzle.
Output
Print ~q~ lines. The ~i~-th line contains an integer representing the minimum number of operations to solve the ~i~-th puzzle.
Scoring
Subtask | Points | Constraints |
---|---|---|
1 | ~500~ | ~k \le 5~, ~q \le 1000~ |
2 | ~750~ | ~k \le 10~ |
3 | ~1000~ | No additional constraints |
Total | ~2250~ |
Sample Input 1
2 3
2 1
0 3
0 0
Sample Output 1
3
4
5
Sample Input 2
3 4
6 2
7 7
3 4
4 6
Sample Output 2
10
10
7
5
Notes
The first example has been illustrated in the image above.
Below is an illustration for the second example.
Summary of the L-shaped tile covering algorithm
From small L-shaped tiles, we can create larger L-shaped tiles by combining them as follows:
To cover the board with L-shaped tiles, ensuring that the cell ~(0, 0)~ is not covered, we can combine them into larger L-shaped tiles and stack them as follows:
Points: 2750
Given a positive integer ~k~ and an array ~a~ consisting of ~n~ non-negative integers less than ~2^k~. For each permutation~^*~ ~p~ consisting of ~n~ elements from ~1~ to ~n~, define:
~f_i(p) = a_{p_1}\ \&\ a_{p_2}\ \& \ldots \&\ a_{p_{i-1}}\ \&\ a_{p_i}~ for ~1 \le i \le n~, where ~\&~ is the bitwise AND operation,
~g(p)~ is the index ~1 \le i \le n~ largest such that ~f_i(p) > 0~. If ~f_i(p) = 0~ for all ~1 \le i \le n~, then ~g(p) = 0~.
Calculate the sum of ~g(p)~ over all permutations ~p~, modulo ~998\,244\,353~.
———————————————————————–
~^*~ A permutation of ~n~ elements from ~1~ to ~n~ is a sequence containing the numbers ~1, 2, \ldots, n~ in any order. For example, ~[1, 3, 2, 4]~ and ~[5, 4, 1, 2, 3]~ are permutations, but ~[1, 4, 2]~ and ~[1, 4, 2, 2, 5]~ are not.
Input
Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 10\,000~). The description of each test case is as follows.
The first line contains two integers ~n~ and ~k~ (~1\le n \le 2^{20}~, ~1 \le k \le 20~) – the number of elements in ~a~ and the limit of the elements in ~a~ is ~2^k~.
The second line contains ~n~ non-negative integers ~a_1,a_2,\ldots,a_n~ (~0\le a_i<2^k~).
It is guaranteed that:
the sum of ~n~ across all test cases does not exceed ~2^{20}~,
the sum of ~2^k~ across all test cases does not exceed ~2^{20}~.
Output
For each test case, print an integer — the sum of ~g(p)~ over all permutations ~p~, modulo ~998\,244\,353~.
Scoring
Subtask | Points | Constraints |
---|---|---|
1 | ~250~ | ~k = 1~ |
2 | ~500~ | ~\sum n \le 2^{10}~ |
3 | ~500~ | ~\sum 2^k \le 2^{10}~ |
4 | ~1500~ | No additional constraints |
Total | ~2750~ |
Sample Input 1
2
3 1
1 0 1
8 3
0 1 2 3 4 5 6 7
Sample Output 1
6
67248
Notes
Let ~a_p = [a_{p_1}, a_{p_2}, \ldots, a_{p_n}]~.
In the first test case, we have ~a = [1, 0, 1]~.
There are 2 permutations ~p~ with ~g(p) = 1~, which are ~p = [1, 2, 3]~ and ~p = [3, 2, 1]~. Both have ~a_p = [1, 0, 1]~.
There are 2 permutations ~p~ with ~g(p) = 2~, which are ~p = [1, 3, 2]~ and ~p = [3, 1, 2]~. Both have ~a_p = [1, 1, 0]~.
The remaining permutations ~p~ have ~g(p) = 0~.
The answer for the test case is ~2 \cdot 1 + 2 \cdot 2 = 6~.
In the second test case, we have ~a~ as a permutation of ~8~ integers from ~0~ to ~7~. The table below shows the number of permutations ~p~ grouped by the value of ~g(p)~.
~g(p)~ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
# | 5040 | 13680 | 12960 | 6912 | 1728 | 0 | 0 | 0 | 0 |
Based on the table above, the answer for the test case is: $$5040 \cdot 0 + 13680 \cdot 1 + 12960 \cdot 2 + 6912 \cdot 3 + 1728 \cdot 4 + 0 \cdot 5 + 0 \cdot 6 + 0 \cdot 7 + 0 \cdot 8 = 67248$$
The kingdom of Pekoland has ~n~ cities numbered from ~1~ to ~n~. A day in Pekoland is divided into ~10^9~ time units, where time ~0~ is midnight. The people of Pekoland mainly travel between cities by plane. Every day, there are ~m~ flights in Pekoland, where the ~i~-th flight departs from city ~u_i~ at time ~x_i~ and lands in city ~v_i~ at time ~y_i~. Thanks to modern infrastructure, the check-in process at airports takes negligible time, so a passenger arriving in city ~u~ at time ~t~ can choose to take any flight departing from ~u~ from time ~t~ onwards.
There are two airlines operating in Pekoland, and all flights here are operated by either of them. Pekoland Airlines is the royal airline, and all flights of Pekoland Airlines are guaranteed to fly on schedule. In contrast, PekoJet Air is a newly established low-cost airline, and its flights may be canceled without notice. Nevertheless, PekoJet Air commits to having at most ~k~ flights canceled each day.
Aqua is a foreign tourist. She has just landed in city ~1~—the capital of Pekoland—at midnight (time ~0~). Aqua wants to fly to city ~n~, which is preparing to celebrate the ~50~-th anniversary of the unification of the kingdom. Assuming Aqua is in city ~u~ at time ~t~, she can choose to check in for one of the flights departing from ~u~ at time ~t~, or choose to do nothing (wait until time ~t+1~). If there are multiple flights departing at the same time, Aqua can only choose one flight to check in for, and she can only know whether that flight is canceled or not after she has checked in. If the flight is canceled, she will remain in city ~u~ at time ~t+1~; otherwise, she will land in the destination city according to the flight schedule.
To find the best spot for the parade the next morning, Aqua wants to reach city ~n~ within the day and as early as possible. Specifically, Aqua wants to know the smallest time ~x~ such that she can arrive at ~n~ before or at time ~x~, regardless of which flights are canceled. If Aqua cannot be sure to reach ~n~ within the day, print ~-1~. Please help Aqua!
Input
Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.
The first line contains three integers ~n~, ~m~, ~k~ (~2 \leq n \leq 10^5~, ~1 \leq m \leq 2 \cdot 10^5~, ~0 \leq k \leq m~) — the number of cities in Pekoland, the number of daily flights in Pekoland, and the maximum number of flights of PekoJet Air that can be canceled in a day.
The ~i~-th of the next ~m~ lines contains five integers ~u_i~, ~v_i~, ~x_i~, ~y_i~, ~p_i~ (~1 \leq u_i, v_i \leq n~, ~u_i \neq v_i~, ~0 \leq x_i < y_i < 10^9~, ~1 \leq p_i \leq 2~) describing a flight. The ~i~-th flight departs from city ~u_i~ at time ~x_i~ and lands in city ~v_i~ at time ~y_i~. The ~i~-th flight is operated by Pekoland Airlines if ~p_i = 1~ and by PekoJet Air if ~p_i = 2~.
It is guaranteed that:
the sum of ~n~ across all test cases does not exceed ~10^5~,
the sum of ~m~ across all test cases does not exceed ~2 \cdot 10^5~.
Output
For each test case, print the smallest time ~x~ such that Aqua can arrive at ~n~ before or at time ~x~, regardless of how many flights are canceled. If she cannot be sure to reach ~n~ within the day, print ~-1~.
Scoring
Subtask | Points | Constraints |
---|---|---|
1 | ~500~ | ~p_i = 1~ for all ~1 \leq i \leq m~ |
2 | ~1000~ | ~\sum n \le 1\,000~, ~\sum m \le 1\,000~ |
3 | ~1750~ | No additional constraints |
Total | ~3250~ |
Sample Input 1
3
2 4 1
1 2 0 12 1
1 2 2 10 2
1 2 3 7 2
1 2 3 4 2
5 6 1
1 2 1 5 1
1 3 1 5 1
1 4 1 5 1
2 5 5 10 2
3 5 5 10 2
4 5 5 10 2
4 7 2
1 2 0 2 2
1 3 1 3 1
2 3 2 3 2
2 4 4 6 1
3 2 3 4 2
3 4 4 7 2
3 4 5 7 2
Sample Output 1
10
-1
7
Notes
In the first example, Aqua can arrive at city ~2~ at the latest by time ~10~ with the following plan:
Skip flight ~1~, check in for flight ~2~ at time ~2~.
If flight ~2~ is not canceled, Aqua lands in city ~2~ at time ~10~.
Otherwise, Aqua checks in for flight ~4~. This flight is guaranteed not to be canceled since flight ~2~ has been canceled, so Aqua lands in city ~2~ at time ~4~.
Note that if Aqua does not check in for flight ~2~, she cannot ensure reaching city ~2~, as flights ~3~ and ~4~ depart at the same time and she can only choose to check in for one of these two flights (and the flight she chooses can always be canceled).
Here is an illustration for the first example:
The blue edge represents flights from ~\color{blue}{Pekoland\,Airlines}~.
The red edge represents flights from ~\color{red}{PekoJetAir}~.
The green number on the edge is the departure time of flight ~\color{green}{x_i}~.
The orange number on the edge is the landing time of flight ~\color{orange}{y_i}~.
Illustration for the first example
In the second example, Aqua can choose to fly to city ~2~, ~3~, or ~4~ at time ~5~. However, regardless of which city she chooses, the only flight connecting that city to city ~5~ could be canceled. Therefore, the answer is ~-1~.
Illustration for the second example
In the third example, PekoJetAir guarantees that no more than 2 flights will be canceled. Aqua can reach city ~4~ at the latest by time ~7~.
At city ~1~, at time ~0~, Aqua can check in for a flight from PekoJet Air.
If the flight is not canceled, Aqua can continue to city ~4~ on a flight from Pekoland Airlines at time ~6~. Aqua has reached her destination.
If the flight is canceled, Aqua arrives in city ~3~ at time ~3~ on a flight from Pekoland Airlines.
When at city ~3~ at time ~3~, Aqua can try a flight from PekoJet Air to city ~2~.
If the flight is not canceled, Aqua can continue to city ~4~ on a flight from Pekoland Airlines at time ~6~. Aqua has reached her destination.
If the flight is canceled, Aqua stays in city ~3~ and considers the flight to city ~4~.
By this time, PekoJet Air has canceled 2 flights, so the airline cannot cancel any more flights.
Aqua can take any flight from PekoJet Air to city ~4~ at time ~7~. Aqua has reached her destination.
Illustration for the third example
Points: 4000
Tahp is a boy fascinated by the beauty of the overlapping mountain ranges. One day, while playing with his favorite sequence of numbers, he suddenly came up with an interesting idea about how to arrange the elements in the sequence to form the shape of a mountain.
Let Tahp's favorite sequence be ~a~ of length ~n~. He calls ~a~ a mountain array if there exists an integer ~k~ satisfying all of the following conditions:
~1 \le k \le n~
~a_i \le a_{i+1}~ for all ~1 \le i < k~
~a_i \le a_{i-1}~ for all ~k < i \le n~
In other words, the sequence will not decrease from position ~1~ to ~k~, and then not increase from position ~k~ to ~n~ afterwards, resembling the shape of a mountain.
It is clear that not every sequence is a mountain array, so Tahp needs to swap two consecutive elements in the given sequence multiple times to transform it into a mountain array. He defines the mountain difference of a sequence as the minimum number of consecutive swaps needed to transform that sequence into a mountain array.
Tahp writes down all the distinct permutations~^*~ of the sequence ~a~, and then selects two special sequences ~l~ and ~h~. Now, he wants to calculate the total mountain difference of all distinct permutations ~p~ of ~a~ that satisfy ~l \le p \le h~ in lexicographic order~^\dagger~.
Your task is to help Tahp calculate the total mountain difference of all distinct permutations that satisfy the above condition. Since the result can be very large, you only need to provide the remainder after dividing it by ~998\,244\,353~.
——————————————-
~^*~ A permutation of a sequence is another sequence that has the same set of elements (including duplicates, if any), but can be arranged in any order. For example, ~[1, 2, 2, 3]~, ~[2, 3, 1, 2]~, and ~[2, 2, 1, 3]~ are some of the permutations of ~[3, 2, 1, 2]~, but ~[2, 4, 3, 1]~, ~[2, 1, 2]~, and ~[1, 1, 2, 3]~ are not. Two permutations are considered different if there exists a position where the value of the element in this permutation differs from the value of the element at the same position in the other permutation.
~^\dagger~ Given two integer sequences ~a = [a_1, a_2, \ldots, a_n]~ and ~b = [b_1, b_2, \ldots, b_n]~. We say that ~a~ is less than or equal to ~b~ in lexicographic order (denoted ~a \le b~) if ~a_i = b_i~ for all ~1 \le i \le n~, or if ~a_j < b_j~ where ~j~ is the smallest index satisfying ~a_j \neq b_j~.
Input
The first line contains an integer ~t~ (~1 \le t \le 10~) — the number of test cases. The description of each test case is as follows.
The first line contains a single integer ~n~ (~1 \le n \le 1000~) — the length of Tahp's favorite sequence.
The second line contains ~n~ integers ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~) — Tahp's favorite sequence.
The third line contains ~n~ integers ~l_1, l_2, \dots, l_n~ (~1 \le l_i \le n~) — the selected sequence ~l~.
The last line contains ~n~ integers ~h_1, h_2, \dots, h_n~ (~1 \le h_i \le n~) — the selected sequence ~h~.
It is guaranteed that ~l~ and ~r~ are permutations of ~a~, and ~l \le h~ in lexicographic order.
Output
Print ~t~ lines, where the ~i~-th line contains a single integer which is the result for the ~i~-th test case after taking the remainder with ~998\,244\,353~.
Scoring
Segment | Points | Constraints |
---|---|---|
1 | ~750~ | ~l_i = h_i~ for all ~1 \le i \le n~ |
2 | ~1250~ | ~n \le 200~ |
3 | ~1000~ | ~a~ is a permutation of the sequence ~1, 2, \ldots, n~ |
4 | ~1000~ | No additional constraints |
Total | ~4000~ |
Sample Input 1
2
4
1 2 2 3
2 1 3 2
3 2 1 2
5
1 3 2 4 5
2 1 5 3 4
5 2 4 1 3
Sample Output 1
5
146
Notes
In the first test case, there are ~7~ distinct permutations that satisfy as follows:
~[2, 1, 3, 2]~ has a mountain difference of ~1~: ~[\underline{2, 1}, 3, 2] \rightarrow [1, 2, \hat{3}, 2]~
~[2, 2, 1, 3]~ has a mountain difference of ~1~: ~[2, 2, \underline{1, 3}] \rightarrow [2, 2, \hat{3}, 1]~
~[2, 2, 3, 1]~ has a mountain difference of ~0~: ~[2, 2, \hat{3}, 1]~
~[2, 3, 1, 2]~ has a mountain difference of ~1~: ~[2, 3, \underline{1, 2}] \rightarrow [2, \hat{3}, 2, 1]~
~[2, 3, 2, 1]~ has a mountain difference of ~0~: ~[2, \hat{3}, 2, 1]~
~[3, 1, 2, 2]~ has a mountain difference of ~1~: ~[\underline{3, 1}, 2, 2] \rightarrow [1, \hat{3}, 2 , 2]~
~[3, 2, 1, 2]~ has a mountain difference of ~1~: ~[3, 2, \underline{1, 2}] \rightarrow [\hat{3}, 2, 2, 1]~
The total mountain difference is ~1 + 1 + 0 + 1 + 0 + 1 + 1 = 5~