Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2

Problem Statement

Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.

Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq T_i \leq 10^9
• 0 \leq K_i < i
• 1 \leq A_{i,j} < i
• \sum_{i=1}^N K_i \leq 2\times 10^5
• A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} are all distinct.
• All values in input are integers.

Sample Input 1

3
3 0
5 1 1
7 1 1

Sample Output 1

10

Here is one possible plan for Takahashi.

• At time 0, start practicing for Move 1 to learn Move 1 at time 3.
• Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.

Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.

Sample Input 2

5
1000000000 0
1000000000 0
1000000000 0
1000000000 0
1000000000 4 1 2 3 4

Sample Output 2

5000000000

Note that the answer may not fit into a 32-bit integer.

Problem Statement

AtCoder cafeteria offers N main dishes and M side dishes. The price of the i-th main dish is A_i, and that of the j-th side dish is B_j. The cafeteria is considering introducing a new set meal menu. A set meal consists of one main dish and one side dish. Let s be the sum of the prices of the main dish and the side dish, then the price of the set meal is \min(s,P). Here, P is a constant given in the input.

There are NM ways to choose a main dish and a side dish for a set meal. Find the total price of all these set meals.

Constraints

• 1\leq N,M \leq 2\times 10^5
• 1\leq A_i,B_j \leq 10^8
• 1\leq P \leq 2\times 10^8
• All input values are integers.

Sample Input 1

2 2 7
3 5
6 1

Sample Output 1

24

• If you choose the first main dish and the first side dish, the price of the set meal is \min(3+6,7)=7.
• If you choose the first main dish and the second side dish, the price of the set meal is \min(3+1,7)=4.
• If you choose the second main dish and the first side dish, the price of the set meal is \min(5+6,7)=7.
• If you choose the second main dish and the second side dish, the price of the set meal is \min(5+1,7)=6.

Thus, the answer is 7+4+7+6=24.

Sample Input 2

1 3 2
1
1 1 1

Sample Output 2

6

Sample Input 3

7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

Sample Output 3

2115597124

Problem Statement

We have an N \times N chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.

• If S_{i,j}= ., the square (i, j) is empty.
• If S_{i,j}= #, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.

We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.

Notes

A white bishop on the square (i, j) can go to the following positions in one move.

• For each positive integer d, it can go to (i+d,j+d) if all of the conditions are satisfied.

  • The square (i+d,j+d) exists in the board.
  • For every positive integer l \le d, (i+l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i+d,j-d) if all of the conditions are satisfied.

  • The square (i+d,j-d) exists in the board.
  • For every positive integer l \le d, (i+l,j-l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j+d) if all of the conditions are satisfied.

  • The square (i-d,j+d) exists in the board.
  • For every positive integer l \le d, (i-l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j-d) if all of the conditions are satisfied.

  • The square (i-d,j-d) exists in the board.
  • For every positive integer l \le d, (i-l,j-l) is not occupied by a white pawn.

Constraints

• 2 \le N \le 1500
• 1 \le A_x,A_y \le N
• 1 \le B_x,B_y \le N
• (A_x,A_y) \neq (B_x,B_y)
• S_i is a string of length N consisting of . and #.
• S_{A_x,A_y}= .
• S_{B_x,B_y}= .

Sample Input 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

Sample Output 1

3

We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.

• (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)

Sample Input 2

4
3 2
4 2
....
....
....
....

Sample Output 2

-1

There is no way to move the bishop from (3,2) to (4,2).

Sample Input 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Sample Output 3

9

Problem Statement

There are N cards called card 1, card 2, \ldots, card N. On card i (1\leq i\leq N), an integer A_i is written.

For K=1, 2, \ldots, N, solve the following problem.

We have a bag that contains K cards: card 1, card 2, \ldots, card K.
Let us perform the following operation twice, and let x and y be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.

Print the expected value of \max(x,y), modulo 998244353 (see Notes).
Here, \max(x,y) denotes the value of the greater of x and y (or x if they are equal).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 2\times 10^5
• All values in the input are integers.

Sample Input 1

3
5 7 5

Sample Output 1

5
499122183
443664163

For instance, the answer for K=2 is found as follows.

The bag contains card 1 and card 2, with A_1=5 and A_2=7 written on them, respectively.

• If you draw card 1 in the first draw and card 1 again in the second draw, we have x=y=5, so \max(x,y)=5.
• If you draw card 1 in the first draw and card 2 in the second draw, we have x=5 and y=7, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 1 in the second draw, we have x=7 and y=5, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 2 again in the second draw, we have x=y=7, so \max(x,y)=7.

These events happen with the same probability, so the sought expected value is \frac{5+7+7+7}{4}=\frac{13}{2}. We have 499122183\times 2\equiv 13 \pmod{998244353}, so 499122183 should be printed.

Sample Input 2

7
22 75 26 45 72 81 47

Sample Output 2

22
249561150
110916092
873463862
279508479
360477194
529680742