Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

• abc is a 3-digit integer abc none of whose digits is 0.

Sample Input 1

123

Sample Output 1

666

We have 123+231+312=666.

Sample Input 2

999

Sample Output 2

2997

We have 999+999+999=2997.

Problem Statement

You are given a positive integer N and a sequence of positive integers A = (A_1,A_2,\dots,A_N) of length N.

Determine whether A is strictly increasing, that is, whether A_i < A_{i+1} holds for every integer i with 1 \leq i < N.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 1000 \ (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3
1 2 5

Sample Output 1

Yes

A_1 < A_2 and A_2 < A_3, so A is strictly increasing.

Sample Input 2

3
3 9 5

Sample Output 2

No

A_1 < A_2, but A_2 < A_3 does not hold, so A is not strictly increasing.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

No

A_1 < A_2 does not hold, so A is not strictly increasing.

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

Constraints

• 1 \leq K \leq N \leq 100
• K and N are integers.
• S_i is a string of length 10 consisting of lowercase English letters.
• S_i \neq S_j if i \neq j.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

• First, choose an integer i between 1 and N-1, inclusive.
• Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
  • Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

• All input values are integers.
• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq T_i \leq S_i \leq 10^9

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
• Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
• Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45

Problem Statement

You are given positive integers N and K. Define a sequence A = (A_0, A_1, \ldots, A_N) of length N+1 as follows:

• A_i = 1 for 0 \le i < K;
• A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1} for K \le i.

Find A_N modulo 10^9.

Constraints

• 1 \le N, K \le 10^{6}
• All input values are integers.

Sample Input 1

4 2

Sample Output 1

5

We have A_0 = A_1 = 1, and A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5.

Sample Input 2

10 20

Sample Output 2

1

Sample Input 3

1000000 500000

Sample Output 3

420890625

Remember to print A_N modulo 10^9.

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

• if the i-th character of S is 0, he has no plan scheduled for the i-th day;
• if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
• if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• 1\leq M\leq N\leq 1000
• S is a string of length N consisting of 0, 1, and 2.
• N and M are integers.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

Problem Statement

We have a string S. Initially, S= 1.
Process Q queries in the following formats in order.

• 1 x : Append a digit x at the end of S.
• 2 : Delete the digit at the beginning of S.
• 3 : Print the number represented by S in decimal, modulo 998244353.

Constraints

• 1 \leq Q \leq 6 \times 10^5
• For each query in the first format, x \in \{1,2,3,4,5,6,7,8,9\}.
• A query in the second format is given only if S has a length of 2 or greater.
• There is at least one query in the third format.

Sample Input 1

3
3
1 2
3

Sample Output 1

1
12

In the first query, S is 1, so you should print 1 modulo 998244353, that is, 1.
In the second query, S becomes 12.
In the third query, S is 12, so you should print 12 modulo 998244353, that is, 12.

Sample Input 2

3
1 5
2
3

Sample Output 2

5

Sample Input 3

11
1 9
1 9
1 8
1 2
1 4
1 4
1 3
1 5
1 3
2
3

Sample Output 3

0

Be sure to print numbers modulo 998244353.

Problem Statement

Given is a positive integer N. Find the value \displaystyle\sum_{i=1}^N \left[ \frac{N}{i} \right].

Here, for a real number x, [x] denotes the largest integer not exceeding x.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

3

Sample Output 1

5

We have \left[ \frac{3}{1} \right]+\left[ \frac{3}{2} \right]+\left[ \frac{3}{3} \right]=3+1+1=5.

Sample Input 2

10000000000

Sample Output 2

231802823220

Note that the input and output may not fit into a 32-bit integer type.

Problem Statement

For a string X of length n, let f(X,k) denote the string obtained by repeating k times the string X, and g(X,k) denote the string obtained by repeating k times the first character, the second character, \dots, the n-th character of X, in this order. For example, if X= abc, then f(X,2)= abcabc, and g(X,3)= aaabbbccc. Also, for any string X, both f(X,0) and g(X,0) are empty strings.

You are given a positive integer N and strings S and T. Find the largest non-negative integer k such that g(T,k) is a (not necessarily contiguous) subsequence of f(S,N). Note that g(T,0) is always a subsequence of f(S,N) by definition.

Constraints

• N is an integer.
• 1\leq N\leq 10^{12}
• S and T are strings consisting of lowercase English letters with lengths between 1 and 10^5, inclusive.

Sample Input 1

3
abc
ab

Sample Output 1

2

We have f(S,3)= abcabcabc. g(T,2)= aabb is a subsequence of f(S,3), but g(T,3)= aaabbb is not, so print 2.

Sample Input 2

3
abc
arc

Sample Output 2

0

Sample Input 3

1000000000000
kzazkakxkk
azakxk

Sample Output 3

344827586207