Problem Statement

Takahashi will have N penalty kicks in a soccer match.

For the i-th penalty kick, he will fail if i is a multiple of 3, and succeed otherwise.

Print the results of his penalty kicks.

Constraints

• 1 \leq N \leq 100
• All inputs are integers.

Sample Input 1

7

Sample Output 1

ooxooxo

Takahashi fails the third and sixth penalty kicks, so the third and sixth characters will be x.

Sample Input 2

9

Sample Output 2

ooxooxoox

Problem Statement

Takahashi had his N-th birthday, when he was T centimeters tall.
Additionally, we know the following facts:

• In each year between Takahashi's birth (0-th birthday) and his X-th birthday, his height increased by D centimeters. More formally, for each i = 1, 2, \ldots, X, his height increased by D centimeters between his (i-1)-th birthday and his i-th birthday.
• Between Takahashi's X-th birthday and his N-th birthday, his height did not change.

Find Takahashi's height on his M-th birthday, in centimeters.

Constraints

• 0 \leq M \lt N \leq 100
• 1 \leq X \leq N
• 1 \leq T \leq 200
• 1 \leq D \leq 100
• Takahashi was at least 1 centimeter tall at his birth.
• All values in input are integers.

Sample Input 1

38 20 17 168 3

Sample Output 1

168

In this sample, Takahashi was 168 centimeters tall on his 38-th birthday. Also, his height did not change between his 17-th birthday and 38-th birthday.
From these facts, we find that he was 168 centimeters tall on his 20-th birthday, so the answer is 168.

Sample Input 2

1 0 1 3 2

Sample Output 2

1

In this sample, Takahashi was 1 centimeter tall on his 0(=M)-th birthday and 3(=T) centimeters tall on his 1(=N)-st birthday.

Sample Input 3

100 10 100 180 1

Sample Output 3

90

Problem Statement

You are given a string S consisting of uppercase English letters and digits. Determine whether S satisfies the following condition.

• S is a concatenation of the following characters and string in the order listed.
  • An uppercase English letter
  • A string of length 6 that is a decimal representation of an integer between 100000 and 999999, inclusive
  • An uppercase English letter

Constraints

• S consists of uppercase English letters and digits.
• The length of S is between 1 and 10, inclusive.

Sample Input 1

Q142857Z

Sample Output 1

Yes

S is a concatenation of Q, 142857, and Z in this order.
Q and Z are uppercase English letters, and 142857 is a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S satisfies the condition.

Sample Input 2

AB912278C

Sample Output 2

No

AB is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 3

X900000

Sample Output 3

No

The last character of S is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 4

K012345K

Sample Output 4

No

012345 is not a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S does not satisfy the condition.

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertex U_i and Vertex V_i.

Find the number of tuples of integers a, b, c that satisfy all of the following conditions:

• 1 \leq a \lt b \lt c \leq N
• There is an edge connecting Vertex a and Vertex b.
• There is an edge connecting Vertex b and Vertex c.
• There is an edge connecting Vertex c and Vertex a.

Constraints

• 3 \leq N \leq 100
• 1 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) satisfy the conditions.

Sample Input 2

3 1
1 2

Sample Output 2

0

Sample Input 3

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

Sample Output 3

4

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

• Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
• Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

• 1 \leq N \leq 10
• 1 \leq X \leq 5
• 1 \leq Y \leq 5
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

12

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

• First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
  • After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
• Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
  • After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
• He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

0

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

2

The given graph contains the following two connected components:

• a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
• a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

5

Sample Input 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

1

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the number of triples of integers (i,j,k) that satisfy all of the following:

• 1 \le i,j,k \le N
• A_i : A_j : A_k = 7:5:3
• \min(i,j,k) = j or \max(i,j,k) = j.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

10
3 10 7 10 7 6 7 6 5 14

Sample Output 1

7

The seven triples of integers (i,j,k) that satisfy the conditions are:

• (3,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (5,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (7,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (10,2,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,2,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.

Sample Input 2

6
210 210 210 210 210 210

Sample Output 2

0

Sample Input 3

21
49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30

Sample Output 3

34

Problem Statement

Takahashi and Aoki will play a game of sugoroku.
Takahashi starts at point A, and Aoki starts at point B. They will take turns throwing dice.
Takahashi's die shows 1, 2, \ldots, P with equal probability, and Aoki's shows 1, 2, \ldots, Q with equal probability.
When a player at point x throws his die and it shows i, he goes to point \min(x + i, N).
The first player to reach point N wins the game.
Find the probability that Takahashi wins if he goes first, modulo 998244353.

Constraints

• 2 \leq N \leq 100
• 1 \leq A, B < N
• 1 \leq P, Q \leq 10
• All values in the input are integers.

Sample Input 1

4 2 3 3 2

Sample Output 1

665496236

If Takahashi's die shows 2 or 3 in his first turn, he goes to point 4 and wins.
If Takahashi's die shows 1 in his first turn, he goes to point 3, and Aoki will always go to point 4 in the next turn and win.
Thus, Takahashi wins with the probability \frac{2}{3}.

Sample Input 2

6 4 2 1 1

Sample Output 2

1

The dice always show 1.
Here, Takahashi goes to point 5, Aoki goes to point 3, and Takahashi goes to point 6, so Takahashi always wins.

Sample Input 3

100 1 1 10 10

Sample Output 3

264077814

Problem Statement

AtCoder Inc.'s online shop currently handles N products, and the stock of product i is A_i units remaining.

Process the following Q orders in order. The i-th order is as follows:

• Buy k_i units each of products l_i,l_i+1,\dots,r_i. For products with fewer than k_i units, buy all available units. Report the total number of products bought in this order.

Note that for i<Q, the stock of products bought in the i-th order is reduced before proceeding to the (i+1)-th order.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^{15}
• 1 \le Q \le 3 \times 10^5
• 1 \le l_i \le r_i \le N
• 1 \le k_i \le 10^9

Sample Input 1

6
2 6 4 5 7 5
5
1 6 1
3 5 4
4 4 1
2 5 1
1 6 100

Sample Output 1

6
11
0
2
10

This input contains 5 orders.

• Initially, the stocks of the products are (from product 1 onward) 2,6,4,5,7,5 units.
• The first order is l_1 = 1, r_1 = 6, k_1 = 1.
  • In this order, 1,1,1,1,1,1 units of the products are bought, for a total of 6 units.
  • After this, the stocks of the products become 1,5,3,4,6,4 units.
• The second order is l_2 = 3, r_2 = 5, k_2 = 4.
  • In this order, 0,0,3,4,4,0 units of the products are bought, for a total of 11 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The third order is l_3 = 4, r_3 = 4, k_3 = 1.
  • In this order, 0,0,0,0,0,0 units of the products are bought, for a total of 0 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The fourth order is l_4 = 2, r_4 = 5, k_4 = 1.
  • In this order, 0,1,0,0,1,0 units of the products are bought, for a total of 2 units.
  • After this, the stocks of the products become 1,4,0,0,1,4 units.
• The fifth order is l_5 = 1, r_5 = 6, k_5 = 100.
  • In this order, 1,4,0,0,1,4 units of the products are bought, for a total of 10 units.
  • After this, the stocks of the products become 0,0,0,0,0,0 units.