Problem Statement

There is a weighted tree T with N vertices numbered 1 to N. The i-th edge of T connects vertices A_i and B_i with weight C_i.

We now construct a complete undirected graph G with N vertices numbered 1 to N, based on T. For each edge of G, the capacity is defined as follows.

• The capacity of edge (i,j) of G is the minimum weight of an edge contained in the path connecting vertices i and j on T.

Let f(i,j) be the capacity of the minimum cut separating vertices i and j on G.

Find \sum_{1 \leq i < j \leq N} f(i,j), modulo 998244353.

Solve S cases for each input.

Constraints

• 1 \leq S \leq 125000
• 2 \leq N \leq 250000
• 1 \leq A_i,B_i \leq N
• 1 \leq C_i \leq 10^{12}
• The input graph is a tree.
• The sum of N over the S cases is at most 250000.
• All input values are integers.

Sample Input 1

4
3
1 2 1
2 3 10
4
1 2 1
2 3 10
3 4 2
13
11 4 337329830
13 1 72247
4 1 1768959
5 4 5399893
2 8 1832265
12 7 107755
10 4 743
5 12 95
4 3 389684075
2 6 1222
11 8 253280162722
9 4 21671
15
8 5 285187324995
14 10 755031423304
2 8 88860861719
12 7 596982637940
10 4 225447687713
7 15 210989590191
13 5 836365489027
6 15 859904883890
8 1 362117197524
12 8 422952343663
1 14 112179584332
15 11 487330735107
12 9 528451854379
3 7 343910842803

Sample Output 1

15
32
13620068
909241492

In the first test case, the capacities of edges (1,2),(1,3),(2,3) of G are 1,1,10, respectively. The answer is f(1,2)+f(1,3)+f(2,3)=2+2+11=15.

Problem Statement

You are given a sequence of positive integers of length N, A=(A_1,A_2,\ldots,A_N). Find, modulo 998244353, the number of sequences of positive integers of length N, x=(x_1,x_2,\ldots,x_N), satisfying all of the following conditions.

• x_i \leq A_i holds for all i.
• There exists a permutation p=(p_1,p_2,\ldots,p_{2N-1}) of (1,2,\ldots,2N-1) satisfying the following condition.
  • For each i (1 \leq i \leq N), consider the sequence of length N, (p_i,p_{i+1},\ldots,p_{i+N-1}). There are exactly x_i different values that are "prefix max" of this sequence. More precisely, the number of indices j (i \leq j \leq i+N-1) such that p_j = \max_{i \leq k \leq j} p_k is x_i.

Constraints

• 2 \leq N \leq 50
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

2
2 2

Sample Output 1

4

For example, consider x=(2,1). The condition is satisfied by p=(2,3,1).

There are four possible values of x: (1,1),(1,2),(2,1),(2,2).

Sample Input 2

2
1 2

Sample Output 2

2

Sample Input 3

3
3 3 3

Sample Output 3

20

For example, consider x=(3,1,3). No choice of p satisfies the conditions.

Sample Input 4

4
3 2 4 3

Sample Output 4

44

Sample Input 5

10
8 3 8 10 1 5 3 1 6 4

Sample Output 5

2590

Sample Input 6

50
29 43 38 17 46 49 39 39 48 27 35 46 50 25 47 38 25 38 32 22 50 42 47 37 26 50 37 30 44 49 22 38 35 44 50 44 46 46 41 48 32 15 6 32 49 37 38 45 33 31

Sample Output 6

969185665

Problem Statement

Define the score of a sequence of length N, x=(x_1,x_2,\ldots,x_N), as \prod_{1 \leq i \leq N} (i+x_i).

You are given a strictly increasing sequence of non-negative integers of length N, A=(A_1,A_2,\ldots,A_N).

Solve the following problem for each d=0,1,\ldots,N-1.

• Consider the sequences x obtained by rearranging the elements of A such that there are exactly d indices i with x_i>x_{i+1}. Find, modulo 998244353, the sum of the scores over all such sequences.

Constraints

• 2 \leq N \leq 80
• 0 \leq A_1 < A_2 < \cdots < A_N < 998244353
• All input values are integers.

Sample Input 1

2
0 1

Sample Output 1

3 4

The permutations and scores corresponding to each d are as follows.

• d=0:
  • x=(0,1): the score is (1+0) \times (2+1)=3
• d=1:
  • x=(1,0): the score is (1+1) \times (2+0)=4

Sample Input 2

3
0 1 2

Sample Output 2

15 84 27

The permutations and scores corresponding to each d are as follows.

• d=0:
  • x=(0,1,2): the score is (1+0) \times (2+1) \times (3+2)=15
• d=1:
  • x=(0,2,1): the score is (1+0) \times (2+2) \times (3+1)=16
  • x=(1,0,2): the score is (1+1) \times (2+0) \times (3+2)=20
  • x=(1,2,0): the score is (1+1) \times (2+2) \times (3+0)=24
  • x=(2,0,1): the score is (1+2) \times (2+0) \times (3+1)=24
• d=2:
  • x=(2,1,0): the score is (1+2) \times (2+1) \times (3+0)=27

Sample Input 3

4
1 2 4 8

Sample Output 3

672 9766 11824 1350

Sample Input 4

10
19237225 22672563 250040585 250876592 344065186 404191279 519729086 709423541 785439575 945005786

Sample Output 4

950922061 100128042 407190855 824408778 310751908 135850478 488617013 247896647 212541677 410171196

