Problem Statement

You are given a string S consisting of lowercase English letters and digits.
S is guaranteed to end with 2023.
Change the last character of S to 4 and print the modified string.

Constraints

• S is a string of length between 4 and 100, inclusive, consisting of lowercase English letters and digits.
• S ends with 2023.

Sample Input 1

hello2023

Sample Output 1

hello2024

Changing the last character of hello2023 to 4 yields hello2024.

Sample Input 2

worldtourfinals2023

Sample Output 2

worldtourfinals2024

Sample Input 3

2023

Sample Output 3

2024

S is guaranteed to end with 2023, possibly being 2023 itself.

Sample Input 4

20232023

Sample Output 4

20232024

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

Constraints

• 0 \leq N \leq 21
• N is an integer.

Sample Input 1

3

Sample Output 1

0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 3 0
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 2 0
2 0 0
2 0 1
2 1 0
3 0 0

Sample Input 2

4

Sample Output 2

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

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

• 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
• 2 p: Find the coordinates of part p.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 2\times 10^5
• For the first type of query, C is one of R, L, U, and D.
• For the second type of query, 1\leq p \leq N.
• All numerical input values are integers.

Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

Problem Statement

There is a grid with N rows and N columns, where N is an odd number at most 45.

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

In this grid, you will place Takahashi and a dragon consisting of N^2-1 parts numbered 1 to N^2-1 in such a way that satisfies the following conditions:

• Takahashi must be placed at the center of the grid, that is, in cell (\frac{N+1}{2},\frac{N+1}{2}).
• Except for the cell where Takahashi is, exactly one dragon part must be placed in each cell.
• For every integer x satisfying 2 \leq x \leq N^2-1, the dragon part x must be placed in a cell adjacent by an edge to the cell containing part x-1.
  • Cells (i,j) and (k,l) are said to be adjacent by an edge if and only if |i-k|+|j-l|=1.

Print one way to arrange the parts to satisfy the conditions. It is guaranteed that there is at least one arrangement that satisfies the conditions.

Constraints

• 3 \leq N \leq 45
• N is odd.

Sample Input 1

5

Sample Output 1

1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9

The following output also satisfies all the conditions and is correct.

9 10 11 14 15
8 7 12 13 16
5 6 T 18 17
4 3 24 19 20 
1 2 23 22 21

On the other hand, the following outputs are incorrect for the reasons given.

Takahashi is not at the center.

1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 T

The cells containing parts 23 and 24 are not adjacent by an edge.

1 2 3 4 5
10 9 8 7 6
11 12 24 22 23
14 13 T 21 20
15 16 17 18 19

Problem Statement

There is a connected undirected graph with N vertices and M edges, where the i-th edge connects vertex U_i and vertex V_i bidirectionally.
Each vertex has an integer written on it, with integer A_v written on vertex v.

For a simple path from vertex 1 to vertex N (a path that does not pass through the same vertex multiple times), the score is determined as follows:

• Let S be the sequence of integers written on the vertices along the path, listed in the order they are visited.
• If S is not non-decreasing, the score of that path is 0.
• Otherwise, the score is the number of distinct integers in S.

Find the path from vertex 1 to vertex N with the highest score among all simple paths and print that score.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• N-1 \le M \le 2 \times 10^5
• 1 \le A_i \le 2 \times 10^5
• The graph is connected.
• 1 \le U_i < V_i \le N
• (U_i,V_i) \neq (U_j,V_j) if i \neq j.

Sample Input 1

5 6
10 20 30 40 50
1 2
1 3
2 5
3 4
3 5
4 5

Sample Output 1

4

The path 1 \rightarrow 3 \rightarrow 4 \rightarrow 5 has S=(10,30,40,50) for a score of 4, which is the maximum.

Sample Input 2

4 5
1 10 11 4
1 2
1 3
2 3
2 4
3 4

Sample Output 2

0

There is no simple path from vertex 1 to vertex N such that S is non-decreasing. In this case, the maximum score is 0.

Sample Input 3

10 12
1 2 3 3 4 4 4 6 5 7
1 3
2 9
3 4
5 6
1 2
8 9
4 5
8 10
7 10
4 6
2 8
6 7

Sample Output 3

5

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.

Problem Statement

You are given N integers A_1,\ldots,A_N and a prime number P. Find the number of pairs of integers (i,j) that satisfy both of the following conditions:

• 1 \leq i,j \leq N;
• There is a positive integer k such that A_i^k \equiv A_j \mod P.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i < P
• 2 \leq P \leq 10^{13}
• P is prime.
• All input values are integers.

Sample Input 1

3 13
2 3 5

Sample Output 1

5

Five pairs satisfy the conditions: (1,1),(1,2),(1,3),(2,2),(3,3).

For example, for the pair (1,3), if we take k=9, then A_1^9 = 512 \equiv 5 = A_3 \mod 13.

Sample Input 2

5 2
1 1 1 1 1

Sample Output 2

25

Sample Input 3

10 9999999999971
141592653589 793238462643 383279502884 197169399375 105820974944 592307816406 286208998628 34825342117 67982148086 513282306647

Sample Output 3

63