Problem Statement

Print the L-th through R-th characters of the string atcoder.

Constraints

• L and R are integers.
• 1 \le L \le R \le 7

Sample Input 1

3 6

Sample Output 1

code

The 3-rd through 6-th characters of atcoder are code.

Sample Input 2

4 4

Sample Output 2

o

Sample Input 3

1 7

Sample Output 3

atcoder

Problem Statement

There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.

Print the total score for all problems with a score of X or less.

Constraints

• All input values are integers.
• 4 \leq N \leq 8
• 100 \leq S_i \leq 675
• 100 \leq X \leq 675

Sample Input 1

6 200
100 675 201 200 199 328

Sample Output 1

499

Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.

Sample Input 2

8 675
675 675 675 675 675 675 675 675

Sample Output 2

5400

Sample Input 3

8 674
675 675 675 675 675 675 675 675

Sample Output 3

0

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.

Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.

• When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
• Otherwise, if the mug is empty, fill the mug with water.
• Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

• 1\leq K\leq 100
• 1\leq G<M\leq 1000
• G, M, and K are integers.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

• Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
• Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
• Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
• Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
• Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.

Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

Problem Statement

Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.

Notes

For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)

Constraints

• -10^{18} \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

47

Sample Output 1

4

The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.

Sample Input 2

-24

Sample Output 2

-3

Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.

Sample Input 3

50

Sample Output 3

5

The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.

Sample Input 4

-30

Sample Output 4

-3

Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.

Sample Input 5

987654321987654321

Sample Output 5

98765432198765432

The answer is 98765432198765432. Make sure that all the digits match.

If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the number of non-empty substrings of S that are repetitions of one character. Here, two substrings that are equal as strings are not distinguished even if they are obtained differently.

A non-empty substring of S is a string of length at least one obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, ab and abc are non-empty substrings of abc, while ac and the empty string are not.

Constraints

• 1 \leq N \leq 2\times 10^5
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
aaabaa

Sample Output 1

4

The non-empty substrings of S that are repetitions of one character are a, aa, aaa, and b; there are four of them. Note that there are multiple ways to obtain a or aa from S, but each should only be counted once.

Sample Input 2

1
x

Sample Output 2

1

Sample Input 3

12
ssskkyskkkky

Sample Output 3

8

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

5
3
1 2
2 3
3 4
4
1 2
2 3
3 4
4 5
9 1 1 1
1 1 1
1 1
9

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214

Problem Statement

You are given an integer N and strings R and C of length N consisting of A, B, and C. Solve the following problem.

There is a N \times N grid. All cells are initially empty.
You can write at most one character from A, B, and C in each cell. (You can also leave the cell empty.)

Determine if it is possible to satisfy all of the following conditions, and if it is possible, print one way to do so.

• Each row and each column contain exactly one A, one B, and one C.
• The leftmost character written in the i-th row matches the i-th character of R.
• The topmost character written in the i-th column matches the i-th character of C.

Constraints

• N is an integer between 3 and 5, inclusive.
• R and C are strings of length N consisting of A, B, and C.

Sample Input 1

5
ABCBC
ACAAB

Sample Output 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

The grid in the output example satisfies all the following conditions, so it will be treated as correct.

• Each row contains exactly one A, one B, and one C.
• Each column contains exactly one A, one B, and one C.
• The leftmost characters written in the rows are A, B, C, B, C from top to bottom.
• The topmost characters written in the columns are A, C, A, A, B from left to right.

Sample Input 2

3
AAA
BBB

Sample Output 2

No

For this input, there is no way to fill the grid to satisfy the conditions.

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

• Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

• 1 \le N \le 2 \times 10^5
• 0 \le M \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i,V_i \le N
• The given graph is simple.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

• Choose Vertex 3. The cost is A_1=3.
• Choose Vertex 1. The cost is A_2+A_4=3.
• Choose Vertex 2. The cost is 0.
• Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

1199

Problem Statement

Given is a string S. From this string, Takahashi will make a new string T as follows.

• First, mark one or more characters in S. Here, no two marked characters should be adjacent.
• Next, delete all unmarked characters.
• Finally, let T be the remaining string. Here, it is forbidden to change the order of the characters.

How many strings are there that can be obtained as T? Find the count modulo (10^9 + 7).

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

4

There are four strings that can be obtained as T: a, b, c, and ac.

Marking the first character of S yields a;

marking the second character of S yields b;

marking the third character of S yields c;

marking the first and third characters of S yields ac.

Note that it is forbidden to, for example, mark both the first and second characters.

Sample Input 2

aa

Sample Output 2

1

There is just one string that can be obtained as T, which is a. Note that marking different positions may result in the same string.

Sample Input 3

acba

Sample Output 3

6

There are six strings that can be obtained as T: a, b, c, aa, ab, and ca.

Sample Input 4

chokudai

Sample Output 4

54