Problem Statement

You are given two positive integers A and B.

Output the square of A + B.

Constraints

• 1 \leq A,B \leq 2025
• All input values are integers.

Sample Input 1

20 25

Sample Output 1

2025

(20+25)^2=2025.

Sample Input 2

30 25

Sample Output 2

3025

Sample Input 3

45 11

Sample Output 3

3136

Sample Input 4

2025 1111

Sample Output 4

9834496

Problem Statement

Among the 81 integers that appear in the 9-by-9 multiplication table, find the sum of those that are not X.

There is a grid of size 9 by 9.
Each cell of the grid contains an integer: the cell at the i-th row from the top and the j-th column from the left contains i \times j.
You are given an integer X. Among the 81 integers written in this grid, find the sum of those that are not X. If the same value appears in multiple cells, add it for each cell.

Constraints

• X is an integer between 1 and 81, inclusive.

Sample Input 1

1

Sample Output 1

2024

The only cell with 1 in the grid is the cell at the 1st row from the top and 1st column from the left. Summing all integers that are not 1 yields 2024.

Sample Input 2

11

Sample Output 2

2025

There is no cell containing 11 in the grid. Thus, the answer is 2025, the sum of all 81 integers.

Sample Input 3

24

Sample Output 3

1929

Problem Statement

A positive integer not less than 10 whose top digit (the most significant digit) in decimal representation is strictly larger than every other digit in that number is called a Snake number. For example, 31 and 201 are Snake numbers, but 35 and 202 are not.

Find how many Snake numbers exist between L and R, inclusive.

Constraints

• 10 \leq L \leq R \leq 10^{18}
• All input values are integers.

Sample Input 1

97 210

Sample Output 1

6

The Snake numbers between 97 and 210, inclusive, are 97, 98, 100, 200, 201, and 210: there are six.

Sample Input 2

1000 9999

Sample Output 2

2025

Sample Input 3

252509054433933519 760713016476190692

Sample Output 3

221852052834757

Problem Statement

You are given a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell is one of the following: a start cell, a goal cell, an empty cell, or an obstacle cell. This information is described by H strings S_1,S_2,\dots,S_H, each of length W. Specifically, the cell (i,j) is a start cell if the j-th character of S_i is S, a goal cell if it is G, an empty cell if it is ., and an obstacle cell if it is #. It is guaranteed that there is exactly one start cell and exactly one goal cell.

You are currently on the start cell. Your objective is to reach the goal cell by repeatedly moving to a cell adjacent by an edge to the one you are in. However, you cannot move onto an obstacle cell or move outside the grid, and you must alternate between moving vertically and moving horizontally each time. (The direction of the first move can be chosen arbitrarily.)

Determine if it is possible to reach the goal cell. If it is, find the minimum number of moves required.

More formally, check if there exists a sequence of cells (i_1,j_1),(i_2,j_2),\dots,(i_k,j_k) satisfying all of the following conditions. If such a sequence exists, find the minimum value of k-1.

• For every 1 \leq l \leq k, it holds that 1 \leq i_l \leq H and 1 \leq j_l \leq W, and (i_l,j_l) is not an obstacle cell.
• (i_1,j_1) is the start cell.
• (i_k,j_k) is the goal cell.
• For every 1 \leq l \leq k-1, |i_l - i_{l+1}| + |j_l - j_{l+1}| = 1.
• For every 1 \leq l \leq k-2, if i_l \neq i_{l+1}, then i_{l+1} = i_{l+2}.
• For every 1 \leq l \leq k-2, if j_l \neq j_{l+1}, then j_{l+1} = j_{l+2}.

Constraints

• 1 \leq H,W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of S, G, ., #.
• There is exactly one start cell and exactly one goal cell.

Sample Input 1

3 5
.S#.G
.....
.#...

Sample Output 1

7

As shown in the left figure, you can move as (1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(2,4)\rightarrow(2,5)\rightarrow(1,5), reaching the goal cell in 7 moves. It is impossible in 6 moves or fewer, so the answer is 7.

Note that you cannot take a path that moves horizontally (or vertically) consecutively without alternating as shown in the right figure.

Sample Input 2

3 5
..#.G
.....
S#...

Sample Output 2

-1

It is not possible to reach the goal cell.

Sample Input 3

8 63
...............................................................
..S...#............................#####..#####..#####..####G..
..#...#................................#..#...#......#..#......
..#####..####...####..####..#..#...#####..#...#..#####..#####..
..#...#..#..#...#..#..#..#..#..#...#......#...#..#..........#..
..#...#..#####..####..####..####...#####..#####..#####..#####..
................#.....#........#...............................
................#.....#........#...............................

Sample Output 3

148

Problem Statement

The digit sum of a positive integer n is defined as the sum of its digits when n is written in decimal. For example, the digit sum of 2025 is 2 + 0 + 2 + 5 = 9.
A positive integer n is called a good integer if it is divisible by its digit sum. For example, 2025 is a good integer because it is divisible by its digit sum of 9.
A pair of positive integers (a, a+1) is called twin good integers if both a and a+1 are good integers. For example, (2024, 2025) is twin good integers.

You are given a positive integer N. Find a pair of twin good integers (a, a + 1) such that N \leq a and a + 1 \leq 2N. If no such pair exists, report that fact.

Constraints

• N is an integer at least 1 and less than 10^{100000}.

Sample Input 1

5

Sample Output 1

8

(8, 9) is a valid pair of twin good integers satisfying the conditions. Other examples include (5, 6), (6, 7), (7, 8), (9, 10).

Sample Input 2

21

Sample Output 2

-1

No pair of twin good integers satisfies the conditions.

Sample Input 3

1234

Sample Output 3

2024

(2024, 2025) is a valid pair of twin good integers.

Sample Input 4

1234567890123456789012345678901234567890

Sample Output 4

1548651852734633803438094164372911259190

Problem Statement

You are given positive integers N, M, and a sequence A = (A_1, A_2, \dots, A_N) of length N, each element being an integer between 1 and N, inclusive.

Find the number, modulo 998244353, of sequences x = (x_1, x_2, \dots, x_N) of length N, each element being an integer between 1 and M, inclusive, that satisfy the following condition:

• x_i \leq x_{A_i} for every i (1 \leq i \leq N).

Constraints

• 1 \leq N, M \leq 2025
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

3 3
2 1 1

Sample Output 1

6

The sequences x=(1,1,1),(2,2,1),(2,2,2),(3,3,1),(3,3,2),(3,3,3) satisfy the condition.

Sample Input 2

4 9
1 1 1 1

Sample Output 2

2025

Sample Input 3

10 5
9 4 5 5 4 2 1 5 7 2

Sample Output 3

10010

Problem Statement

Find the number, modulo 998244353, of simple undirected connected graphs G with N vertices labeled from 1 to N that satisfy the following condition:

• For every circuit in G, the number of edges in that circuit is a prime number.
  Here, a circuit is a closed trail that may pass through the same vertex more than once (but must not use the same edge more than once).

Constraints

• N is an integer between 1 and 2.5 \times 10^5, inclusive.

Sample Input 1

3

Sample Output 1

4

There are four such graphs G:

• The graph with edges (1, 2) and (1, 3)
• The graph with edges (1, 2) and (2, 3)
• The graph with edges (1, 3) and (2, 3)
• The graph with edges (1, 2), (1, 3), and (2, 3)

Sample Input 2

2025

Sample Output 2

879839321

Sample Input 3

61261

Sample Output 3

202537766