Problem Statement

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

• N is an integer such that 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa

Problem Statement

You are given a sequence of integers A = (A_1, A_2, A_3).
Let B = (B_1, B_2, B_3) be any permutation of A.
Determine whether it is possible that B_1 \times B_2 = B_3.

Constraints

• All input values are integers.
• 1 \le A_1, A_2, A_3 \le 100

Sample Input 1

3 15 5

Sample Output 1

Yes

Here, A=(3,15,5). By rearranging it as B=(3,5,15), we can satisfy B_1 \times B_2 = B_3.

Sample Input 2

5 3 2

Sample Output 2

No

No permutation of B satisfies B_1 \times B_2 = B_3.

Problem Statement

There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq L_i \leq 100
• 1 \leq T \leq 100
• 1 \leq P \leq N
• All input values are integers.

Sample Input 1

5 10 3
3 11 1 6 2

Sample Output 1

7

There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.

After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.

Sample Input 2

2 5 2
10 10

Sample Output 2

0

Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.

Sample Input 3

3 10 1
1 2 3

Sample Output 3

7

Problem Statement

Iroha has a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N (N \ge 1).
She generated a string S using A as follows:

• Start with S = |.
• For i = 1, 2, \dots, N, perform the following operations in order:
  • Append A_i copies of - to the end of S.
  • Then, append one | to the end of S.

Given the generated string S, reconstruct the sequence A.

Constraints

• S is a string of length between 3 and 100, inclusive, generated by the method in the problem statement.
• A is a sequence of positive integers of length at least 1.

Sample Input 1

|---|-|----|-|-----|

Sample Output 1

3 1 4 1 5

S = |---|-|----|-|-----| is generated by A = (3, 1, 4, 1, 5).

Sample Input 2

|----------|

Sample Output 2

10

Sample Input 3

|-|-|-|------|

Sample Output 3

1 1 1 6

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

• 1 \leq a \lt b \leq H
• 1 \leq c \lt d \leq W
• There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

• 2 \leq H, W \leq 500
• S_{i,j} is # or ..

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

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 a tree with N vertices: vertex 1, vertex 2, \ldots, vertex N. The i-th edge (1\leq i\lt N) connects vertex u _ i and vertex v _ i.

Consider repeating the following operation some number of times:

• Choose one leaf vertex v and delete it along with all incident edges.

Find the minimum number of operations required to delete vertex 1.

Constraints

• 2\leq N\leq3\times10^5
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

The given graph looks like this:

For example, you can choose vertices 9,8,7,6,1 in this order to delete vertex 1 in five operations.

Vertex 1 cannot be deleted in four or fewer operations, so print 5.

Sample Input 2

6
1 2
2 3
2 4
3 5
3 6

Sample Output 2

1

In the given graph, vertex 1 is a leaf. Hence, you can choose and delete vertex 1 in the first operation.

Sample Input 3

24
3 6
7 17
7 20
7 11
14 18
17 21
6 19
5 22
9 24
11 14
6 23
8 17
9 12
4 17
2 15
1 17
3 9
10 16
7 13
2 16
1 16
5 7
1 3

Sample Output 3

12

Problem Statement

In a coordinate space, we want to place three cubes with a side length of 7 so that the volumes of the regions contained in exactly one, two, three cube(s) are V_1, V_2, V_3, respectively.

For three integers a, b, c, let C(a,b,c) denote the cubic region represented by (a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7).

Determine whether there are nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 that satisfy all of the following conditions, and find one such tuple if it exists.

• |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| \leq 100
• Let C_i = C(a_i, b_i, c_i)\ (i=1,2,3).
  • The volume of the region contained in exactly one of C_1, C_2, C_3 is V_1.
  • The volume of the region contained in exactly two of C_1, C_2, C_3 is V_2.
  • The volume of the region contained in all of C_1, C_2, C_3 is V_3.

Constraints

• 0 \leq V_1, V_2, V_3 \leq 3 \times 7^3
• All input values are integers.

Sample Input 1

840 84 7

Sample Output 1

Yes
0 0 0 0 6 0 6 0 0

Consider the case (a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (0, 0, 0, 0, 6, 0, 6, 0, 0).

The figure represents the positional relationship of C_1, C_2, and C_3, corresponding to the orange, cyan, and green cubes, respectively.

Here,

• All of |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| are not greater than 100.
• The region contained in all of C_1, C_2, C_3 is (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7), with a volume of (7-6)\times(7-6)\times(7-0)=7.
• The region contained in exactly two of C_1, C_2, C_3 is ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y < 6) \land (0\leq z\leq 7)), with a volume of (6-0)\times(7-6)\times(7-0)\times 2=84.
• The region contained in exactly one of C_1, C_2, C_3 has a volume of 840.

Thus, all conditions are satisfied.

(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (-10, 0, 0, -10, 0, 6, -10, 6, 1) also satisfies all conditions and would be a valid output.

Sample Input 2

343 34 3

Sample Output 2

No

No nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions.

Problem Statement

There are N rooms numbered 1, 2, \ldots, N, each with one person living in it, and M corridors connecting two different rooms. The i-th corridor connects room U_i and room V_i with a length of W_i.

One day (we call this day 0), the K people living in rooms A_1, A_2, \ldots, A_K got (newly) infected with a virus. Furthermore, on the i-th of the following D days (1\leq i\leq D), the infection spread as follows.

People who were infected at the end of the night of day (i-1) remained infected at the end of the night of day i.
For those who were not infected, they were newly infected if and only if they were living in a room within a distance of X_i from at least one room where an infected person was living at the end of the night of day (i-1). Here, the distance between rooms P and Q is defined as the minimum possible sum of the lengths of the corridors when moving from room P to room Q using only corridors. If it is impossible to move from room P to room Q using only corridors, the distance is set to 10^{100}.

For each i (1\leq i\leq N), print the day on which the person living in room i was newly infected. If they were not infected by the end of the night of day D, print -1.

Constraints

• 1 \leq N\leq 3\times 10^5
• 0 \leq M\leq 3\times 10^5
• 1 \leq U_i < V_i\leq N
• All (U_i,V_i) are different.
• 1\leq W_i\leq 10^9
• 1 \leq K\leq N
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1 \leq D\leq 3\times 10^5
• 1\leq X_i\leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
1
2

The infection spreads as follows.

• On the night of day 0, the person living in room 1 gets infected.
• The distances between room 1 and rooms 2,3,4 are 2,3,5, respectively. Thus, since X_1=3, the people living in rooms 2 and 3 are newly infected on the night of day 1.
• The distance between rooms 3 and 4 is 2. Thus, since X_2=3, the person living in room 4 also gets infected on the night of day 2.

Therefore, the people living in rooms 1,2,3,4 were newly infected on days 0,1,1,2, respectively, so print 0,1,1,2 in this order on separate lines.

Sample Input 2

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

Sample Output 2

0
1
2
-1
2
0
-1

Sample Input 3

5 1
1 2 5
2
1 3
3
3 7 5

Sample Output 3

0
2
0
-1
-1

Note that it is not always possible to move between any two rooms using only corridors.