Problem Statement

You are given an odd-length string S consisting of lowercase English letters.

Print the central character of S.

Constraints

• S is an odd-length string consisting of lowercase English letters.
• The length of S is between 1 and 99 (inclusive).

Sample Input 1

atcoder

Sample Output 1

o

The central character of atcoder is o.

Sample Input 2

a

Sample Output 2

a

Problem Statement

The magnitude of an earthquake is a logarithmic scale of the energy released by the earthquake. It is known that each time the magnitude increases by 1, the amount of energy gets multiplied by approximately 32.
Here, we assume that the amount of energy gets multiplied by exactly 32 each time the magnitude increases by 1. In this case, how many times is the amount of energy of a magnitude A earthquake as much as that of a magnitude B earthquake?

Constraints

• 3\leq B\leq A\leq 9
• A and B are integers.

Sample Input 1

6 4

Sample Output 1

1024

6 is 2 greater than 4, so a magnitude 6 earthquake has 32\times 32=1024 times as much energy as a magnitude 4 earthquake has.

Sample Input 2

5 5

Sample Output 2

1

Earthquakes with the same magnitude have the same amount of energy.

Problem Statement

You are given a string S consisting of lowercase English letters. Find the character that appears most frequently in S. If multiple such characters exist, report the one that comes earliest in alphabetical order.

Constraints

• 1 \leq |S| \leq 1000 (|S| is the length of the string S.)
• Each character in S is a lowercase English letter.

Sample Input 1

frequency

Sample Output 1

e

In frequency, the letter e appears twice, which is more than any other character, so you should print e.

Sample Input 2

atcoder

Sample Output 2

a

In atcoder, each of the letters a, t, c, o, d, e, and r appears once, so you should print the earliest in alphabetical order, which is a.

Sample Input 3

pseudopseudohypoparathyroidism

Sample Output 3

o

Problem Statement

Takahashi has N foods in his house. The i-th food has the tastiness of A_i.
He dislikes K of these foods: for each i=1,2,\ldots,K, he dislikes the B_i-th food.

Out of the foods with the greatest tastiness among the N foods, Takahashi will randomly choose one and eat it.
If he has a chance to eat something he dislikes, print Yes; otherwise, print No.

Constraints

• 1\leq K\leq N\leq 100
• 1\leq A_i\leq 100
• 1\leq B_i\leq N
• All B_i are distinct.
• All values in input are integers.

Sample Input 1

5 3
6 8 10 7 10
2 3 4

Sample Output 1

Yes

Among the five foods, the ones with the greatest tastiness are Food 3 and 5, of which he eats one.
He dislikes Food 2, 3, and 4, one of which he has a chance to eat: Food 3.
Therefore, the answer is Yes.

Sample Input 2

5 2
100 100 100 1 1
5 4

Sample Output 2

No

The foods with the greatest tastiness are Food 1, 2, and 3, none of which he has a chance to eat.

Sample Input 3

2 1
100 1
2

Sample Output 3

No

The food with the greatest tastiness is Food 1, which he has no chance to eat.

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

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

• if the i-th character of S is 0, he has no plan scheduled for the i-th day;
• if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
• if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• 1\leq M\leq N\leq 1000
• S is a string of length N consisting of 0, 1, and 2.
• N and M are integers.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

Problem Statement

For real numbers L and R, let us denote by [L,R) the set of real numbers greater than or equal to L and less than R. Such a set is called a right half-open interval.

You are given N right half-open intervals [L_i,R_i). Let S be their union. Represent S as a union of the minimum number of right half-open intervals.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq L_i \lt R_i \leq 2\times 10^5
• All values in input are integers.

Sample Input 1

3
10 20
20 30
40 50

Sample Output 1

10 30
40 50

The union of the three right half-open intervals [10,20),[20,30),[40,50) equals the union of two right half-open intervals [10,30),[40,50).

Sample Input 2

3
10 40
30 60
20 50

Sample Output 2

10 60

The union of the three right half-open intervals [10,40),[30,60),[20,50) equals the union of one right half-open interval [10,60).

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

• Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
  • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
  • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

• X is an integer between 1 and 10^{17} (inclusive).

Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.

Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.

Sample Input 3

8989898989

Sample Output 3

9876543210

Problem Statement

The Republic of Atcoder has N towns numbered 1 through N, and M highways numbered 1 through M.
Highway i connects Town A_i and Town B_i bidirectionally.

King Takahashi is going to construct (N-M-1) new highways so that the following two conditions are satisfied:

• One can travel between every pair of towns using some number of highways
• For each i=1,\ldots,N, exactly D_i highways are directly connected to Town i

Determine if there is such a way of construction. If it exists, print one.

Constraints

• 2 \leq N \leq 2\times 10^5
• 0 \leq M \lt N-1
• 1 \leq D_i \leq N-1
• 1\leq A_i \lt B_i \leq N
• If i\neq j, then (A_i, B_i) \neq (A_j,B_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

6 2
5 6
4 5

As in the Sample Output, the conditions can be satisfied by constructing highways connecting Towns 6 and 2, Towns 5 and 6, and Towns 4 and 5, respectively.

Another example to satisfy the conditions is to construct highways connecting Towns 6 and 4, Towns 5 and 6, and Towns 2 and 5, respectively.

Sample Input 2

5 1
1 1 1 1 4
2 3

Sample Output 2

-1

Sample Input 3

4 0
3 3 3 3

Sample Output 3

-1