Problem Statement

You are given a non-empty string S consisting of uppercase and lowercase English letters. Determine whether the following condition is satisfied:

• The first character of S is uppercase, and all other characters are lowercase.

Constraints

• 1 \leq |S| \leq 100 (|S| is the length of the string S.)
• Each character of S is an uppercase or lowercase English letter.

Sample Input 1

Capitalized

Sample Output 1

Yes

The first character C of Capitalized is uppercase, and all other characters apitalized are lowercase, so you should print Yes.

Sample Input 2

AtCoder

Sample Output 2

No

AtCoder contains an uppercase letter C that is not at the beginning, so you should print No.

Sample Input 3

yes

Sample Output 3

No

The first character y of yes is not uppercase, so you should print No.

Sample Input 4

A

Sample Output 4

Yes

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

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

The AtCoder Archipelago consists of N islands connected by N bridges. The islands are numbered from 1 to N, and the i-th bridge (1\leq i\leq N-1) connects islands i and i+1 bidirectionally, while the N-th bridge connects islands N and 1 bidirectionally. There is no way to travel between islands other than crossing the bridges.

On the islands, a tour that starts from island X_1 and visits islands X_2, X_3, \dots, X_M in order is regularly conducted. The tour may pass through islands other than those being visited, and the total number of times bridges are crossed during the tour is defined as the length of the tour.

More precisely, a tour is a sequence of l+1 islands a_0, a_1, \dots, a_l that satisfies all the following conditions, and its length is defined as l:

• For all j\ (0\leq j\leq l-1), islands a_j and a_{j+1} are directly connected by a bridge.
• There are some 0 = y_1 < y_2 < \dots < y_M = l such that for all k\ (1\leq k\leq M), a_{y_k} = X_k.

Due to financial difficulties, the islands will close one bridge to reduce maintenance costs. Determine the minimum possible length of the tour when the bridge to be closed is chosen optimally.

Constraints

• 3\leq N \leq 2\times 10^5
• 2\leq M \leq 2\times 10^5
• 1\leq X_k\leq N
• X_k\neq X_{k+1}\ (1\leq k\leq M-1)
• All input values are integers.

Sample Input 1

3 3
1 3 2

Sample Output 1

2

