Problem Statement

Takahashi wants to set his password for a certain website to a string P consisting of lowercase English letters.
The password for that website must be a string of length at least L.

Determine whether P satisfies the length condition, that is, whether it is a string of length at least L.

Constraints

• P is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
• 1 \leq L \leq 100
• L is an integer.

Sample Input 1

chokudai
5

Sample Output 1

Yes

The length of chokudai is 8, which is at least 5, so it satisfies the length condition.
Thus, print Yes.

Sample Input 2

ac
3

Sample Output 2

No

The length of ac is 2, which is less than 3, so it does not satisfy the length condition.
Thus, print No.

Sample Input 3

atcoder
7

Sample Output 3

Yes

The length of atcoder is 7, which is at least 7, so it satisfies the length condition.
Thus, print Yes.

Problem Statement

Takahashi is a teapot.
Since he is a teapot, he will gladly accept tea, but will refuse any other liquid.
Determine whether you can pour a liquid named S into him.

You are given a string S of length N consisting of lowercase English letters.
Determine whether S is a string that ends with tea.

Constraints

• 1 \leq N \leq 20
• N is an integer.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
greentea

Sample Output 1

Yes

greentea is a string that ends with tea.

Sample Input 2

6
coffee

Sample Output 2

No

coffee is not a string that ends with tea.

Sample Input 3

3
tea

Sample Output 3

Yes

Sample Input 4

1
t

Sample Output 4

No

Problem Statement

Takahashi is health-conscious and concerned about whether he is getting enough of M types of nutrients from his diet.

For the i-th nutrient, his goal is to take at least A_i units per day.

Today, he ate N foods, and from the i-th food, he took X_{i,j} units of nutrient j.

Determine whether he has met the goal for all M types of nutrients.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 0 \leq A_i, X_{i,j} \leq 10^7
• All input values are integers.

Sample Input 1

2 3
10 20 30
20 0 10
0 100 100

Sample Output 1

Yes

For nutrient 1, Takahashi took 20 units from the 1-st food and 0 units from the 2-nd food, totaling 20 units, thus meeting the goal of taking at least 10 units.
Similarly, he meets the goal for nutrients 2 and 3.

Sample Input 2

2 4
10 20 30 40
20 0 10 30
0 100 100 0

Sample Output 2

No

The goal is not met for nutrient 4.

Problem Statement

You are given a positive integer X.

Find the minimum value among all positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X (without leading zeros) such that there is no leading zero.

Constraints

• 1\leq X < 10^5
• X is an integer.

Sample Input 1

903

Sample Output 1

309

There are four positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X such that there is no leading zero: 903, 930, 309, 390; the minimum value among them is 309.

Sample Input 2

432

Sample Output 2

234

Sample Input 3

100

Sample Output 3

100

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

Constraints

• 1 \le |S| \le 8
• S consists of lowercase English letters.
• There are at least K distinct strings that are permutations of S.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

There are H \times W cookies in H rows and W columns.
The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter c_{i,j}.

We will perform the following procedure.

1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.

2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.

3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.

Find the number of cookies remaining at the end of the procedure.

Constraints

• 2 \leq H, W \leq 2000
• c_{i,j} is a lowercase English letter.

Sample Input 1

4 3
aaa
aaa
abc
abd

Sample Output 1

2

The procedure is performed as follows.

• 1. Mark the cookies in the first and second rows.
• 2. Mark the cookies in the first column.
• 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
.bc
.bd

• 1. Do nothing.
• 2. Mark the cookies in the second column.
• 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
..c
..d

• 1. Do nothing.
• 2. Do nothing.
• 3. No cookies are marked, so terminate the procedure.

The final number of cookies remaining is 2.

Sample Input 2

2 5
aaaaa
abcde

Sample Output 2

4

Sample Input 3

3 3
ooo
ooo
ooo

Sample Output 3

0

Problem Statement

You are given a sequence A=(A_0,A_1,\ldots,A_{N-1}) of length N.
There is an initially empty dish. Takahashi is going to repeat the following operation K times.

• Let X be the number of candies on the dish. He puts A_{(X\bmod N)} more candies on the dish. Here, X\bmod N denotes the remainder when X is divided by N.

Find how many candies are on the dish after the K operations.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq K \leq 10^{12}
• 1 \leq A_i\leq 10^6
• All values in input are integers.

Sample Input 1

5 3
2 1 6 3 1

Sample Output 1

11

The number of candies on the dish transitions as follows.

• In the 1-st operation, we have X=0, so A_{(0\mod 5)}=A_0=2 more candies will be put on the dish.
• In the 2-nd operation, we have X=2, so A_{(2\mod 5)}=A_2=6 more candies will be put on the dish.
• In the 3-rd operation, we have X=8, so A_{(8\mod 5)}=A_3=3 more candies will be put on the dish.

Thus, after the 3 operations, there will be 11 candies on the dish. Note that you must not print the remainder divided by N.

Sample Input 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

Sample Output 2

826617499998784056

The answer may not fit into a 32-bit integer type.

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

Takahashi is initially at square (1,1) with zero money.

When Takahashi is at square (i,j), he can perform one of the following in one action:

• Stay at the same square and increase his money by P_{i,j}.
• Pay R_{i,j} from his money and move to square (i,j+1).
• Pay D_{i,j} from his money and move to square (i+1,j).

He cannot make a move that would make his money negative or take him outside the grid.

If Takahashi acts optimally, how many actions does he need to reach square (N,N)?

Constraints

• 2 \leq N \leq 80
• 1 \leq P_{i,j} \leq 10^9
• 1 \leq R_{i,j},D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

It is possible to reach square (3,3) in eight actions as follows:

• Stay at square (1,1) and increase money by 1. His money is now 1.
• Pay 1 money and move to square (2,1). His money is now 0.
• Stay at square (2,1) and increase money by 3. His money is now 3.
• Stay at square (2,1) and increase money by 3. His money is now 6.
• Stay at square (2,1) and increase money by 3. His money is now 9.
• Pay 4 money and move to square (2,2). His money is now 5.
• Pay 3 money and move to square (3,2). His money is now 2.
• Pay 2 money and move to square (3,3). His money is now 0.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Sample Output 2

4000000004