Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

• S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Sample Input 1

tourist

Sample Output 1

3858

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

3481

At the start of this contest, the rating of semiexp in the algorithm category is 3481.

Problem Statement

You are given a positive integer N. Print a string of length (N+1), s_0s_1\ldots s_N, defined as follows.

For each i = 0, 1, 2, \ldots, N,

• if there is a divisor j of N that is between 1 and 9, inclusive, and i is a multiple of N/j, then s_i is the digit corresponding to the smallest such j (s_i will thus be one of 1, 2, ..., 9);
• if no such j exists, then s_i is -.

Constraints

• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

12

Sample Output 1

1-643-2-346-1

We will explain how to determine s_i for some i.

• For i = 0, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 1, 2, 3, 4, 6. The smallest of these is 1, so s_0 = 1.

• For i = 4, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 3, 6. The smallest of these is 3, so s_4 = 3.

• For i = 11, there are no divisors j of N between 1 and 9 such that i is a multiple of N/j, so s_{11} = -.

Sample Input 2

7

Sample Output 2

17777771

Sample Input 3

1

Sample Output 3

11

Problem Statement

There is a 3\times3 grid with numbers between 1 and 9, inclusive, written in each square. The square at the i-th row from the top and j-th column from the left (1\leq i\leq3,1\leq j\leq3) contains the number c _ {i,j}.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that c _ {i,j} satisfies all of the following conditions.

• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

Constraints

• c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Sample Input 1

3 1 9
2 5 6
2 7 1

Sample Output 1

0.666666666666666666666666666667

For example, if Takahashi sees c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 in this order, he will get disappointed.

On the other hand, if Takahashi sees c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} in this order, he will see all numbers without getting disappointed.

The probability that Takahashi sees all the numbers without getting disappointed is \dfrac 23. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}, so outputs such as 0.666666657 and 0.666666676 would also be accepted.

Sample Input 2

7 7 6
8 6 8
7 7 6

Sample Output 2

0.004982363315696649029982363316

Sample Input 3

3 6 7
1 9 7
5 7 5

Sample Output 3

0.4

Problem Statement

Takahashi is displaying a sentence with N words in a window. All words have the same height, and the width of the i-th word (1\leq i\leq N) is L _ i.

The words are displayed in the window separated by a space of width 1. More precisely, when the sentence is displayed in a window of width W, the following conditions are satisfied.

• The sentence is divided into several lines.
• The first word is displayed at the beginning of the top line.
• The i-th word (2\leq i\leq N) is displayed either with a gap of 1 after the (i-1)-th word, or at the beginning of the line below the line containing the (i-1)-th word. It will not be displayed anywhere else.
• The width of each line does not exceed W. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into M or fewer lines. Find the minimum possible width of the window.

Constraints

• 1\leq M\leq N\leq2\times10 ^ 5
• 1\leq L _ i\leq10^9\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

26

When the width of the window is 26, you can fit the given sentence into three lines as follows.

You cannot fit the given sentence into three lines when the width of the window is 25 or less, so print 26.

Note that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.

Sample Input 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000009

Note that the answer may not fit into a 32\operatorname{bit} integer.

Sample Input 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

Sample Output 3

189

Problem Statement

Takahashi is initially at his house and is about to visit Aoki's house.

There are N bus stops numbered 1 to N between the two houses, and Takahashi can move between them in the following ways:

• He can walk from his house to bus stop 1 in X units of time.
• For each i = 1, 2, \ldots, N-1, a bus departs from bus stop i at each time that is a multiple of P_i, and by taking this bus, he can get to bus stop (i+1) in T_i units of time. Here, the constraints guarantee that 1 \leq P_i \leq 8.
• Takahashi can walk from bus stop N to Aoki's house in Y units of time.

For each i = 1, 2, \ldots, Q, process the following query.

Find the earliest time that Takahashi can arrive at Aoki's house when he leaves his house at time q_i.

Note that if he arrives at a bus stop exactly at the departure time of a bus, he can take that bus.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq X, Y \leq 10^9
• 1 \leq P_i \leq 8
• 1 \leq T_i \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq q_i \leq 10^9
• All input values are integers.

Sample Input 1

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

Sample Output 1

34
22
710511052
136397548
763027402
644706946
447672250

For the first query, Takahashi can move as follows to arrive at Aoki's house at time 34.

• Leave his house at time 13.
• Walk from his house and arrive at bus stop 1 at time 15.
• Take the bus departing from bus stop 1 at time 15 and arrive at bus stop 2 at time 19.
• Take the bus departing from bus stop 2 at time 24 and arrive at bus stop 3 at time 30.
• Take the bus departing from bus stop 3 at time 30 and arrive at bus stop 4 at time 31.
• Walk from bus stop 4 and arrive at Aoki's house at time 34.