• If the first bridge is closed: By taking the sequence of islands (a_0, a_1, a_2) = (1, 3, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 2 can be conducted. There is no shorter tour.
• If the second bridge is closed: By taking the sequence of islands (a_0, a_1, a_2, a_3) = (1, 3, 1, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 3 can be conducted. There is no shorter tour.
• If the third bridge is closed: By taking the sequence of islands (a_0, a_1, a_2, a_3) = (1, 2, 3, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 3 can be conducted. There is no shorter tour.

Therefore, the minimum possible length of the tour when the bridge to be closed is chosen optimally is 2.

The following figure shows, from left to right, the cases when bridges 1, 2, 3 are closed, respectively. The circles with numbers represent islands, the lines connecting the circles represent bridges, and the blue arrows represent the shortest tour routes.

Sample Input 2

4 5
2 4 2 4 2

Sample Output 2

8

The same island may appear multiple times in X_1, X_2, \dots, X_M.

Sample Input 3

163054 10
62874 19143 77750 111403 29327 56303 6659 18896 64175 26369

Sample Output 3

390009

Problem Statement

There are 2N points placed at equal intervals on a circle, numbered 1 to 2N in a clockwise direction starting from a certain point.

There are also N chords on the circle, with the i-th chord connecting points A_i and B_i. It is guaranteed that all the values A_1,\dots,A_N,B_1,\dots,B_N are distinct.

Determine whether there is an intersection between the chords.

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq 2N
• A_1,\dots,A_N,B_1,\dots,B_N are all distinct
• All input values are integers

Sample Input 1

3
1 3
4 2
5 6

Sample Output 1

Yes

As shown in the figure, chord 1 (the line segment connecting points 1 and 3) and chord 2 (the line segment connecting points 4 and 2) intersect, so print Yes.

Sample Input 2

3
6 1
4 3
2 5

Sample Output 2

No

As shown in the figure, there is no intersection between the chords, so print No.

Sample Input 3

4
2 4
3 7
8 6
5 1

Sample Output 3

Yes

Problem Statement

There is a weighted simple directed graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge has a weight of W_i and extends from vertex U_i to vertex V_i. The weights can be negative, but the graph does not contain negative cycles.

Determine whether there is a walk that visits each vertex at least once. If such a walk exists, find the minimum total weight of the edges traversed. If the same edge is traversed multiple times, the weight of that edge is added for each traversal.

Here, "a walk that visits each vertex at least once" is a sequence of vertices v_1,v_2,\dots,v_k that satisfies both of the following conditions:

• For every i (1\leq i\leq k-1), there is an edge extending from vertex v_i to vertex v_{i+1}.
• For every j\ (1\leq j\leq N), there is i (1\leq i\leq k) such that v_i=j.

Constraints

• 2\leq N \leq 20
• 1\leq M \leq N(N-1)
• 1\leq U_i,V_i \leq N
• U_i \neq V_i
• (U_i,V_i) \neq (U_j,V_j) for i\neq j
• -10^6\leq W_i \leq 10^6
• The given graph does not contain negative cycles.
• All input values are integers.

Sample Input 1

3 4
1 2 5
2 1 -3
2 3 -4
3 1 100

Sample Output 1

-2

By following the vertices in the order 2\rightarrow 1\rightarrow 2\rightarrow 3, you can visit all vertices at least once, and the total weight of the edges traversed is (-3)+5+(-4)=-2. This is the minimum.

Sample Input 2

3 2
1 2 0
2 1 0

Sample Output 2

No

There is no walk that visits all vertices at least once.

Sample Input 3

5 9
1 2 -246288
4 5 -222742
3 1 246288
3 4 947824
5 2 -178721
4 3 -947824
5 4 756570
2 5 707902
5 1 36781

Sample Output 3

-449429

Problem Statement

You are given a string S. Each character of S is one of 123456789+*, and the first and last characters of S are digits. There are no adjacent non-digit characters in S.

For a pair of integers i, j (1 \leq i \leq j \leq |S|), we define \mathrm{eval}(S_{i..j}) as follows:

• If both the i-th and j-th characters of S are digits, then \mathrm{eval}(S_{i..j}) is the result of evaluating the i-th to the j-th characters (inclusive) of S as a usual arithmetic expression (where * represents multiplication). For example, if S = 1+2*151, then \mathrm{eval}(S_{1..6}) = 1 + 2 \times 15 = 31.
• Otherwise, \mathrm{eval}(S_{i..j}) is zero.

Find {\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}, modulo 998244353.

Constraints

• 1 \leq |S| \leq 10^6
• Each character of S is one of 123456789+*.
• The first and last characters of S are digits.
• There are no adjacent non-digit characters in S.

Sample Input 1

1+2*34

Sample Output 1

197

The cases where \mathrm{eval}(S_{i..j}) is not zero are as follows:

• \mathrm{eval}(S_{1..1}) = 1
• \mathrm{eval}(S_{1..3}) = 1 + 2 = 3
• \mathrm{eval}(S_{1..5}) = 1 + 2 \times 3 = 7
• \mathrm{eval}(S_{1..6}) = 1 + 2 \times 34 = 69
• \mathrm{eval}(S_{3..3}) = 2
• \mathrm{eval}(S_{3..5}) = 2 \times 3 = 6
• \mathrm{eval}(S_{3..6}) = 2 \times 34 = 68
• \mathrm{eval}(S_{5..5}) = 3
• \mathrm{eval}(S_{5..6}) = 34
• \mathrm{eval}(S_{6..6}) = 4

The sum of these is 1+3+7+69+2+6+68+3+34+4 = 197.

Sample Input 2

338*3338*33338*333338+3333338*33333338+333333338

Sample Output 2

527930018