Problem Statement

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

• Each of S and T is a string that satisfies the following conditions.
  • The length is between 1 and 10, inclusive.
  • The first character is an uppercase English letter.
  • All characters except the first one are lowercase English letters.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san

Problem Statement

You are given a positive integer N.
Output the sum of all integers from 1 to N, that is, 1+2+\cdots+N.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

5

Sample Output 1

15

Since 1+2+3+4+5=15, output 15.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

29

Sample Output 3

435

Problem Statement

There are 2N people standing in a row, and the person at the i-th position from the left is wearing clothes of color A_i. Here, the clothes have N colors from 1 to N, and exactly two people are wearing clothes of each color.

Find how many of the integers i=1,2,\ldots,N satisfy the following condition:

• There is exactly one person between the two people wearing clothes of color i.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq N
• Each integer from 1 through N appears exactly twice in A.
• All input values are integers.

Sample Input 1

3
1 2 1 3 2 3

Sample Output 1

2

There are two values of i that satisfy the condition: 1 and 3.

In fact, the people wearing clothes of color 1 are at the 1st and 3rd positions from the left, with exactly one person in between.

Sample Input 2

2
1 1 2 2

Sample Output 2

0

There may be no i that satisfies the condition.

Sample Input 3

4
4 3 2 3 2 1 4 1

Sample Output 3

3

Problem Statement

There are N types of elements numbered 1, 2, \ldots, N.

Elements can be combined with each other. When elements i and j are combined, they transform into element A_{i, j} if i \geq j, and into element A_{j, i} if i < j.

Starting with element 1, combine it with elements 1, 2, \ldots, N in this order. Find the final element obtained.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_{i, j} \leq N
• All input values are integers.

Sample Input 1

4
3
2 4
3 1 2
2 1 2 4

Sample Output 1

2

• Combining element 1 with element 1 results in element 3.

• Combining element 3 with element 2 results in element 1.

• Combining element 1 with element 3 results in element 3.

• Combining element 3 with element 4 results in element 2.

Therefore, the value to be printed is 2.

Sample Input 2

5
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

Sample Output 2

5

Sample Input 3

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

Sample Output 3

5

Problem Statement

There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:

• Choose one integer x not less than 2 written on the blackboard.
• Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
• Takahashi must pay x yen to perform this series of operations.

Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

• 2 \leq N \leq 10^{17}

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one 3 written on the blackboard.
• He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
• There is one 2 and one 1 written on the blackboard.
• He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
• There are three 1s written on the blackboard.
• Since all integers not less than 2 have been removed from the blackboard, the process is finished.

Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

Problem Statement

Takahashi is a cashier.

There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The cash register initially displays 0. Whenever he types the key 00, the displayed number is multiplied by 100; whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.

Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?

Constraints

• 1\leq S\leq 10^{100000}
• S is an integer.

Sample Input 1

40004

Sample Output 1

4

For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.

• Type the key 4. It now displays 4.
• Type the key 00. It now displays 400.
• Type the key 0. It now displays 4000.
• Type the key 4. It now displays 40004.

He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.

Sample Input 2

1355506027

Sample Output 2

10

Sample Input 3

10888869450418352160768000001

Sample Output 3

27

Note that S may not fit into a 64-\operatorname{bit} integer type.

Problem Statement

You initially have an empty string S.
Additionally, there are bags 1, 2, \dots, N, each containing some strings.
Bag i contains A_i strings S_{i,1}, S_{i,2}, \dots, S_{i,A_i}.

You will repeat the following steps for i = 1, 2, \dots, N:

• Choose and perform one of the following two actions:
  • Pay 1 yen, select exactly one string from bag i, and concatenate it to the end of S.
  • Do nothing.

Given a string T, find the minimum amount of money required to make the final S equal T.
If there is no way to make the final S equal T, print -1.

Constraints

• T is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
• N is an integer between 1 and 100, inclusive.
• A_i is an integer between 1 and 10, inclusive.
• S_{i,j} is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

Sample Output 1

2

For example, doing the following makes the final S equal T with two yen, which can be shown to be the minimum amount required.

• For i=1, select abc from bag 1 and concatenate it to the end of S, making S= abc.
• For i=2, do nothing.
• For i=3, select de from bag 3 and concatenate it to the end of S, making S= abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final S equal T, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4

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 Vertices U_i and V_i.

There are 2^N ways to paint each vertex red or blue. Find the number, modulo 998244353, of such ways that satisfy all of the following conditions:

• There are exactly K vertices painted red.
• There is an even number of edges connecting vertices painted in different colors.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 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

4 4 2
1 2
1 3
2 3
3 4

Sample Output 1

2

The following two ways satisfy the conditions.

• Paint Vertices 1 and 2 red and Vertices 3 and 4 blue.
• Paint Vertices 3 and 4 red and Vertices 1 and 2 blue.

In either of the ways above, the 2-nd and 3-rd edges connect vertices painted in different colors.

Sample Input 2

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

Sample Output 2

64

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1, 2, \ldots, N, and for each 1\leq i\leq N-1, the i-th edge connects Vertex U_i and Vertex V_i. Let D be the diameter of the tree. Find the number, modulo 998244353, of ways to choose two or more of the vertices and paint them red so that all distances between two red vertices are D.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of the tree is the maximum distance between two vertices.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq U_i,V_i \leq N
• U_i \neq V_i
• All values in input are integers.
• The given graph is a tree.

Sample Input 1

5
1 2
1 3
1 4
4 5

Sample Output 1

2

The given tree has five vertices and a diameter of 3.
There are just two pairs of vertices whose distance is 3: (2,5) and (3,5), so there are two ways to paint the tree to satisfy the condition: \lbrace 2,5\rbrace and \lbrace 3,5\rbrace .
Note that painting 2,3,5 does not satisfy the condition since the distance between Vertex 2 and Vertex 3 is 2.

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

4

The diameter is 2, and the four ways to paint the tree to satisfy the condition are: \lbrace 2,3\rbrace , \lbrace 2,4\rbrace , \lbrace 3,4\rbrace , \lbrace 2,3,4\rbrace .