Little G is an intelligent being living on planet $$$\mathbf{H}$$$. On this planet, there are endless fields of flowers, and Little G loves hopping among them. On the $$$(10^9+7)$$$-th day of playing in the flower fields, Little G learned about Manhattan distance and immediately invented a game with it.
Little G's game works as follows: choose a square patch of flowers and divide it into $$$n^2$$$ identical smaller squares arranged in $$$n$$$ rows and $$$n$$$ columns, then hop between all the vertices of these squares. Each hop must cover a Manhattan distance of exactly a given positive integer $$$K$$$. Moreover, Little G does not want to get lost, so he wants to eventually return to the starting point after a sequence of hops.
Little G quickly found a simple solution: start at a corner vertex, hop to a vertex at Manhattan distance $$$K$$$, and hop back. This immediately gives all solutions with an even number of hops. But Little G thinks this is too easy — he wants to find solutions with an odd number of hops, and asks for your help.
Based on his experience, Little G believes that finding the minimum number of hops is sufficient to construct solutions with more hops. So you only need to report the minimum number of hops among all solutions with an odd number of hops, or report that no such solution exists. Since Little G has not yet decided on $$$n$$$ or $$$K$$$, he will ask you $$$T$$$ queries, each specifying positive integers $$$n$$$ and $$$K$$$.
To help you (a human) better understand the mysterious ideas of planet $$$\mathbf{H}$$$'s inhabitants: consider all vertices of the divided squares as lattice points in the Cartesian plane with both coordinates being integers in $$$[0, n]$$$. We call these special points. A hop between two special points $$$\mathbf{I}(x_1,y_1)$$$ and $$$\mathbf{T}(x_2,y_2)$$$ is valid if and only if $$$|x_1-x_2|+|y_1-y_2|=K$$$.
For each query with given positive integers $$$n$$$ and $$$K$$$: determine whether there exists a cycle starting and ending at some special point, following the hopping rules, with an odd number of hops. If such a cycle exists, output the minimum number of hops; otherwise, output $$$-1$$$.
The first line contains an integer $$$T$$$ ($$$1\le T\le 10^5$$$) — the number of queries. The next $$$T$$$ lines each contain two integers $$$n$$$ ($$$1\le n\le 10^8$$$) and $$$K$$$ ($$$1\le K\le 2n$$$).
Output $$$T$$$ lines, each containing a single integer. If a cycle with an odd number of hops exists, output the minimum number of hops; otherwise, output $$$-1$$$.
31 12 24 8
-1 3 -1
In Japanese, the digits $$$1$$$ through $$$9$$$ are pronounced as follows:
| Digit | Japanese |
| 1 | ichi |
| 2 | ni |
| 3 | san |
| 4 | yon |
| 5 | go |
| 6 | roku |
| 7 | nana |
| 8 | hachi |
| 9 | kyuu |
To read a multi-digit number, simply concatenate the Japanese readings of each digit from left to right. For example, $$$15$$$ is read as ichigo, and $$$893$$$ is read as hachikyuusan.
What is $$$72$$$ in Japanese?
This problem has no input.
Output a single string — the Japanese reading of $$$72$$$.
Given a positive integer $$$N$$$, define the repunit $$$R(k)$$$ as the number consisting of $$$k$$$ ones, i.e., $$$R(k) = \underbrace{11\ldots1}_{k}$$$.
Find the largest positive integer $$$k$$$ such that $$$R(k)$$$ is a divisor of $$$N$$$, and output $$$k$$$.
Note that $$$R(1) = 1$$$ divides every positive integer, so the answer is at least $$$1$$$.
The first line contains a positive integer $$$T$$$ — the number of test cases.
The next $$$T$$$ lines each contain a positive integer $$$N$$$ (with no leading zeros).
$$$1 \le T \le 5 \times 10^5$$$, $$$1 \le |N| \le 10^5$$$, $$$\sum |N| \le 5 \times 10^5$$$, where $$$|N|$$$ denotes the number of decimal digits of $$$N$$$.
Output $$$T$$$ lines, each containing a positive integer $$$k$$$.
31221997
3 2 1
In the first example, $$$1221 = 111 \times 11$$$, so $$$R(3) = 111$$$ divides $$$N$$$. $$$R(4) = 1111$$$ does not divide $$$N$$$, so the answer is $$$3$$$.
In the second example, $$$99 = 11 \times 9$$$, so $$$R(2) = 11$$$ divides $$$N$$$. $$$R(3) = 111 \gt 99$$$, so the answer is $$$2$$$.
In the third example, $$$7$$$ is not a multiple of $$$11$$$, so the answer is $$$1$$$.
This is an interactive problem.
There is a hidden partition of the integers $$$1, 2, \ldots, n$$$ into $$$\frac{n}{k}$$$ disjoint $$$k$$$-tuples. It is guaranteed that $$$k \mid n$$$.
You need to determine all hidden $$$k$$$-tuples through queries.
In each query, you may choose a set $$$S \subseteq \{1, 2, \ldots, n\}$$$, and the interactor will return an integer indicating how many hidden $$$k$$$-tuples are entirely contained in $$$S$$$.
The number of queries must not exceed $$$n\lceil \log_2 n \rceil$$$.
At the start of your program, the interactor outputs a line with two integers $$$n$$$ and $$$k$$$.
Here $$$2 \le n \le 300$$$, $$$2 \le k \le n$$$, and $$$k \mid n$$$.
The hidden partition is stored by the interactor and is not given directly.
After each valid query you output, the interactor returns a line with a single integer $$$r$$$ — the number of hidden $$$k$$$-tuples entirely contained in the set you queried.
You may make queries of the following form:
where $$$0 \le c \le n$$$, and $$$x_1, x_2, \ldots, x_c$$$ must be pairwise distinct integers satisfying $$$1 \le x_i \le n$$$.
This query means you choose the set $$$S=\{x_1,x_2,\ldots,x_c\}$$$. The interactor returns an integer $$$r$$$ — the number of hidden $$$k$$$-tuples entirely contained in $$$S$$$.
When you have determined the answer, output:
where $$$a_i$$$ denotes the tuple number that element $$$i$$$ belongs to. The numbering must satisfy $$$1 \le a_i \le \frac{n}{k}$$$. Two elements in the same hidden tuple must have the same number; two elements in different hidden tuples must have different numbers. The ordering of tuple numbers is arbitrary.
The number of queries must not exceed $$$n\lceil \log_2 n \rceil$$$. After outputting the final answer, your program should terminate immediately.
Note that after each query or the final answer, you must flush the output buffer. For example, in C++ you can use:
or
If your output format is invalid, the number of queries exceeds the limit, or the final answer is wrong, you will receive Wrong Answer or Presentation Error.
The interactor is non-adaptive, meaning all $$$k$$$-tuples are fixed before the interaction begins and do not change based on your queries.
6 2 1 1 3
? 3 1 3 5 ? 4 2 3 4 5 ? 6 1 2 3 4 5 6 ! 1 2 1 3 3 2
In the example below, $$$n = 6$$$, $$$k = 2$$$, and the hidden tuples are $$$\{1, 3\}$$$, $$$\{2, 6\}$$$, $$$\{4, 5\}$$$.
| Program | Interactor |
| 6 2 | |
| ? 3 1 3 5 | 1 |
| ? 4 2 3 4 5 | 0 |
| ? 6 1 2 3 4 5 6 | 3 |
| ! 1 2 1 3 3 2 |
Query $$$\{1,3,5\}$$$: tuple $$$\{1,3\} \subseteq S$$$, so the answer is $$$1$$$.
Query $$$\{2,3,4,5\}$$$: tuple $$$\{4,5\} \subseteq S$$$, so the answer is $$$1$$$.
Query $$$\{1,2,3,4,5,6\}$$$: all three tuples are contained, so the answer is $$$3$$$.
Output ! 1 2 1 3 3 2 means: elements $$$1, 3$$$ form group $$$1$$$; elements $$$2, 6$$$ form group $$$2$$$; elements $$$4, 5$$$ form group $$$3$$$.
$$$tarjen$$$ has recently been playing Roco Kingdom and wants to catch some shiny spirits.
To farm shiny spirits, $$$tarjen$$$ must first repeatedly catch regular spirits. Catching regular spirits accumulates the pollution progress of a shiny pool. When the pollution progress reaches the required threshold, a corrupted spirit belonging to that pool spawns on the map. After defeating a corrupted spirit, there is a chance to encounter a shiny spirit.
However, the number of corrupted spirits on the map is limited. If too many spawn, old corrupted spirits are pushed out by new ones.
Additionally, there is a pity mechanism for shiny encounters. Each shiny pool has an independent pity counter. Each time a corrupted spirit from that pool is defeated, the pool's pity counter increases by one. When a pool's pity counter reaches $$$80$$$, defeating a corrupted spirit from that pool is guaranteed to trigger a shiny encounter.
The detailed rules are as follows.
There are $$$n$$$ types of regular spirits, $$$A$$$ families, and $$$B$$$ elements. The $$$i$$$-th type of regular spirit belongs to family $$$fa_i$$$ and has element $$$el_i$$$.
There are two types of shiny pools:
- Family pool $$$F_x$$$: the shiny pool for the $$$x$$$-th family.
- Element pool $$$E_x$$$: the shiny pool for the $$$x$$$-th element.
Each shiny pool $$$P$$$ maintains four values:
- $$$progress_P$$$: pollution progress, initially $$$0$$$.
- $$$pity_P$$$: pity counter, initially $$$0$$$.
- $$$need_P$$$: the number of regular catches needed to spawn one corrupted spirit (a given constant).
- $$$luck_P$$$: the luck threshold (a given constant).
At most $$$m$$$ corrupted spirits can exist on the map simultaneously. All corrupted spirits are arranged in a queue ordered by spawn time (oldest first). If the count exceeds $$$m$$$, the oldest corrupted spirits are removed from the front until the count is at most $$$m$$$. Corrupted spirits pushed out by the map capacity are not considered defeated and do not affect any pool's pity counter.
There are $$$q$$$ operations, each being one of the following two types.
Operation 1: Regular Catch
C T x c
$$$tarjen$$$ catches the $$$x$$$-th type of regular spirit $$$c$$$ times consecutively, crediting these $$$c$$$ catches to a certain shiny pool. If $$$T = F$$$, credit to family pool $$$F_{fa_x}$$$; if $$$T = E$$$, credit to element pool $$$E_{el_x}$$$.
Let the credited pool be $$$P$$$. Set $$$progress_P \mathrel{+}= c$$$. Then, whenever $$$progress_P \ge need_P$$$, spawn one corrupted spirit belonging to pool $$$P$$$ and set $$$progress_P \mathrel{-}= need_P$$$.
Note that a single catch operation may spawn multiple corrupted spirits.
The newly spawned corrupted spirits are appended to the end of the queue in order. If the count exceeds $$$m$$$, the oldest corrupted spirits are removed from the front.
Operation 2: Defeat Corrupted Spirit
B k r
$$$tarjen$$$ challenges the $$$k$$$-th corrupted spirit on the map (ordered from oldest to newest).
If there are fewer than $$$k$$$ corrupted spirits on the map, output MISS and no state changes occur.
Otherwise, let the corrupted spirit belong to pool $$$P$$$. Remove it from the map and set $$$pity_P \mathrel{+}= 1$$$.
Then perform the shiny check. Each pool $$$P$$$ has a luck threshold $$$luck_P$$$. If $$$r \le luck_P$$$ or $$$pity_P = 80$$$, a shiny is encountered: output SHINY P and set $$$pity_P = 0$$$. Otherwise, output NORMAL P $$$pity_P$$$.
The first line contains five integers $$$n, A, B, m, q$$$ ($$$\boldsymbol{1 \le n, A, B, m, q \le 2 \times 10^5}$$$) — the number of regular spirit types, the number of families, the number of elements, the maximum number of corrupted spirits on the map, and the number of operations.
The next $$$n$$$ lines each contain two integers $$$fa_i, el_i$$$ ($$$1 \le fa_i \le A$$$, $$$1 \le el_i \le B$$$).
The next line contains $$$A$$$ integers $$$need_{F_1}, \ldots, need_{F_A}$$$ ($$$1 \le need_{F_i} \le 10^9$$$).
The next line contains $$$B$$$ integers $$$need_{E_1}, \ldots, need_{E_B}$$$ ($$$1 \le need_{E_i} \le 10^9$$$).
The next line contains $$$A$$$ integers $$$luck_{F_1}, \ldots, luck_{F_A}$$$ ($$$0 \le luck_{F_i} \le 10^9$$$).
The next line contains $$$B$$$ integers $$$luck_{E_1}, \ldots, luck_{E_B}$$$ ($$$0 \le luck_{E_i} \le 10^9$$$).
The next $$$q$$$ lines each describe an operation in the format C T x c ($$$\boldsymbol{T \in \{F, E\}}$$$, $$$\boldsymbol{1 \le x \le n}$$$, $$$\boldsymbol{1 \le c \le 10^{18}}$$$) or B k r ($$$\boldsymbol{1 \le k \le 10^{18}}$$$, $$$\boldsymbol{1 \le r \le 10^9}$$$).
For each B operation, output one line. If there are fewer than $$$k$$$ corrupted spirits on the map, output MISS. Otherwise, if a shiny is encountered, output SHINY F x or SHINY E x; if not, output NORMAL F x p or NORMAL E x p, where $$$x$$$ is the shiny pool index and $$$p$$$ is the pool's current pity counter.
5 2 2 5 101 21 12 21 12 22 22 340 54 41C E 5 9C E 4 5B 2 608984673B 4 918347739B 4 37535012C E 5 7B 1 712704464C F 4 7B 3 270899745B 5 363752455
NORMAL E 2 1 NORMAL E 1 1 MISS NORMAL E 2 2 NORMAL F 1 1 MISS
3 2 1 3 81 11 12 12 320 510C F 1 2C E 2 4B 2 50C F 3 6B 3 3B 5 1C F 1 2B 3 100
NORMAL E 1 1 SHINY F 2 MISS NORMAL F 1 1
For sample 2:
Let $$$\mathit{F1}$$$ denote a corrupted spirit from pool $$$F\ 1$$$, and $$$\mathit{E1}$$$ denote a corrupted spirit from pool $$$E\ 1$$$.
After the first two catch operations, the corrupted spirits on the map are $$$[\mathit{F1}, \mathit{E1}, \mathit{E1}]$$$.
Execute B 2 50: defeat the 2nd spirit ($$$\mathit{E1}$$$). $$$50 \gt luck_{E1} = 10$$$ and $$$pity = 1 \ne 80$$$, output NORMAL E 1 1.
Then catch the 3rd type of spirit and credit to the family pool, spawning $$$2$$$ copies of $$$\mathit{F2}$$$. Map capacity is $$$3$$$, so after eviction the map becomes $$$[\mathit{E1}, \mathit{F2}, \mathit{F2}]$$$.
Execute B 3 3: defeat the 3rd spirit ($$$\mathit{F2}$$$). $$$3 \le luck_{F2} = 5$$$, shiny encountered, output SHINY F 2.
Execute B 5 1: fewer than $$$5$$$ spirits on the map, output MISS.
The last defeat is $$$\mathit{F1}$$$, no shiny encountered, output NORMAL F 1 1.
Given an integer $$$K$$$ and two arrays $$$a_{1\sim 2^{K}-1}$$$ and $$$b_{1\sim 2^{K}-1}$$$, each of size $$$2^{K}-1$$$.
There is an undirected complete graph $$$G$$$ of size $$$2^K$$$ with vertices numbered $$$0\sim 2^K - 1$$$.
For a spanning tree $$$T$$$ of $$$G$$$, define $$$A(T)=\prod_{(u,v)\in T}a_{u\oplus v}$$$, $$$B(T)=\sum_{(u,v)\in T}b_{u\oplus v}$$$, $$$C(T)=\oplus_{(u,v)\in T}(u\oplus v)$$$.
For each $$$0\le x \lt 2^K$$$, compute $$$(\sum_{T,C(T)=x}A(T)B(T)^p) \bmod 998244353$$$, where $$$p$$$ is a given constant.
We define $$$0^0=1$$$.
The first line contains two integers $$$K,p$$$ ($$$1\le K\le 16$$$, $$$0\le p\le 5$$$).
The next line contains $$$2^K-1$$$ integers, where the $$$i$$$-th integer is $$$a_i$$$ ($$$0\le a_i \lt 998244353$$$).
The next line contains $$$2^K-1$$$ integers, where the $$$i$$$-th integer is $$$b_i$$$ ($$$0\le b_i \lt 998244353$$$).
Output a single line with $$$2^K$$$ integers, where the $$$i$$$-th integer is the answer for $$$x=i-1$$$.
2 01 1 11 2 3
4 4 4 4
2 22 3 51 4 2
5880 5416 10464 9640
Given an integer sequence $$$a$$$ of length $$$n$$$ with values in $$$[0,2]$$$.
An operation is defined as choosing an index $$$x\in [1,n-2]$$$:
- Let $$$s=(a_x+a_{x+1}+a_{x+2})\bmod 3$$$, then set $$$a_x,a_{x+1},a_{x+2}$$$ all to $$$s$$$ simultaneously.
You need to perform some operations (possibly none) to maximize the sum of all elements in sequence $$$a$$$. Additionally, you must provide a valid operation sequence whose length does not exceed $$$\lfloor\dfrac{5}{7}n\rfloor+100$$$.
This problem has multiple test cases.
The first line contains an integer $$$T$$$ — the number of test cases.
For each test case:
The first line contains an integer $$$n$$$ — the length of sequence $$$a$$$.
The second line contains $$$n$$$ integers, where the $$$i$$$-th integer is $$$a_i$$$.
For each test case:
The first line should contain two integers $$$s$$$ and $$$K$$$ — the maximum sum of the sequence and the number of operations, respectively. You must ensure $$$0\le K\le \lfloor\dfrac{5}{7}n\rfloor+100$$$.
The next line should contain $$$K$$$ positive integers, where the $$$i$$$-th integer is the index $$$x$$$ chosen in the $$$i$$$-th operation.
330 1 050 2 1 2 271 1 1 1 1 1 1
3 1 1 10 4 2 2 3 1 14 5 1 3 4 5 1
For $$$100\%$$$ of the data, it is guaranteed that $$$1\le T\le 1000$$$, $$$\sum n\le 10^6$$$, $$$3\le n\le 10^6$$$, $$$0\le a_i\le 2$$$.
Given a simple undirected connected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges, you need to choose two distinct edges to delete, obtaining a new graph $$$G'$$$, such that $$$G'$$$ remains connected.
Let the two deleted edges be $$$(p,q)$$$ and $$$(u,v)$$$. You need to minimize the sum of the shortest path between $$$p$$$ and $$$q$$$ in $$$G'$$$ plus the shortest path between $$$u$$$ and $$$v$$$ in $$$G'$$$. Output this minimum value and the number of deletion schemes that achieve it.
This problem has multiple test cases.
The first line contains an integer $$$T$$$ — the number of test cases.
For each test case:
The first line contains two integers $$$n,m$$$.
The next $$$m$$$ lines each contain two integers $$$u,v$$$, representing an edge.
The graph has no multi-edges or self-loops. It is guaranteed that at least one deletion scheme exists such that the graph remains connected.
$$$1\le T\le 5000$$$, $$$1\le \sum n,\sum m \le 5000$$$, $$$4\le n$$$, $$$5\le m$$$.
For each test case:
Output a single line with two integers — the minimum value and the number of schemes.
44 61 21 31 42 32 43 44 51 22 33 41 41 35 61 32 31 42 41 52 55 71 22 33 44 51 52 51 4
4 15 4 4 6 12 4 4
Koishi found a positive integer sequence $$$a = [a_1, a_2, \cdots, a_n]$$$ of length $$$n$$$ on the road, satisfying $$$1\le a_i\le n$$$. She then computed the prefix maximum sequence $$$b = [b_1, b_2, \cdots, b_n]$$$, where $$$b_i$$$ is the maximum of the first $$$i$$$ elements of $$$a$$$:
$$$$$$b_i = \max\{a_1, a_2, \cdots, a_i\} = \max_{1\le j\le i}\{a_j\}$$$$$$
After obtaining both sequences, Koishi merged them together, defining a sequence $$$c$$$ of length $$$2n$$$ as $$$c = [a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n]$$$, and sorted $$$c$$$ in non-decreasing order.
Being the girl of the unconscious, Koishi lost the values of $$$a$$$ and $$$b$$$, and only the sequence $$$c$$$ remains.
Being the girl of the unconscious, Koishi has given the sequence $$$c$$$ to you — the cutest college student of the 21st century — hoping that you can find any valid sequence $$$a$$$. There may be multiple valid sequences; you only need to output any one of them. There may also be no valid sequence, in which case you should report that no solution exists.
The first line contains an integer $$$T$$$ — the number of test cases. The next $$$T$$$ sections each describe one test case:
- The first line contains an integer $$$n$$$ — the length of sequence $$$a$$$.
- The second line contains a sequence $$$c$$$ of length $$$2 \times n$$$, with adjacent integers separated by spaces. It is guaranteed that $$$c$$$ is non-decreasing and $$$1\le c_i\le n$$$.
It is guaranteed that $$$1\le \sum n\le 3\times 10^5$$$.
For each test case:
- If a solution exists, print "Yes" on the first line, then output $$$n$$$ integers $$$[a_1, a_2, \cdots, a_n]$$$ on the second line, separated by spaces.
- If no solution exists, print "No" on a single line.
"Yes" and "No" are case-insensitive. For example, "Yes", "YES", "yEs" are all accepted as positive answers, and "No", "NO", "nO" are all accepted as negative answers.
5 3 1 1 2 2 3 3 3 1 1 1 1 2 3 6 1 1 1 1 1 4 4 4 5 5 5 5 5 1 1 1 2 3 4 5 5 5 5 9 2 3 3 4 4 5 8 9 9 9 9 9 9 9 9 9 9 9
Yes 1 2 3 No Yes 1 1 4 5 1 4 No Yes 9 9 8 2 4 4 3 5 3
$$$tarjen$$$ has a permutation $$$p$$$ of length $$$n$$$. You may perform at most one operation: choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and reverse the subarray $$$p_l, p_{l+1}, \ldots, p_r$$$.
What is the maximum number of inversions in the permutation after the operation?
An inversion is a pair of indices $$$(i, j)$$$ satisfying $$$1 \le i \lt j \le n$$$ and $$$p_i \gt p_j$$$.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.
Each test case:
- The first line contains an integer $$$n$$$ ($$$1 \le n \le 8000$$$) — the length of the permutation.
- The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation.
The sum of $$$n$$$ over all test cases does not exceed $$$8000$$$.
For each test case, output a single integer — the maximum number of inversions.
332 1 355 4 3 2 163 5 1 4 2 6
2 10 10
Reversing the interval $$$[1, 3]$$$ yields $$$[3, 1, 2]$$$, which has $$$2$$$ inversions: $$$(1,2)$$$ and $$$(1,3)$$$.
$$$tarjen$$$ is playing a game of combining two trees into one graph.
He took two trees on $$$n$$$ vertices and combined them into an undirected unweighted graph $$$G = (V, E)$$$ with $$$n$$$ vertices and $$$m = 2n - 2$$$ edges.
But now he cannot decompose the graph back into two trees — please help him!
Formally, partition all edges into exactly two sets $$$T$$$ and $$$E \setminus T$$$ such that both $$$T$$$ and $$$E \setminus T$$$ form spanning trees of $$$G$$$.
You may output any valid partition. It is guaranteed that a valid partition exists.
The graph may contain parallel edges but no self-loops.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.
For each test case:
The first line contains an integer $$$n$$$ ($$$2 \le n \le 5000$$$) — the number of vertices.
The next $$$2n - 2$$$ lines each contain two integers $$$u, v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), describing an edge. Edges are numbered from $$$1$$$ to $$$2n-2$$$ in input order.
The sum of $$$n$$$ over all test cases does not exceed $$$10000$$$.
For each test case, output $$$n - 1$$$ integers in ascending order — the edge indices included in the first spanning tree. The remaining $$$n - 1$$$ edges must also form a spanning tree.
231 22 31 31 241 22 33 41 41 32 4
1 2 1 2 3
First test case: edges $$$\{1, 2\}$$$ correspond to $$$\{(1,2), (2,3)\}$$$, forming a spanning tree. The remaining edges $$$\{3, 4\}$$$ correspond to $$$\{(1,3), (1,2)\}$$$, also forming a spanning tree.
Second test case: edges $$$\{1, 2, 3\}$$$ correspond to $$$\{(1,2), (2,3), (3,4)\}$$$, forming a spanning tree. The remaining edges $$$\{4, 5, 6\}$$$ correspond to $$$\{(1,4), (1,3), (2,4)\}$$$, also forming a spanning tree.
Dou Di Zhu (Fight the Landlord) is one of the most popular card games in China. The game uses a standard 54-card deck (52 regular cards + 2 jokers).
In Dou Di Zhu, a straight is a hand of at least 5 cards with consecutive ranks. The ranks in ascending order are: 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. Note that 2 and the jokers cannot appear in a straight.
$$$tarjen$$$ currently holds 17 cards and loves straights. He wants to know the length of the longest straight he can play. Can you help him?
If no straight can be played, output 0.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
The next $$$t$$$ lines each contain 17 space-separated strings representing 17 cards. Each card is represented as follows:
- 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A: the card of the corresponding rank
- 2: the card ranked 2
- SJ: the small joker
- BJ: the big joker
Each regular card (A, 2$$$\sim$$$10, J, Q, K) appears at most 4 times per test case. The small and big jokers each appear at most once.
For each test case, output a single integer — the length of the longest straight that can be played. If no straight exists (i.e., there is no consecutive rank sequence of length $$$\ge 5$$$), output 0.
23 4 5 6 7 3 4 5 6 7 2 2 2 2 SJ BJ A2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 7
5 0
The ranks available for a straight are 3, 4, 5, 6, 7, and A. The longest consecutive sequence is $$$3, 4, 5, 6, 7$$$, with length $$$5$$$.
$$$tarjen$$$ is the guardian of the Crystal Castle. The castle's corridor is inlaid with a row of $$$n$$$ magic crystals, where the $$$i$$$-th crystal has color number $$$a_i$$$. Adjacent crystals of the same color resonate and form a color segment — a maximal run of consecutive identical colors. For example, the color sequence $$$[1, 1, 2, 2, 1]$$$ has $$$3$$$ color segments: $$$[1, 1]$$$, $$$[2, 2]$$$, and $$$[1]$$$.
Every day, travelers come and ask $$$q$$$ questions. Each question specifies an interval $$$[l, r]$$$: if we take out these crystals, randomly shuffle them (choosing uniformly at random among all permutations with repetition), what is the expected number of color segments?
Output the answer modulo $$$998244353$$$. That is, if the answer is an irreducible fraction $$$\frac{p}{q}$$$, output $$$p \cdot q^{-1} \bmod 998244353$$$. It can be shown that $$$q^{-1} \bmod 998244353$$$ always exists under the constraints of this problem.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 100\,000$$$) — the number of test cases.
For each test case:
The first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 100\,000$$$) — the number of crystals and the number of queries.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the color of each crystal.
The next $$$q$$$ lines each contain two integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of the query interval.
The sum of $$$n$$$ over all test cases does not exceed $$$100\,000$$$, and the sum of $$$q$$$ does not exceed $$$100\,000$$$.
For each query, output a single integer — the expected number of color segments modulo $$$998244353$$$.
14 21 1 2 21 21 4
1 3
110 53 5 3 3 6 4 8 2 3 56 91 88 104 97 7
474868327236654962411
For the first sample:
The first query: the crystal colors taken out are $$$[1, 1]$$$. There is only one permutation, and the number of color segments is $$$1$$$.
The second query: the crystal colors taken out are $$$[1, 1, 2, 2]$$$. The $$$6$$$ permutations have color segment counts $$$2, 4, 3, 3, 4, 2$$$, and the expected value is $$$\frac{18}{6} = 3$$$.