Problem Statement

You are given a string S. Here, the first character of S is an uppercase English letter, and the second and subsequent characters are lowercase English letters.

Print the string formed by concatenating the first character of S and UPC in this order.

Constraints

• S is a string of length between 1 and 100, inclusive.
• The first character of S is an uppercase English letter.
• The second and subsequent characters of S are lowercase English letters.

Sample Input 1

Kyoto

Sample Output 1

KUPC

The first character of Kyoto is K, so concatenate K and UPC, and print KUPC.

Sample Input 2

Tohoku

Sample Output 2

TUPC

Problem Statement

This is the 214-th AtCoder Beginner Contest (ABC).

The ABCs so far have had the following number of problems.

• The 1-st through 125-th ABCs had 4 problems each.
• The 126-th through 211-th ABCs had 6 problems each.
• The 212-th through 214-th ABCs have 8 problems each.

Find the number of problems in the N-th ABC.

Constraints

• 1 \leq N \leq 214
• All values in input are integers.

Sample Input 1

214

Sample Output 1

8

Sample Input 2

1

Sample Output 2

4

Sample Input 3

126

Sample Output 3

6

Problem Statement

KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.

You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.

More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:

• 1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
• |S| < i \leq |T|.
• |T| < i \leq |S|.

Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.

Constraints

• S and T are strings of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

abcde
abedc

Sample Output 1

3

We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.

Sample Input 2

abcde
abcdefg

Sample Output 2

6

We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.

Sample Input 3

keyence
keyence

Sample Output 3

0

S and T are equal, so print 0.

Problem Statement

A string S is given.

Find how many places in S have A, B, and C in this order at even intervals.

Specifically, find the number of triples of integers (i,j,k) that satisfy all of the following conditions. Here, |S| denotes the length of S, and S_x denotes the x-th character of S.

• 1 \leq i < j < k \leq |S|
• j - i = k - j
• S_i = A
• S_j = B
• S_k = C

Constraints

• S is an uppercase English string with length between 3 and 100, inclusive.

Sample Input 1

AABCC

Sample Output 1

2

There are two triples (i,j,k) = (1,3,5) and (2,3,4) that satisfy the conditions.

Sample Input 2

ARC

Sample Output 2

0

Sample Input 3

AABAAABBAEDCCCD

Sample Output 3

4

Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

• All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.

Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228

Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• 1 \leq N \leq 10
• 1 \leq Q_i \leq 10^6
• 0 \leq A_i \leq 10^6
• There is an i such that A_i \geq 1.
• 0 \leq B_i \leq 10^6
• There is an i such that B_i \geq 1.
• All input values are integers.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

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

Sample Output 4

222222

Problem Statement

Find the number of positive integers not greater than N that have exactly 9 positive divisors.

Constraints

• 1 \leq N \leq 4 \times 10^{12}
• All input values are integers.

Sample Input 1

200

Sample Output 1

3

Three positive integers 36,100,196 satisfy the condition.

Sample Input 2

4000000000000

Sample Output 2

407073

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges (a simple graph contains no self-loop and no multi-edges).
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

• At least one vertex is painted black.
• For every i = 1, 2, \ldots, K, the following holds:
  • the minimum distance between vertex p_i and a vertex painted black is exactly d_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in a path connecting u and v.

Constraints

• 1 \leq N \leq 2000
• N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace
• 1 \leq u_i, v_i \leq N
• 0 \leq K \leq N
• 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N
• 0 \leq d_i \leq N
• The given graph is simple and connected.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes
10100

One way to satisfy the conditions is to paint vertices 1, 3 black and vertices 2, 4, 5 white.
Indeed, for each i = 1, 2, 3, 4, 5, let A_i denote the minimum distance between vertex i and a vertex painted black, and we have (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2), where A_1 = 0, A_5 = 2.

Sample Input 2

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

Sample Output 2

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3

1 0
0

Sample Output 3

Yes
1

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.

A sequence (A_1, A_2, \ldots, A_k) is said to be a path of length k if both of the following two conditions are satisfied:

• For all i = 1, 2, \dots, k, it holds that 1 \leq A_i \leq N.
• For all i = 1, 2, \ldots, k-1, Vertex A_i and Vertex A_{i+1} are directly connected by an edge.

An empty sequence is regarded as a path of length 0.

Let S = s_1s_2\ldots s_N be a string of length N consisting of 0 and 1. A path A = (A_1, A_2, \ldots, A_k) is said to be a good path with respect to S if the following conditions are satisfied:

• For all i = 1, 2, \ldots, N, it holds that:
  • if s_i = 0, then A has even number of i's.
  • if s_i = 1, then A has odd number of i's.

There are 2^N possible S (in other words, there are 2^N strings of length N consisting of 0 and 1). Find the sum of "the length of the shortest good path with respect to S" over all those S.

Under the Constraints of this problem, it can be proved that, for any string S of length N consisting of 0 and 1, there is at least one good path with respect to S.

Constraints

• 2 \leq N \leq 17
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple and connected.
• All values in input are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

14

• For S = 000, the empty sequence () is the shortest good path with respect to S, whose length is 0.
• For S = 100, (1) is the shortest good path with respect to S, whose length is 1.
• For S = 010, (2) is the shortest good path with respect to S, whose length is 1.
• For S = 110, (1, 2) is the shortest good path with respect to S, whose length is 2.
• For S = 001, (3) is the shortest good path with respect to S, whose length is 1.
• For S = 101, (1, 2, 3, 2) is the shortest good path with respect to S, whose length is 4.
• For S = 011, (2, 3) is the shortest good path with respect to S, whose length is 2.
• For S = 111, (1, 2, 3) is the shortest good path with respect to S, whose length is 3.

Therefore, the sought answer is 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14.

Sample Input 2

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

Sample Output 2

108