Problem Statement

You are given an integer S between 100 and 999 (inclusive).

If S is between 200 and 299 (inclusive), print Success; otherwise, print Failure.

Constraints

• 100 \le S \le 999
• S is an integer.

Sample Input 1

200

Sample Output 1

Success

200 is between 200 and 299, so print Success.

Sample Input 2

401

Sample Output 2

Failure

401 is not between 200 and 299, so print Failure.

Sample Input 3

999

Sample Output 3

Failure

Problem Statement

One day, Takahashi performed N operations on a certain web site.

The i‑th operation (1 \le i \le N) is represented by a string S_i, which is one of the following:

• S _ i= login: He performs a login operation and becomes logged in to the site.
• S _ i= logout: He performs a logout operation and becomes not logged in to the site.
• S _ i= public: He accesses a public page of the site.
• S _ i= private: He accesses a private page of the site.

The site returns an authentication error if and only if he accesses a private page while he is not logged in.

Logging in again while already logged in, or logging out again while already logged out, does not cause an error. Even after an authentication error is returned, he continues performing the remaining operations.

Initially, he is not logged in.

Print the number of operations among the N operations at which he receives an authentication error.

Constraints

• 1 \le N \le 100
• N is an integer.
• Each S_i is one of login, logout, public, private. (1 \le i \le N)

Sample Input 1

6
login
private
public
logout
private
public

Sample Output 1

1

The result of each operation is as follows:

• Takahashi becomes logged in.
• He accesses a private page. He is logged in, so no error is returned.
• He accesses a public page.
• He becomes logged out.
• He accesses a private page. He is not logged in, so an authentication error is returned.
• He accesses a public page.

An authentication error occurs only at the 5th operation, so print 1.

Sample Input 2

4
private
private
private
logout

Sample Output 2

3

If he tries to access private pages consecutively while not logged in, he receives an authentication error for each such operation.

Note that logging out again while already logged out does not cause an authentication error.

Sample Input 3

20
private
login
private
logout
public
logout
logout
logout
logout
private
login
login
private
login
private
login
public
private
logout
private

Sample Output 3

3

Problem Statement

You are given positive integers N and K. Define a sequence A = (A_0, A_1, \ldots, A_N) of length N+1 as follows:

• A_i = 1 for 0 \le i < K;
• A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1} for K \le i.

Find A_N modulo 10^9.

Constraints

• 1 \le N, K \le 10^{6}
• All input values are integers.

Sample Input 1

4 2

Sample Output 1

5

We have A_0 = A_1 = 1, and A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5.

Sample Input 2

10 20

Sample Output 2

1

Sample Input 3

1000000 500000

Sample Output 3

420890625

Remember to print A_N modulo 10^9.

Problem Statement

You are given a string S of length N consisting of the characters ., o, and ?. Among the strings that can be obtained by replacing every ? in S independently with either . or o, let X be the set of strings that satisfy all of the following conditions:

• The number of os is exactly K.
• No two os are adjacent.

It is guaranteed that X is non‑empty.

Print a string T of length N that satisfies the following (let T_i denote the i‑th character of T):

• If the i‑th character of every string in X is ., then T_i= ..
• If the i‑th character of every string in X is o, then T_i= o.
• If X contains both a string whose i‑th character is . and a string whose i‑th character is o, then T_i= ?.

Constraints

• 1 \le N \le 2 \times 10^{5}
• 0 \le K
• S is a string of length N consisting of ., o, ?.
• X is non‑empty.
• All given numerical values are integers.

Sample Input 1

4 2
o???

Sample Output 1

o.??

The set X consists of the two strings o.o. and o..o.

• The 1st character of every string in X is o, so T_1 is o.
• The 2nd character of every string in X is ., so T_2 is ..
• The 3rd character of a string in X can be either . or o, so T_3 is ?.

Sample Input 2

5 2
?????

Sample Output 2

?????

Sample Input 3

7 3
.o???o.

Sample Output 3

.o.o.o.

Problem Statement

You are given an undirected graph with N vertices and M edges. The vertices are numbered 1,2,\ldots,N, and the i‑th edge (1 \le i \le M) connects vertices u_i and v_i.

For each k = 1,2,\ldots,N, solve the following problem:

Consider the following operation.

• Choose one vertex, and delete that vertex together with all edges incident to it.

Determine whether one can repeat this operation to satisfy the following condition:

• The set of vertices reachable from vertex 1 by traversing edges consists exactly of the k vertices 1,2,\ldots,k.

If it is possible, find the minimum number of operations required to do so.

Constraints

• 1 \le N \le 2 \times 10^{5}
• 0 \le M \le 3 \times 10^{5}
• 1 \le u_i < v_i \le N\ (1 \le i \le M)
• (u_i,v_i) \ne (u_j,v_j)\ (1 \le i < j \le M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
3
3
2
1
0

For example, for k = 2, deleting the three vertices 3, 4, 5 makes the set of vertices reachable from vertex 1 equal to the two vertices 1, 2. It is impossible with two or fewer deletions, so print 3 on the 2nd line.

For k = 6, deleting zero vertices makes the set of vertices reachable from vertex 1 equal to the six vertices 1,2,\ldots,6, so print 0 on the 6th line.

Sample Input 2

5 4
1 5
2 3
3 4
4 5

Sample Output 2

1
-1
-1
-1
0

Sample Input 3

2 0

Sample Output 3

0
-1

There may be no edges.

Sample Input 4

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

Sample Output 4

5
-1
-1
-1
-1
-1
4
3
2
1
0

Problem Statement

You are given two trees: tree 1 with N_1 vertices numbered 1 to N_1, and tree 2 with N_2 vertices numbered 1 to N_2. The i-th edge of tree 1 connects vertices u_{1,i} and v_{1,i} bidirectionally, and the i-th edge of tree 2 connects vertices u_{2,i} and v_{2,i} bidirectionally.

One can add a bidirectional edge between vertex i of tree 1 and vertex j of tree 2 to obtain a single tree. Let f(i,j) be the diameter of this tree.

Find \displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j).

