Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

• 1 \leq V,A,B,C \leq 10^5
• All values in input are integers.

Sample Input 1

25 10 11 12

Sample Output 1

T

Now, they have 25 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 15.
• Next, Takahashi's mother uses 11 milliliters, leaving 4.
• Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

F

Now, they have 30 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 20.
• Next, Takahashi's mother uses 10 milliliters, leaving 10.
• Then, Takahashi uses 10 milliliters, leaving 0.
• Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

M

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9
• 0 \leq Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All X_i and Y_i are integers.
• S is a string of length N consisting of L and R.

Sample Input 1

3
2 3
1 1
4 1
RRL

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

2
1 1
2 1
RR

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Sample Output 3

Yes

Problem Statement

There is a perfect binary tree with 2^{10^{100}}-1 vertices, numbered 1,2,...,2^{10^{100}}-1.
Vertex 1 is the root. For each 1\leq i < 2^{10^{100}-1}, Vertex i has two children: Vertex 2i to the left and Vertex 2i+1 to the right.

Takahashi starts at Vertex X and performs N moves, represented by a string S. The i-th move is as follows.

• If the i-th character of S is U, go to the parent of the vertex he is on now.
• If the i-th character of S is L, go to the left child of the vertex he is on now.
• If the i-th character of S is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after N moves. In the given cases, it is guaranteed that the answer is at most 10^{18}.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq X \leq 10^{18}
• N and X are integers.
• S has a length of N and consists of U, L, and R.
• When Takahashi is at the root, he never attempts to go to the parent.
• When Takahashi is at a leaf, he never attempts to go to a child.
• The index of the vertex Takahashi is on after N moves is at most 10^{18}.

Sample Input 1

3 2
URL

Sample Output 1

6

The perfect binary tree has the following structure.

In the three moves, Takahashi goes 2 \to 1 \to 3 \to 6.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds 10^{18}.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges.
Edge i connects Vertex A_i and Vertex B_i, and has a length of C_i.

Let us delete some number of edges while satisfying the conditions below. Find the maximum number of edges that can be deleted.

• The graph is still connected after the deletion.
• For every pair of vertices (s, t), the distance between s and t remains the same before and after the deletion.

Notes

A simple connected undirected graph is a graph that is simple and connected and has undirected edges.
A graph is simple when it has no self-loops and no multi-edges.
A graph is connected when, for every pair of two vertices s and t, t is reachable from s by traversing edges.
The distance between Vertex s and Vertex t is the length of a shortest path between s and t.

Constraints

• 2 \leq N \leq 300
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i \lt B_i \leq N
• 1 \leq C_i \leq 10^9
• (A_i, B_i) \neq (A_j, B_j) if i \neq j.
• The given graph is connected.
• All values in input are integers.

Sample Input 1

3 3
1 2 2
2 3 3
1 3 6

Sample Output 1

1

The distance between each pair of vertices before the deletion is as follows.

• The distance between Vertex 1 and Vertex 2 is 2.
• The distance between Vertex 1 and Vertex 3 is 5.
• The distance between Vertex 2 and Vertex 3 is 3.

Deleting Edge 3 does not affect the distance between any pair of vertices. It is impossible to delete two or more edges while satisfying the condition, so the answer is 1.

Sample Input 2

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

Sample Output 2

0

No edge can be deleted.

Sample Input 3

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

Sample Output 3

5

Problem Statement

Takahashi is participating in a lottery.

Each time he takes a draw, he gets one of the N prizes available. Prize i is awarded with probability \frac{W_i}{\sum_{j=1}^{N}W_j}. The results of the draws are independent of each other.

What is the probability that he gets exactly M different prizes from K draws? Find it modulo 998244353.

Note

To print a rational number, start by representing it as a fraction \frac{y}{x}. Here, x and y should be integers, and x should not be divisible by 998244353 (under the Constraints of this problem, such a representation is always possible). Then, print the only integer z between 0 and 998244352 (inclusive) such that xz\equiv y \pmod{998244353}.

Constraints

