Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

• 100 \le N \le 999
• N is an integer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.

Problem Statement

Takahashi decided to make takoyaki (octopus balls) and serve it to Snuke. Takahashi instructed Snuke to raise only his left hand if he wants to eat takoyaki, and only his right hand otherwise.

You are given the information about which hand Snuke is raising as two integers L and R. He is raising his left hand if and only if L = 1, and raising his right hand if and only if R = 1. He might not follow the instructions and could raise both hands or not raise any hand at all.

If Snuke is raising only one hand, print Yes if he wants to eat takoyaki, and No if he does not. If he is raising both hands or not raising any hand, print Invalid.

Assume that if Snuke is raising only one hand, he is always following the instructions.

Constraints

• Each of L and R is 0 or 1.

Sample Input 1

1 0

Sample Output 1

Yes

Snuke wants to eat takoyaki, so he is raising only his left hand.

Sample Input 2

1 1

Sample Output 2

Invalid

Snuke is raising both hands.

Problem Statement

A string S consisting of lowercase English letters is a good string if and only if it satisfies the following property for all integers i not less than 1:

• There are exactly zero or exactly two different letters that appear exactly i times in S.

Given a string S, determine if it is a good string.

Constraints

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

Sample Input 1

commencement

Sample Output 1

Yes

For the string commencement, the number of different letters that appear exactly i times is as follows:

• i=1: two letters (o and t)
• i=2: two letters (c and n)
• i=3: two letters (e and m)
• i\geq 4: zero letters

Therefore, commencement satisfies the condition of a good string.

Sample Input 2

banana

Sample Output 2

No

For the string banana, there is only one letter that appears exactly one time, which is b, so it does not satisfy the condition of a good string.

Sample Input 3

ab

Sample Output 3

Yes

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

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

• 1 \le M \le N \le 2 \times 10^5
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

15

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

31

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

There is a maze consisting of a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. The type of cell (i,j) is given as a character S_{i,j}, where each character has the following meaning:

• . : Empty cell
• # : Obstacle cell
• Lowercase English letter (a - z): Warp cell

In the maze, you can perform the following two types of actions any number of times in any order:

• Walk: Move from the current cell to a cell that is one cell away in one of the four directions (up, down, left, right). However, you cannot move to an obstacle cell or outside the grid.
• Warp: When you are at a warp cell, move to any warp cell with the same character written on it.

Determine whether it is possible to move from cell (1,1) to cell (H,W), and if possible, find the minimum total number of actions required.

Constraints

• 1\leq H,W \leq 1000
• H\times W \geq 2
• H and W are integers.
• S_{i,j} is ., #, or a lowercase English letter.
• S_{1,1}\neq #
• S_{H,W}\neq #

Sample Input 1

3 4
..a.
####
ba#b

Sample Output 1

5

You can move from cell (1,1) to cell (3,4) by performing actions as follows:

1. Move from cell (1,1) to cell (1,2) by walking.
2. Move from cell (1,2) to cell (1,3) by walking.
3. Move from cell (1,3) to cell (3,2) by warping.
4. Move from cell (3,2) to cell (3,1) by walking.
5. Move from cell (3,1) to cell (3,4) by warping.

The total number of actions is 5, which is the minimum.

Sample Input 2

3 4
..a.
####
b.#b

Sample Output 2

-1

It is impossible to move from cell (1,1) to cell (3,4).

Sample Input 3

4 4
xxxx
xxxx
xxxx
xxxx

Sample Output 3

1

Sample Input 4

7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.

Sample Output 4

12

Problem Statement

Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).

Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:

• A'_1 \leq A'_k.

Since the count can be enormous, print it modulo 998244353.

Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 2 1

Sample Output 1

3

A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).

Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.

Sample Input 2

3
1 2 2

Sample Output 2

4

Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.

Sample Input 3

3
3 2 1

Sample Output 3

0

There may be no subsequence that satisfies the condition.

Sample Input 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

Sample Output 4

830

Problem Statement

AtCoder Island has N species of cicadas. Cicadas of species i (1 \leq i \leq N) have mass outbreaks only in years that are multiples of A_i.

Among the Y years from year 1 to year Y, find how many years have mass outbreaks of exactly M species of cicadas.

Constraints

• 1 \leq M \leq N \leq 20
• 1 \leq Y \leq 10^{18}
• 1 \leq A_i \leq 10^{18} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 2 16
4 2 3

Sample Output 1

4

From years 1 to 16, each species of cicada has mass outbreaks in the following years:

• Species 1 cicadas have mass outbreaks in years 4,8,12,16.
• Species 2 cicadas have mass outbreaks in years 2,4,6,8,10,12,14,16.
• Species 3 cicadas have mass outbreaks in years 3,6,9,12,15.

From years 1 to 16, exactly two species of cicadas have mass outbreaks four times in years 4,6,8,16.

Sample Input 2

2 1 122333444422333
1429 73651

Sample Output 2

87266392324

The answer may not fit in a 32-bit integer.

Sample Input 3

20 3 832725971730072237
19639596380058 49098990950145 32732660633430 114564312217005 68738587330203 45825724886802 252041486877411 180029633483865 108017780090319 72011853393546 468077047058049 297867211764213 212762294117295 127657376470377 85104917646918 723391799998803 612100753845141 389518661537817 278227615384155 166936569230493

Sample Output 3

24231

Input values may not fit in a 32-bit integer.