Problem Statement

You are given an odd-length string S consisting of lowercase English letters.

Print the central character of S.

Constraints

• S is an odd-length string consisting of lowercase English letters.
• The length of S is between 1 and 99 (inclusive).

Sample Input 1

atcoder

Sample Output 1

o

The central character of atcoder is o.

Sample Input 2

a

Sample Output 2

a

Problem Statement

You are given an integer N between -10^{18} and 10^{18} (inclusive).

Find an integer x between 0 and 998244353 - 1 (inclusive) that satisfies the following condition. It can be proved that such an integer is unique.

• N-x is a multiple of 998244353.

Constraints

• N is an integer between -10^{18} and 10^{18} (inclusive).

Sample Input 1

998244354

Sample Output 1

1

998244354-1 = 998244353 is a multiple of 998244353, so the condition is satisfied.

Sample Input 2

-9982443534

Sample Output 2

998244349

-9982443534-998244349= -10980687883 is a multiple of 998244353, so the condition is satisfied.

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
• 0 \leq X_i \leq 4
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinate 0 to catch the first Snuke at time 1.
• Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323

Problem Statement

Let us play a game using a die. The game consists of at most N turns, each of which goes as follows.

• Throw a 6-sided die that shows 1,\ldots,6 with equal probability, and let X be the number shown (each throw is independent of the others).
• If it is the N-th turn now, your score is X, and the game ends.
• Otherwise, choose whether to continue or end the game.
  • If you end the game, your score is X, and there is no more turn.

Find the expected value of your score when you play the game to maximize this expected value.

Constraints

• 1 \leq N \leq 100

Sample Input 1

1

Sample Output 1

3.5000000000

Sample Input 2

2

Sample Output 2

4.2500000000

Sample Input 3

10

Sample Output 3

5.6502176688

Problem Statement

You are given a connected simple undirected graph G with N vertices numbered 1 to N and N edges. The i-th edge connects Vertex u_i and Vertex v_i bidirectionally.

Answer the following Q queries.

• Determine whether there is a unique simple path from Vertex x_i to Vertex y_i (a simple path is a path without repetition of vertices).

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i\leq N
• (u_i,v_i) \neq (u_j,v_j) if i \neq j.
• G is a connected simple undirected graph with N vertices and N edges.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i < y_i\leq N
• All values in input are integers.

Sample Input 1

5
1 2
2 3
1 3
1 4
2 5
3
1 2
1 4
1 5

Sample Output 1

No
Yes
No

The simple paths from Vertex 1 to 2 are (1,2) and (1,3,2), which are not unique, so the answer to the first query is No.

The simple path from Vertex 1 to 4 is (1,4), which is unique, so the answer to the second query is Yes.

The simple paths from Vertex 1 to 5 are (1,2,5) and (1,3,2,5), which are not unique, so the answer to the third query is No.

Sample Input 2

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

Sample Output 2

Yes
No
Yes
Yes
No
No
Yes
No
Yes
No

Problem Statement

You are given integers R, G, B, and K. How many strings S consisting of R, G, and B satisfy all of the conditions below? Find the count modulo 998244353.

• The number of occurrences of R, G, and B in S are R, G, and B, respectively.
• The number of occurrences of RG as (contiguous) substrings in S is K.

Constraints

• 1 \leq R,G,B\leq 10^6
• 0 \leq K \leq \mathrm{min}(R,G)
• All values in input are integers.

Sample Input 1

2 1 1 1

Sample Output 1

6

The following six strings satisfy the conditions.

• RRGB
• RGRB
• RGBR
• RBRG
• BRRG
• BRGR

Sample Input 2

1000000 1000000 1000000 1000000

Sample Output 2

80957240

Find the count modulo 998244353.

Problem Statement

Takahashi is trying to catch many Snuke.

There are some pits in a two-dimensional coordinate plane, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinates (X_i,Y_i) at time T_i, and its size is A_i.

Takahashi is at coordinates (0,0) at time 0 and can do the following two kinds of moves.

• Move at a speed of at most 1 in the x-direction (positive or negative).
• Move at a speed of at most 1 in the positive y-direction.

Moving in the negative y-direction is not allowed.

He can catch a Snuke appearing from a pit if and only if he is at the coordinates of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T_i \leq 10^9
• 0 \leq X_i,Y_i \leq 10^9
• 1 \leq A_i \leq 10^9
• The triples (T_i,X_i,Y_i) are distinct.
• All values in input are integers.

Sample Input 1

3
1 0 0 100
3 2 1 10
5 3 1 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinates (0,0) to catch the first Snuke at time 1.
• Go to coordinates (3,1) to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

2
100 0 1 1
200 1 0 10

Sample Output 2

10

Moving in the negative y-direction is not allowed, so he cannot catch the first Snuke and then the second.

Sample Input 3

10
797829355 595605750 185676190 353195922
913575467 388876063 395940406 533206504
810900084 201398242 159760440 87027328
889089200 220046203 85488350 325976483
277429832 161055688 73308100 940778720
927999455 429014248 477195779 174616807
673419335 415891345 81019893 286986530
989248231 147792453 417536200 219371588
909664305 22150727 414107912 317441890
988670052 140275628 468278658 67181740

Sample Output 3

1553741733