Problem Statement

You are given a string S consisting of uppercase and lowercase English letters. Print the string obtained by concatenating only the uppercase letters of S in their original order.

Constraints

• S is a string of uppercase and lowercase English letters.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

AtCoderBeginnerContest

Sample Output 1

ACBC

The string obtained by concatenating only the uppercase letters of S in their original order is ACBC. Hence, print ACBC.

Sample Input 2

PaymentRequired

Sample Output 2

PR

Sample Input 3

program

Sample Output 3

Note that S may contain no uppercase letters.

Problem Statement

Takahashi had his N-th birthday, when he was T centimeters tall.
Additionally, we know the following facts:

• In each year between Takahashi's birth (0-th birthday) and his X-th birthday, his height increased by D centimeters. More formally, for each i = 1, 2, \ldots, X, his height increased by D centimeters between his (i-1)-th birthday and his i-th birthday.
• Between Takahashi's X-th birthday and his N-th birthday, his height did not change.

Find Takahashi's height on his M-th birthday, in centimeters.

Constraints

• 0 \leq M \lt N \leq 100
• 1 \leq X \leq N
• 1 \leq T \leq 200
• 1 \leq D \leq 100
• Takahashi was at least 1 centimeter tall at his birth.
• All values in input are integers.

Sample Input 1

38 20 17 168 3

Sample Output 1

168

In this sample, Takahashi was 168 centimeters tall on his 38-th birthday. Also, his height did not change between his 17-th birthday and 38-th birthday.
From these facts, we find that he was 168 centimeters tall on his 20-th birthday, so the answer is 168.

Sample Input 2

1 0 1 3 2

Sample Output 2

1

In this sample, Takahashi was 1 centimeter tall on his 0(=M)-th birthday and 3(=T) centimeters tall on his 1(=N)-st birthday.

Sample Input 3

100 10 100 180 1

Sample Output 3

90

Problem Statement

There is a grid with H rows and W columns. Takahashi is going to paint each cell of this grid black or white.

He paints all cells on the border of the grid black, and all other cells white. Output the grid after he has painted it.

Constraints

• 3\le H\le10
• 3\le W\le10
• All input values are integers.

Sample Input 1

4 5

Sample Output 1

#####
#...#
#...#
#####

For example, cell (1,1) is on the border. This is because there are only two cells edge-adjacent to cell (1,1): cells (1,2) and (2,1). Thus, cell (1,1) is painted black, so the first character of the first line should be #.

Conversely, for example, cell (3,4) is not on the border. This is because there are four cells edge-adjacent to cell (3,4): cells (2,4), (3,3), (3,5), and (4,4). Thus, cell (3,4) is painted white, so the fourth character of the third line should be ..

Sample Input 2

5 6

Sample Output 2

######
#....#
#....#
#....#
######

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.

Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq T_i \leq 10^9
• 0 \leq K_i < i
• 1 \leq A_{i,j} < i
• \sum_{i=1}^N K_i \leq 2\times 10^5
• A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} are all distinct.
• All values in input are integers.

Sample Input 1

3
3 0
5 1 1
7 1 1

Sample Output 1

10

Here is one possible plan for Takahashi.

• At time 0, start practicing for Move 1 to learn Move 1 at time 3.
• Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.

Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.

Sample Input 2

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

Sample Output 2

5000000000

Note that the answer may not fit into a 32-bit integer.