Problem Statement

You are given a positive integer N.
Output the sum of all integers from 1 to N, that is, 1+2+\cdots+N.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

5

Sample Output 1

15

Since 1+2+3+4+5=15, output 15.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

29

Sample Output 3

435

Problem Statement

There are N boxes arranged in a row, and some of these boxes contain cookies.

The state of these boxes is represented by a string S of length N. Specifically, the i-th box (1\leq i \leq N) from the left contains one cookie if the i-th character of S is @, and is empty if it is ..

Over the next D days, Takahashi will choose and eat one cookie per day from among the cookies in these boxes.

Determine how many of the N boxes will be empty after D days have passed. (It can be proved that this value does not depend on which cookies Takahashi chooses each day.)

It is guaranteed that S contains at least D occurrences of @.

Constraints

• 1 \leq D \leq N \leq 100
• N and D are integers.
• S is a string of length N consisting of @ and ..
• S contains at least D occurrences of @.

Sample Input 1

5 2
.@@.@

Sample Output 1

4

For example, Takahashi might act as follows:

• Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. He chooses the cookie in the 2nd box to eat.
• Day 2: There are cookies in the 3rd and 5th boxes. He chooses the cookie in the 5th box to eat.
• After two days have passed, only the 3rd box from the left contains a cookie. Therefore, four out of the five boxes are empty.

Even though Takahashi might choose differently on each day than in this example, there will still be four empty boxes after two days. Therefore, the answer is 4.

Sample Input 2

3 3
@@@

Sample Output 2

3

Sample Input 3

10 4
@@@.@@.@@.

Sample Output 3

7

Problem Statement

N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.

For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.

The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.

More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.

Constraints

• N is an integer between 2 and 30, inclusive.
• M is an integer between 1 and 30, inclusive.
• S_i is a string of length M consisting of o and x.

Sample Input 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

Sample Output 1

5

The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.

On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.

Sample Input 2

3 2
ox
xo
xx

Sample Output 2

1

Sample Input 3

2 4
xxxx
oxox

Sample Output 3

0

Problem Statement

KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.

You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.

More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:

• 1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
• |S| < i \leq |T|.
• |T| < i \leq |S|.

Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.

Constraints

• S and T are strings of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

abcde
abedc

Sample Output 1

3

We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.

Sample Input 2

abcde
abcdefg

Sample Output 2

6

We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.

Sample Input 3

keyence
keyence

Sample Output 3

0

S and T are equal, so print 0.

Problem Statement

The decimal representation of 414 is 414, which is a palindrome. Also, the octal representation of 414 is 636, which is also a palindrome. Based on this, solve the following problem.

You are given positive integers A and N. Find the sum of all integers between 1 and N, inclusive, whose decimal representation and base-A representation are both palindromes.

Under the constraints of this problem, it can be proved that the answer is less than 2^{63}.

Constraints

• 2 \leq A \leq 9
• 1 \leq N \le 10^{12}
• All input values are integers.

Sample Input 1

8
1000

Sample Output 1

2155

The integers satisfying the condition are 1,2,3,4,5,6,7,9,121,292,333,373,414,585 (14 integers), and their sum is 2155.

Sample Input 2

8
999999999999

Sample Output 2

914703021014

Sample Input 3

6
999999999999

Sample Output 3

283958331810

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

There are N sleighs numbered 1,2,\ldots, N.

R_i reindeer are required to pull sleigh i.

Additionally, each reindeer can pull at most one sleigh. More precisely, \sum_{k=1}^{m} R_{i_k} reindeer are required to pull m sleighs i_1, i_2, \ldots, i_m.

Find the answer to Q queries of the following form:

• You are given an integer X. Determine the maximum number of sleighs that can be pulled when there are X reindeer.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq R_i \leq 10^9
• 1 \leq X \leq 2 \times 10^{14}
• All input values are integers.

Sample Input 1

4 3
5 3 11 8
16
7
1000

Sample Output 1

3
1
4

When there are 16 reindeer, sleighs 1,2,4 can be pulled.

It is impossible to pull four sleighs with 16 reindeer, so the answer to query 1 is 3.

Sample Input 2

6 6
1 2 3 4 5 6
1
2
3
4
5
6

Sample Output 2

1
1
2
2
2
3

Sample Input 3

2 2
1000000000 1000000000
200000000000000
1

Sample Output 3

2
0

Problem Statement

For a string S consisting of digits from 1 through 9, let f(S) be the string T obtained by the following procedure. (S_i denotes the i-th character of S.)

• Let T be an initially empty string.
• For i=1, 2, \dots, |S| - 1, perform the following operation:
  • Append n copies of S_i to the tail of T, where n is the value when S_{i+1} is interpreted as an integer.

For example, S = 313 yields f(S) = 3111 by the following steps.

• T is initially empty.
• For i=1, we have n = 1. Append one copy of 3 to T, which becomes 3.
• For i=2, we have n = 3. Append three copies of 1 to T, which becomes 3111.
• Terminate the procedure. We obtain T = 3111.

You are given a length-N string S consisting of digits from 1 through 9.
You repeat the following operation until the length of S becomes 1: replace S with f(S).
Find how many times, modulo 998244353, you perform the operation until you complete it. If you will repeat the operation indefinitely, print -1 instead.

Constraints

• 2 \leq N \leq 10^6
• S is a length-N string consisting of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

3
313

Sample Output 1

4

If S = 313, the length of S be comes 1 after four operations.

• We have f(S) = 3111. Replace S with 3111.
• We have f(S) = 311. Replace S with 311.
• We have f(S) = 31. Replace S with 31.
• We have f(S) = 3. Replace S with 3.
• Now that the length of S is 1, terminate the repetition.

Sample Input 2

9
123456789

Sample Output 2

-1

If S = 123456789, you indefinitely repeat the operation. In this case, -1 should be printed.

Sample Input 3

2
11

Sample Output 3

1

Problem Statement

You will play a game against a dealer. The game uses a D-sided die (dice) that shows an integer from 1 to D with equal probability, and two variables x and y initialized to 0. The game proceeds as follows:

• You may perform the following operation any number of times: roll the die and add the result to x. You can choose whether to continue rolling or not after each roll.

• Then, the dealer will repeat the following operation as long as y < L: roll the die and add the result to y.

• If x > N, you lose. Otherwise, you win if y > N or x > y and lose if neither is satisfied.

Determine the probability of your winning when you act in a way that maximizes the probability of winning.

Constraints

• All inputs are integers.
• 1 \leq L \leq N \leq 2 \times 10^5
• 1 \leq D \leq N

Sample Input 1

3 2 2

Sample Output 1

0.468750000000000

It can be proved that the optimal strategy is to continue rolling as long as x is not greater than 2.

Sample Input 2

200000 200000 200000

Sample Output 2

0.999986408692793