Here, the distance between two vertices of a tree is the minimum number of edges that must be used to move between them, and the diameter of a tree is the maximum distance between two vertices.

Constraints

• 1 \le N_1, N_2 \le 2 \times 10^{5}
• 1 \le u_{1,i}, v_{1,i} \le N_1
• 1 \le u_{2,i}, v_{2,i} \le N_2
• Both given graphs are trees.
• All input values are integers.

Sample Input 1

3
1 3
1 2
3
1 2
3 1

Sample Output 1

39

For example, one can connect vertex 2 of tree 1 and vertex 3 of tree 2 to obtain a tree of diameter 5. Thus, f(2,3) is 5.

The sum of f(i,j) is 39.

Sample Input 2

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

Sample Output 2

267

Problem Statement

There are N people and N buttons on a plane. The plane has an origin, and the coordinates (x, y) represents the position that is x meters east and y meters north of the origin. The i‑th person (1 \le i \le N) starts at (\mathit{sx}_i,\mathit{sy}_i). The i‑th button (1 \le i \le N) is located at (\mathit{gx}_i,\mathit{gy}_i).

The people want to move and press these N buttons simultaneously. A button can be pressed only by a person who is at the same coordinate as that button. The time required to press a button after reaching its coordinate is 0 seconds.

Each person can move in any direction with speed at most 1 meter per second. More formally, if the position of the i‑th person t seconds after the start is (x_i(t), y_i(t)), all of the following must hold:

• x_i(0) = \mathit{sx}_i;
• y_i(0) = \mathit{sy}_i;
• For all non‑negative real numbers t_0, t_1, the distance between (x_i(t_0), y_i(t_0)) and (x_i(t_1), y_i(t_1)) is at most |t_0 - t_1|.

Find the time required for the people to achieve the goal. Formally, find the minimum t that satisfies the following condition:

• It is possible to set x_i and y_i under the above conditions so that, for every integer j\ (1\leq j\leq N) and every real number t ^ \prime\ (t ^ \prime\gt t), there exists an integer i\ (1\leq i\leq N) with (x _ i(t ^ \prime),y _ i(t ^ \prime))=(\mathit{gx} _ j,\mathit{gy} _ j).

Constraints

• 1\leq N\leq 300
• 0\leq\mathit{sx} _ i\leq10 ^ {18}\ (1\leq i\leq N)
• 0\leq\mathit{sy} _ i\leq10 ^ {18}\ (1\leq i\leq N)
• 0\leq\mathit{gx} _ i\leq10 ^ {18}\ (1\leq i\leq N)
• 0\leq\mathit{gy} _ i\leq10 ^ {18}\ (1\leq i\leq N)
• (\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{sx} _ j,\mathit{sy} _ j)\ (1\leq i\lt j\leq N)
• (\mathit{gx} _ i,\mathit{gy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\lt j\leq N)
• (\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\leq N,1\leq j\leq N)
• All input values are integers.

Sample Input 1

4
0 0
0 1
2 0
3 1
0 2
1 0
1 2
2 2

Sample Output 1

2

Initially, the positions of the people and buttons are as shown below.

Suppose persons 1,2,3,4 move straight toward buttons 1,3,2,4, respectively.

They reach their respective buttons after 2, \sqrt2, 1, and \sqrt2 seconds.

Thus, all buttons can be pressed simultaneously 2 seconds after the start.

Conversely, they cannot press all buttons simultaneously earlier than 2 seconds, so print 2.

Because an output is accepted if its relative error from the true value is at most 10^{-6}, outputs such as 1.999998 or 2.00000014 are also considered correct for this test case.

Sample Input 2

3
1 4
1 5
9 2
653589793238462643 383279502884197169
399375105820974944 592307816406286208
99862803482534211 706798214808651328

Sample Output 2

757682516069002110.04581169374262658710741005525

Note that the input coordinates may not fit in 32‑bit integers.

Sample Input 3

12
4459915897 5789359311
4393259463 4247016333
4827828467 4179021045
2654035685 3406423989
1790405301 4886103164
2978675817 4818583236
5912369644 5824121992
6016882384 4165667191
4305949638 3454894060
6545166942 5390976281
4043403253 4019611554
3462096432 4117859301
3528911877 4631601790
4627979431 4814676729
3810130146 5728760563
5586470124 3310360339
3664130072 4525834271
1710246881 3750440871
3143440609 5038869551
2294021341 3965849888
6189106395 4499485672
4799619607 5151972020
6905793542 3976136296
1764267574 4525373194

Sample Output 3

1299999319.116399442508650717909981965254