• 1 \leq K \leq 50
• 1 \leq M \leq N \leq 50
• 0 < W_i
• 0 < W_1 + \ldots + W_N < 998244353
• All values in input are integers.

Sample Input 1

2 1 2
2
1

Sample Output 1

221832079

Each draw awards Prize 1 with probability \frac{2}{3} and Prize 2 with probability \frac{1}{3}.

He gets Prize 1 at both of the two draws with probability \frac{4}{9}, and Prize 2 at both draws with probability \frac{1}{9}, so the sought probability is \frac{5}{9}.

The modulo 998244353 representation of this value, according to Note, is 221832079.

Sample Input 2

3 3 2
1
1
1

Sample Output 2

0

It is impossible to get three different prizes from two draws, so the sought probability is 0.

Sample Input 3

3 3 10
499122176
499122175
1

Sample Output 3

335346748

Sample Input 4

10 8 15
1
1
1
1
1
1
1
1
1
1

Sample Output 4

755239064

Problem Statement

We have a sequence of length 1: A=(X). Let us perform the following operation on this sequence 10^{100} times.

Operation: Let Y be the element at the end of A. Choose an integer between 1 and \sqrt{Y} (inclusive), and append it to the end of A.

How many sequences are there that can result from 10^{100} operations?

You will be given T test cases to solve.

It can be proved that the answer is less than 2^{63} under the Constraints.

Constraints

• 1 \leq T \leq 20
• 1 \leq X \leq 9\times 10^{18}
• All values in input are integers.

Sample Input 1

4
16
1
123456789012
1000000000000000000

Sample Output 1

5
1
4555793983
23561347048791096

In the first case, the following five sequences can result from the operations.

• (16,4,2,1,1,1,\ldots)
• (16,4,1,1,1,1,\ldots)
• (16,3,1,1,1,1,\ldots)
• (16,2,1,1,1,1,\ldots)
• (16,1,1,1,1,1,\ldots)

Problem Statement

There is a grid with H \times W squares. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
C_{i,j} represents the state of each square. Each square is in one of the following four states.

• S: The starting point. The grid has exactly one starting point.
• G: The goal. The grid has exactly one goal.
• .: A constructible square, where a wall can be built.
• O: An unconstructible square, where a wall cannot be built.

Aoki intends to start at the starting point and get to the goal. When he is at (i,j), he can go to (i+1,j), (i,j+1), (i-1,j), or (i,j-1). It is not allowed to exit the grid or enter a square with a wall.

Takahashi decides to build a wall on one or more constructible squares of his choice before Aoki starts so that there is no way for Aoki to reach the goal. Here, the starting point and the goal cannot be chosen.

Is it possible for Takahashi to build walls to prevent Aoki from reaching the goal? If it is possible, also compute the two values below:

• the minimum number n of walls needed to prevent Aoki from reaching the goal, and
• the number of ways modulo 998244353, r, to achieve that minimum number of walls.

Constraints

• 2 \leq H \leq 100
• 2 \leq W \leq 100
• C_{i,j} is S, G, ., or O.
• Each of S and G appears exactly once in C_{i,j}.

Sample Input 1

4 3
S..
O..
..O
..G

Sample Output 1

Yes
3 6

Let # represent a square to build a wall on. The six ways to achieve the minimum number of walls are as follows:

S#.  S.#  S..  S..  S..  S..
O#.  O#.  O##  O.#  O.#  O.#
#.O  #.O  #.O  ##O  .#O  .#O
..G  ..G  ..G  ..G  #.G  .#G

Sample Input 2

3 2
.G
.O
.S

Sample Output 2

No

Regardless of how Takahashi builds walls, Aoki can always reach the goal.

Sample Input 3

2 2
S.
.G

Sample Output 3

Yes
2 1

Sample Input 4

10 10
OOO...OOO.
.....OOO.O
OOO.OO.OOO
OOO..O..S.
....O.O.O.
.OO.O.OOOO
..OOOG.O.O
.O.O..OOOO
.O.O.OO...
...O..O..O

Sample Output 4

Yes
10 12