Problem Statement

You are given three integers A,B,C. Determine whether it is possible to divide these three integers into two or more groups so that these groups have equal sums.

Constraints

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

Sample Input 1

3 8 5

Sample Output 1

Yes

For example, by dividing into two groups (3,5) and (8), each group can have the sum 8.

Sample Input 2

2 2 2

Sample Output 2

Yes

By dividing into three groups (2),(2),(2), each group can have the sum 2.

Sample Input 3

1 2 4

Sample Output 3

No

No matter how you divide them into two or more groups, it is not possible to make the sums equal.

Problem Statement

There is 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.

If S_{i,j} is #, the cell (i,j) is impassable; if it is ., the cell is passable and contains no house; if it is @, the cell is passable and contains a house.

Initially, Santa Claus is in cell (X,Y). He will act according to the string T as follows.

• Let |T| be the length of the string T. For i=1,2,\ldots,|T|, he moves as follows.
  • Let (x,y) be the cell he is currently in.
    • If T_i is U and cell (x-1,y) is passable, move to cell (x-1,y).
    • If T_i is D and cell (x+1,y) is passable, move to cell (x+1,y).
    • If T_i is L and cell (x,y-1) is passable, move to cell (x,y-1).
    • If T_i is R and cell (x,y+1) is passable, move to cell (x,y+1).
    • Otherwise, stay in cell (x,y).

Find the cell where he is after completing all actions, and the number of distinct houses that he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 3 \leq H,W \leq 100
• 1 \leq X \leq H
• 1 \leq Y \leq W
• All given numbers are integers.
• Each S_{i,j} is one of #, ., @.
• S_{i,1} and S_{i,W} are # for every 1 \leq i \leq H.
• S_{1,j} and S_{H,j} are # for every 1 \leq j \leq W.
• S_{X,Y}= .
• T is a string of length at least 1 and at most 10^4, consisting of U, D, L, R.

Sample Input 1

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

Sample Output 1

2 3 1

Santa Claus behaves as follows:

• T_1= L, so he moves from (3,4) to (3,3). A house is passed.
• T_2= L, so he moves from (3,3) to (3,2).
• T_3= L, but cell (3,1) is impassable, so he stays at (3,2).
• T_4= D, so he moves from (3,2) to (4,2).
• T_5= R, so he moves from (4,2) to (4,3).
• T_6= U, so he moves from (4,3) to (3,3). A house is passed, but it has already been passed.
• T_7= U, so he moves from (3,3) to (2,3).

The number of houses he passed or arrived during his actions is 1.

Sample Input 2

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

Sample Output 2

3 11 11

Sample Input 3

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

Sample Output 3

4 14 1

Problem Statement

There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.

You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:

• The chosen buildings all have the same height.
• The chosen buildings are arranged at equal intervals.

What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.

Constraints

• 1 \leq N \leq 3000
• 1 \leq H_i \leq 3000
• All input values are integers.

Sample Input 1

8
5 7 5 7 7 5 7 7

Sample Output 1

3

Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.

Sample Input 2

10
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

1

Choosing just one building is considered to satisfy the conditions.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

Sample Output 3

3

Problem Statement

There are N houses at points (X_1,Y_1),\ldots,(X_N,Y_N) on a two-dimensional plane.

Initially, Santa Claus is at point (S_x,S_y). He will act according to the sequence (D_1,C_1),\ldots,(D_M,C_M) as follows:

• For i=1,2,\ldots,M in order, he moves as follows:
  • Let (x,y) be the point where he currently is.
    • If D_i is U, move in a straight line from (x,y) to (x,y+C_i).
    • If D_i is D, move in a straight line from (x,y) to (x,y-C_i).
    • If D_i is L, move in a straight line from (x,y) to (x-C_i,y).
    • If D_i is R, move in a straight line from (x,y) to (x+C_i,y).

Find the point where he is after completing all actions, and the number of distinct houses he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• -10^9 \leq X_i,Y_i \leq 10^9
• The pairs (X_i,Y_i) are distinct.
• -10^9 \leq S_x,S_y \leq 10^9
• There is no house at (S_x,S_y).
• Each D_i is one of U, D, L, R.
• 1 \leq C_i \leq 10^9
• All input numbers are integers.

Sample Input 1

3 4 3 2
2 2
3 3
2 1
L 2
D 1
R 1
U 2

Sample Output 1

2 3 2

Santa Claus behaves as follows:

