Problem Statement

You are given a string S of length between 1 and 25 consisting of lowercase English letters.
Output one lowercase English letter that does not appear in S.
If there are multiple such letters, you may output any one of them.

Constraints

• S is a string of length between 1 and 25 (inclusive) consisting of lowercase English letters.

Sample Input 1

a

Sample Output 1

d

S= a.
Any lowercase English letter other than a (that is, b, c, …, or z) is a correct answer.

Sample Input 2

abcdfhijklmnopqrstuvwxyz

Sample Output 2

e

The lowercase English letters not included in S are e and g.

Sample Input 3

qazplwsxokmedcijnrfvuhbgt

Sample Output 3

y

Problem Statement

Takahashi is enjoying a game at school. The game starts at the moment the bell rings.

Immediately after the bell rings, he repeats the following actions:

• Run at a speed of S meters per second for A seconds. Then, remain stationary for B seconds.

How many meters in total does he run by the time X seconds have elapsed since the bell rang?

Constraints

• 1 \leq S \leq 15
• 1 \leq A \leq 1000
• 1 \leq B \leq 1000
• 1 \leq X \leq 1000
• All input values are integers.

Sample Input 1

7 3 2 11

Sample Output 1

49

During the 11 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 3 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
• From 3 seconds to 5 seconds, he remains stationary.
• From 5 seconds to 8 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
• From 8 seconds to 10 seconds, he remains stationary.
• From 10 seconds to 11 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 7 meters.

The total distance traveled is 49 meters, so output 49.

Sample Input 2

6 3 2 9

Sample Output 2

36

During the 9 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 3 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
• From 3 seconds to 5 seconds, he remains stationary.
• From 5 seconds to 8 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
• From 8 seconds to 9 seconds, he remains stationary.

The total distance traveled is 36 meters, so output 36.

Sample Input 3

1 1 666 428

Sample Output 3

1

During the 428 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 1 second, he runs at a speed of 1 meter per second. The distance traveled during this time is 1 meter.
• From 1 second to 428 seconds, he remains stationary.

The total distance traveled is 1 meter, so output 1.

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 1000
• All input values are integers.
• The lost integer is uniquely determined.

Sample Input 1

3
2 3 5

Sample Output 1

4

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

7

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

151

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

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.