For the second query, Takahashi can move as follows and arrive at Aoki's house at time 22.

• Leave his house at time 0.
• Walk from his house and arrive at bus stop 1 at time 2.
• Take the bus departing from bus stop 1 at time 5 and arrive at bus stop 2 at time 9.
• Take the bus departing from bus stop 2 at time 12 and arrive at bus stop 3 at time 18.
• Take the bus departing from bus stop 3 at time 18 and arrive at bus stop 4 at time 19.
• Walk from bus stop 4 and arrive at Aoki's house at time 22.

Problem Statement

There is a tree with N vertices. The 1-st vertex is the root, and the parent of the i-th vertex (2\leq i\leq N) is p _ i\ (1\leq p _ i\lt i).

Each non-root vertex has an enemy or a medicine on it. Takahashi wants to defeat all the enemies. Initially, his strength is 1, and he is at vertex 1. For i=2,\ldots,N, the information of the i-th vertex is represented by a triple of integers (t _ i,s _ i,g _ i) as follows.

• If t _ i=1, there is an enemy at the i-th vertex. When Takahashi visits this vertex for the first time, if his strength is less than s _ i, Takahashi is defeated by the enemy and loses, after which he cannot move to other vertices. Otherwise, he defeats the enemy, and his strength increases by g _ i.
• If t _ i=2, there is a medicine at the i-th vertex. When Takahashi visits this vertex for the first time, he takes the medicine, and his strength is multiplied by g _ i. (For a vertex with a medicine, s _ i=0.)

There are at most 10 vertices with a medicine.

Takahashi can repeatedly move to an adjacent vertex. Determine if he can defeat all the enemies.

Constraints

• 2\leq N\leq 500
• 1\leq p _ i\lt i\ (2\leq i\leq N)
• t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
• t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
• t _ i=2\implies s _ i=0\ (2\leq i\leq N)
• 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
• There are at most 10 vertices with t _ i=2.
• All input values are integers.

Sample Input 1

8
1 2 0 3
2 1 3 3
1 2 0 4
4 1 2 2
1 2 0 5
6 1 5 5
5 1 140 1

Sample Output 1

Yes

Initially, the tree looks like this:

Takahashi can defeat all the enemies by moving from vertex 1 to 2,3,2,1,6,7,6,1,4,5,8 in this order. Here, his position and strength change as shown in the following figure (movements to vertices that have already been visited are omitted).

On the other hand, if he moves from vertex 1 to 4,5,8 in this order, for example, his strength when visiting vertex 8 will be less than s _ 8=140, so he will lose without defeating all the enemies.

Sample Input 2

12
1 1 166 619
1 1 17 592
2 1 222 983
2 1 729 338
5 1 747 62
3 1 452 815
3 2 0 1
4 2 0 40
4 1 306 520
6 1 317 591
1 1 507 946

Sample Output 2

No

Sample Input 3

12
1 1 1 791
2 2 0 410
2 1 724 790
2 1 828 599
5 2 0 13
3 1 550 803
1 1 802 506
5 1 261 587
6 1 663 329
8 1 11 955
9 1 148 917

Sample Output 3

Yes

Sample Input 4

12
1 2 0 1000000000
2 2 0 1000000000
3 2 0 1000000000
4 2 0 1000000000
5 2 0 1000000000
6 2 0 1000000000
7 2 0 1000000000
8 2 0 1000000000
9 2 0 1000000000
10 2 0 1000000000
11 1 1 1

Sample Output 4

Yes

Problem Statement

We will perform the following operation on a complete undirected graph G with N vertices.

For each i = 1, 2, \ldots, M, delete the undirected edge connecting vertices u_i and v_i.

Determine if there is a path from vertex 1 to vertex N in G after the operation. If there is, find the number, modulo 998244353, of shortest paths from vertex 1 to vertex N.

Here, a shortest path from vertex 1 to vertex N is a path from vertex 1 to vertex N that contains the minimum number of edges.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

In G after the operation, the shortest paths from vertex 1 to vertex N are the following three, each containing three edges.

• vertex 1 \rightarrow vertex 2 \rightarrow vertex 3 \rightarrow vertex 6
• vertex 1 \rightarrow vertex 2 \rightarrow vertex 5 \rightarrow vertex 6
• vertex 1 \rightarrow vertex 4 \rightarrow vertex 5 \rightarrow vertex 6

Sample Input 2

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

Sample Output 2

-1

G has no edges after the operation. There is no path from vertex 1 to vertex N, so print -1.