Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

• C[a][b] is #.
• C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
• At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

• 3 \leq H, W \leq 100
• C[i][j] is # or ..
• No two different squares that comprise two different crosses share a corner.
• H and W are integers.

Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

• Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
• Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
  • For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

• H and W are integers.
• 1 \le H,W
• 1 \le H \times W \le 4 \times 10^5
• S_i and T_i are strings of length W consisting of # and ..

Sample Input 1

3 4
##.#
##..
#...
.###
..##
...#

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes

Problem Statement

You are given positive integers A and B.

You will repeat the following operation until A=B:

• compare A and B to perform one of the following two:
  • if A > B, replace A with A-B;
  • if A < B, replace B with B-A.

How many times will you repeat it until A=B? It is guaranteed that a finite repetition makes A=B.

Constraints

• 1 \le A,B \le 10^{18}
• All values in the input are integers.

Sample Input 1

3 8

Sample Output 1

4

Initially, A=3 and B=8. You repeat the operation as follows:

• A<B, so replace B with B-A=5, making A=3 and B=5.
• A<B, so replace B with B-A=2, making A=3 and B=2.
• A>B, so replace A with A-B=1, making A=1 and B=2.
• A<B, so replace B with B-A=1, making A=1 and B=1.

Thus, you repeat it four times.

Sample Input 2

1234567890 1234567890

Sample Output 2

0

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

Sample Input 3

1597 987

Sample Output 3

15

Problem Statement

For a positive integer n, define A_n as the least common multiple of 1, 2, \dots, n.
You are given positive integers L and R. How many distinct integers are contained in the sequence (A_L, A_{L+1}, \dots, A_R)?

Constraints

• 1 \leq L \leq R \leq 10^{14}
• R - L \leq 10^7
• L and R are integers.

Sample Input 1

4 12

Sample Output 1

6

Listing A_4 through A_{12}:

• A_4 = 12
• A_5 = 60
• A_6 = 60
• A_7 = 420
• A_8 = 840
• A_9 = 2520
• A_{10} = 2520
• A_{11} = 27720
• A_{12} = 27720

Thus, (A_4, A_5, \dots, A_{12}) contains six distinct integers.

Sample Input 2

123456789 123456789

Sample Output 2

1

Sample Input 3

99999990000000 100000000000000

Sample Output 3

310458

Problem Statement

There is a row of N squares labeled 1,2,\dots,N and a sequence A=(A_1,A_2,\dots,A_N) of length N.
Initially, square 1 is painted black, the other N-1 squares are painted white, and a piece is placed on square 1.

You may repeat the following operation any number of times, possibly zero:

• When the piece is on square i, choose a positive integer x and move the piece to square i + A_i \times x.
  • Here, you cannot make a move with i + A_i \times x > N.
• Then, paint the square i + A_i \times x black.

Find the number of possible sets of squares that can be painted black at the end of the operations, modulo 998244353.

Constraints

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

Sample Input 1

5
1 2 3 1 1

Sample Output 1

8

There are eight possible sets of squares painted black:

• Square 1
• Squares 1,2
• Squares 1,2,4
• Squares 1,2,4,5
• Squares 1,3
• Squares 1,4
• Squares 1,4,5
• Squares 1,5

Sample Input 2

1
200000

Sample Output 2

1

Sample Input 3

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

721419738

Be sure to find the number modulo 998244353.