• D_1= L, so he moves from (3,2) to (3-2,2) in a straight line. During this, he passes through the house at (2,2).
• D_2= D, so he moves from (1,2) to (1,2-1) in a straight line.
• D_3= R, so he moves from (1,1) to (1+1,1) in a straight line. During this, he passes through the house at (2,1).
• D_4= U, so he moves from (2,1) to (2,1+2) in a straight line. During this, he passes through the house at (2,2), but it has already been passed.

The number of houses he passed or arrived during his actions is 2.

Sample Input 2

1 3 0 0
1 1
R 1000000000
R 1000000000
R 1000000000

Sample Output 2

3000000000 0 0

Be careful with overflow.

Problem Statement

A "Snowflake Tree" is defined as a tree that can be generated by the following procedure:

1. Choose positive integers x,y.
2. Prepare one vertex.
3. Prepare x more vertices, and connect each of them to the vertex prepared in step 2.
4. For each of the x vertices prepared in step 3, attach y leaves to it.

The figure below shows a Snowflake Tree with x=4,y=2. The vertices prepared in steps 2, 3, 4 are shown in red, blue, and green, respectively.

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (i=1,2,\dots,N-1) connects vertices u_i and v_i.

Consider deleting zero or more vertices of T and the edges adjacent to them so that the remaining graph becomes a single Snowflake Tree. Find the minimum number of vertices that must be deleted. Under the constraints of this problem, it is always possible to transform T into a Snowflake Tree.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq u_i < v_i \leq N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

8
1 3
2 3
3 4
4 5
5 6
5 7
4 8

Sample Output 1

1

By deleting vertex 8, the given tree can be transformed into a Snowflake Tree with x=2,y=2.

Sample Input 2

3
1 2
2 3

Sample Output 2

0

The given tree is already a Snowflake Tree with x=1,y=1.

Sample Input 3

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

Sample Output 3

3

Problem Statement

There are N buildings numbered 1 to N on a number line.
Building i is at coordinate X_i and has height H_i. The size in directions other than height is negligible.

From a point P with coordinate x and height h, building i is considered visible if there exists a point Q on building i such that the line segment PQ does not intersect with any other building.

Find the maximum height at coordinate 0 from which it is not possible to see all buildings. Height must be non-negative; if it is possible to see all buildings at height 0 at coordinate 0, report -1 instead.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X_1 < \dots < X_N \leq 10^9
• 1 \leq H_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 2
5 4
7 5

Sample Output 1

1.500000000000000000

From coordinate 0 and height 1.5, building 3 cannot be seen. If the height is even slightly greater than 1.5, all buildings including building 3 can be seen. Thus, the answer is 1.5.

Sample Input 2

2
1 1
2 100

Sample Output 2

-1

Note that -1.000 or similar outputs would be considered incorrect.

Sample Input 3

3
1 1
2 2
3 3

Sample Output 3

0.000000000000000000

Sample Input 4

4
10 10
17 5
20 100
27 270

Sample Output 4

17.142857142857142350

Problem Statement

For a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), define integers L(P) and R(P) as follows:

• Consider N buildings arranged in a row from left to right, with the height of the i-th building from the left being P_i. Then L(P) is the number of buildings visible when viewed from the left, and R(P) is the number of buildings visible when viewed from the right.
  More formally, L(P) is the count of indices i such that P_j < P_i for all j < i, and R(P) is the count of indices i such that P_i > P_j for all j > i.

You are given integers N and K. Find, modulo 998244353, the count of all permutations P of (1,2,\dots,N) such that L(P)-R(P)=K.

Constraints

• 1 \leq N \leq 2 \times 10^5
• |K| \leq N-1
• All input values are integers.

Sample Input 1

3 -1

Sample Output 1

1

• P=(1,2,3): L(P)-R(P)=3-1=2.
• P=(1,3,2): L(P)-R(P)=2-2=0.
• P=(2,1,3): L(P)-R(P)=2-1=1.
• P=(2,3,1): L(P)-R(P)=2-2=0.
• P=(3,1,2): L(P)-R(P)=1-2=-1.
• P=(3,2,1): L(P)-R(P)=1-3=-2.

Therefore, the number of permutations P with L(P)-R(P)=-1 is 1.

Sample Input 2

1 0

Sample Output 2

1

Sample Input 3

2024 385

Sample Output 3

576300012

Print the count modulo 998244353.