Problem Statement

There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_i \leq A_{i+1} \ (1 \leq i < N)
• All input values are integers.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

8

The sizes of the given mochi are as follows:

In this case, you can make the following eight kinds of kagamimochi:

Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.

Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.

Sample Input 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

Sample Output 3

388

Problem Statement

There are N black balls and M white balls.
Each ball has a value. The value of the i-th black ball (1 \le i \le N) is B_i, and the value of the j-th white ball (1 \le j \le M) is W_j.

Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• -10^9 \leq B_i, W_j \leq 10^9
• All input values are integers.

Sample Input 1

4 3
8 5 -1 3
3 -2 -4

Sample Output 1

19

If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is 8+5+3+3=19, which is the maximum.

Sample Input 2

4 3
5 -10 -2 -5
8 1 4

Sample Output 2

15

If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is 5+(-2)+8+4=15, which is the maximum.

Sample Input 3

3 5
-36 -33 -31
12 12 28 24 27

Sample Output 3

0

It is possible to choose no balls.

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

• If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.

• If the j-th character of S_i is ., then (i, j) is an empty cell without a player.

• If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

• Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

• N is an integer between 2 and 60, inclusive.
• S_i is a string of length N consisting of P, ., and #.
• There are exactly two pairs (i, j) where the j-th character of S_i is P.

Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

3

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

• Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).

• Choose up. Player 1 does not move, and Player 2 moves to (3, 2).

• Choose left. Player 1 does not move, and Player 2 moves to (3, 1).

Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

Sample Output 3

10

Problem Statement

The Kingdom of AtCoder has N cities called City 1,2,\ldots,N and M roads called Road 1,2,\ldots,M.
Road i connects Cities A_i and B_i bidirectionally and has a length of C_i.
One can travel between any two cities using some roads.

Under financial difficulties, the kingdom has decided to maintain only N-1 roads so that one can still travel between any two cities using those roads and abandon the rest.

Let d_i be the total length of the roads one must use when going from City 1 to City i using only maintained roads. Print a choice of roads to maintain that minimizes d_2+d_3+\ldots+d_N.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i < B_i \leq N
• (A_i,B_i)\neq(A_j,B_j) if i\neq j.
• 1\leq C_i \leq 10^9
• One can travel between any two cities using some roads.
• All values in input are integers.

Sample Input 1

3 3
1 2 1
2 3 2
1 3 10

Sample Output 1

1 2

Here are the possible choices of roads to maintain and the corresponding values of d_i.

• Maintain Road 1 and 2: d_2=1, d_3=3.
• Maintain Road 1 and 3: d_2=1, d_3=10.
• Maintain Road 2 and 3: d_2=12, d_3=10.

Thus, maintaining Road 1 and 2 minimizes d_2+d_3.

Sample Input 2

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

Sample Output 2

3 1 2

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is black or white, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

• if the j-th character of S_i is ., square (i,j) is white;
• if the j-th character of S_i is #, square (i,j) is black.

The grid is said to be beautiful when the following condition is satisfied.

• For every pair of integers (i,j) such that 1 \le i \le N, 1 \le j \le M, if square (i,j) is black, the square under (i,j) and the square to the immediate lower right of (i,j) are also black (if they exist).
• Formally, all of the following are satisfied.
  • If square (i,j) is black and square (i+1,j) exists, square (i+1,j) is also black.
  • If square (i,j) is black and square (i+1,j+1) exists, square (i+1,j+1) is also black.

Takahashi can paint zero or more white squares black, and he will do so to make the grid beautiful.
Find the number of different beautiful grids he can make, modulo 998244353.
Two grids are considered different when there is a square that has different colors in those two grids.

Constraints

• 1 \le N,M \le 2000
• S_i is a string of length M consisting of . and #.

Sample Input 1

2 2
.#
..

Sample Output 1

3

He can make the following three different beautiful grids:

.#  .#  ##
.#  ##  ##

Sample Input 2

5 5
....#
...#.
..#..
.#.#.
#...#

Sample Output 2

92

Sample Input 3

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

Sample Output 3

604936632

Find the count modulo 998244353.