Sample Input 5

80
22039836 28981946 30860430 45459908 69714419 80565655 86264514 88704853 91058795 111982636 139793596 151769562 164543594 197971506 210619166 221745114 225051881 238856535 245101681 248730678 255908811 256810168 272481811 273714212 283615535 284686636 297323928 298241991 319502970 321722967 360690308 361481447 366075547 418633758 422209788 423073188 433378197 437330820 459117401 480124392 485979799 486475154 490049033 498896932 504089816 518458804 520999410 531470304 542901248 560047125 582857561 595934547 619322493 622712481 627798362 686621115 695016247 712639027 714635866 721488863 735151983 742973826 753705854 758288417 768080799 775681305 834897126 851716760 855572558 858395194 905527130 907645400 908902333 922571073 933505674 948631706 966125570 978445563 979797105 985573661

Sample Output 5

298255098 551019397 284987769 99242062 369815630 718585554 688109983 392309922 737456536 523073775 694983953 356882261 567442787 317777842 776589570 791050897 233517530 674210008 665902332 505999118 194082824 507392235 703668642 165275650 789544696 135388036 169254144 708650783 647965741 603841383 863435804 818717034 510094830 247810285 479685478 505643001 637957324 951738617 677727811 891846762 611641571 564907071 866950984 142999964 318492053 834273618 862706905 372559206 72047272 966554479 825019950 285454795 341834405 779072147 246845153 958325353 790516997 805752624 345221877 580204783 779467953 925770800 711605667 652190020 304063629 645132429 538451131 174490604 596444184 12799293 750957647 585286962 463254142 857306647 282172657 929005032 870614339 445303380 729482922 179226742

Problem Statement

You are given permutations P and Q of (1,2,\ldots,N). Here, P is lexicographically not greater than Q.

You can perform the following operation zero or more times.

• Choose two adjacent elements of P and swap them. Here, the following conditions must be satisfied.
  • P after the operation is still lexicographically not greater than Q.
  • Let (x,y) be the two values being swapped. The pair (x,y) has never been swapped in previous operations. Here, the order of x,y does not matter. That is, once (x,y) has been swapped, neither (x,y) nor (y,x) can be swapped again.

Find the lexicographically greatest permutation that P can become in the end.

Solve T cases for each input.

Constraints

• 1 \leq T \leq 500000
• 2 \leq N \leq 10^6
• P is a permutation of (1,2,\ldots,N).
• Q is a permutation of (1,2,\ldots,N).
• P is lexicographically not greater than Q.
• The sum of N over the T cases is at most 10^6.
• All input values are integers.

Sample Input 1

6
3
1 2 3
3 1 2
3
2 3 1
3 1 2
4
3 1 4 2
4 2 3 1
4
2 3 4 1
3 4 1 2
4
1 3 4 2
1 4 2 3
5
4 2 5 3 1
4 2 5 3 1

Sample Output 1

3 1 2
2 3 1
4 2 1 3
3 2 4 1
1 3 4 2
4 2 5 3 1

In the first test case, it is optimal to perform operations as follows.

• Start with P=(1,2,3).
• Swap (2,3), resulting in P=(1,3,2).
• Swap (1,3), resulting in P=(3,1,2).

In the second test case, it is optimal to perform no operations at all.

Problem Statement

There is a board with N rows and M columns. Let us call the cell at the i-th row from the top and j-th column from the left cell (i,j).

Each cell is empty or has one piece placed on it. The state of the board is given by N length-M strings S_1,S_2,\ldots,S_N: if the j-th character of S_{i} is ., cell (i,j) is empty, and if it is O, cell (i,j) has a piece placed on it.

For integers L and R (1 \leq L \leq R \leq N), define f(L,R) as follows.

• Extract only rows L through R of the board, obtaining a board with R-L+1 rows. Call this new board X.

• You can repeat the following operation on X zero or more times.

  • Choose one piece and move it to any of the cells adjacent to it (up, down, left, or right). Here, the destination cell must not have another piece on it. Also, you cannot perform an operation that would move a piece outside of X.

• Your goal is to reach a state where, for every row of X, the number of pieces in that row is even. If it is impossible to achieve the goal, let f(L,R)=0. If it is possible, let f(L,R) be the minimum number of operations required to do so.

Find \sum_{1 \leq L \leq R \leq N} f(L,R), modulo 998244353.

Solve T cases for each input.

Constraints

• 1 \leq T \leq 250000
• 2 \leq N \leq 500000
• 2 \leq M \leq 10
• S_i is a string of length M consisting of . and O.
• The sum of N over the T cases is at most 500000.

Sample Input 1

7
3 2
O.
O.
.O
4 3
OOO
OOO
...
OOO
5 3
OOO
OOO
..O
OOO
...
7 3
OOO
..O
OOO
OOO
O..
OOO
.OO
8 3
OO.
OOO
OOO
..O
OOO
.O.
.OO
O..
4 5
.O..O
OOOOO
OOOOO
.O.O.
10 10
O.O..O..OO
........O.
OOO.O.OO.O
O..O..OOOO
OO..O.....
.OOOO..OO.
O.......O.
OOO.O.....
O.O.O....O
.....OO.O.

Sample Output 1

3
5
9
7
29
9
44

The values of f(L,R) in the first test case are as follows.

• f(1,1)=0
• f(1,2)=2
• f(1,3)=0
• f(2,2)=0
• f(2,3)=1
• f(3,3)=0