Problem Statement

There is a row of N people. They are described by a string S of length N. The i-th person from the front is male if the i-th character of S is M, and female if it is F.

Determine whether the men and women are alternating.

It is said that the men and women are alternating if and only if there is no position where two men or two women are adjacent.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is a string of length N consisting of M and F.

Sample Input 1

6
MFMFMF

Sample Output 1

Yes

There is no position where two men or two women are adjacent, so the men and women are alternating.

Sample Input 2

9
FMFMMFMFM

Sample Output 2

No

Sample Input 3

1
F

Sample Output 3

Yes

Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

• S is a string of length 4 consisting of 0 and 1.

Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.

Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111

Problem Statement

You are given a positive integer M. Find a positive integer N and a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) that satisfy all of the following conditions:

• 1 \le N \le 20
• 0 \le A_i \le 10 (1 \le i \le N)
• \displaystyle \sum_{i=1}^N 3^{A_i} = M

It can be proved that under the constraints, there always exists at least one such pair of N and A satisfying the conditions.

Constraints

• 1 \le M \le 10^5

Sample Input 1

6

Sample Output 1

2
1 1

For example, with N=2 and A=(1,1), we have \displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6, satisfying all conditions.

Another example is N=4 and A=(0,0,1,0), which also satisfies the conditions.

Sample Input 2

100

Sample Output 2

4
2 0 2 4

Sample Input 3

59048

Sample Output 3

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

Note the condition 1 \le N \le 20.

Problem Statement

Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.

He was typing while looking only at the keyboard, not the screen.

Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.

He did not mistakenly press any keys other than those for lowercase English letters.

The characters in T that were not mistakenly typed are called correctly typed characters.

Determine the positions in T of the correctly typed characters.

Constraints

• S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
• T is a string obtained by the procedure described in the problem statement.

Sample Input 1

abc
axbxyc

Sample Output 1

1 3 6

The sequence of Takahashi's typing is as follows:

• Type a.
• Try to type b but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Type b.
• Try to type c but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Try to type c but mistakenly type y.
• Press the backspace key, but the character is not deleted.
• Type c.

The correctly typed characters are the first, third, and sixth characters.

Sample Input 2

aaaa
bbbbaaaa

Sample Output 2

5 6 7 8

Sample Input 3

atcoder
atcoder

Sample Output 3

1 2 3 4 5 6 7

Takahashi did not mistakenly type any characters.

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

• N is an integer.
• 1 \le N < 10^{18}

Sample Input 1

16

Sample Output 1

73

• For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
  • Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
• For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
  • Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

238

Sample Output 2

13870

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• 1 \leq N \leq 200000
• 1 \leq S_i,T_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27

Problem Statement

Takahashi is displaying a sentence with N words in a window. All words have the same height, and the width of the i-th word (1\leq i\leq N) is L _ i.

The words are displayed in the window separated by a space of width 1. More precisely, when the sentence is displayed in a window of width W, the following conditions are satisfied.

• The sentence is divided into several lines.
• The first word is displayed at the beginning of the top line.
• The i-th word (2\leq i\leq N) is displayed either with a gap of 1 after the (i-1)-th word, or at the beginning of the line below the line containing the (i-1)-th word. It will not be displayed anywhere else.
• The width of each line does not exceed W. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into M or fewer lines. Find the minimum possible width of the window.

Constraints

• 1\leq M\leq N\leq2\times10 ^ 5
• 1\leq L _ i\leq10^9\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

Sample Output 1

26

When the width of the window is 26, you can fit the given sentence into three lines as follows.

You cannot fit the given sentence into three lines when the width of the window is 25 or less, so print 26.

Note that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.

Sample Input 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000009

Note that the answer may not fit into a 32\operatorname{bit} integer.

Sample Input 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

Sample Output 3

189

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the cell at the i-th row (1\leq i\leq H) from the top and j-th column (1\leq j\leq W) from the left.

Initially, there is a slime with strength S _ {i,j} in cell (i,j), and Takahashi is the slime in the cell (P,Q).

Find the maximum possible strength of Takahashi after performing the following action any number of times (possibly zero):

• Among the slimes adjacent to him, choose one whose strength is strictly less than \dfrac{1}{X} times his strength and absorb it. As a result, the absorbed slime disappears, and Takahashi's strength increases by the strength of the absorbed slime.

When performing the above action, the gap left by the disappeared slime is immediately filled by Takahashi, and the slimes that were adjacent to the disappeared one (if any) become newly adjacent to Takahashi (refer to the explanation in sample 1).

Constraints

• 1\leq H,W\leq500
• 1\leq P\leq H
• 1\leq Q\leq W
• 1\leq X\leq10^9
• 1\leq S _ {i,j}\leq10^{12}
• All input values are integers.

Sample Input 1

3 3 2
2 2
14 6 9
4 9 20
17 15 7

Sample Output 1

28

Initially, the strength of the slime in each cell is as follows:

For example, Takahashi can act as follows:

• Absorb the slime in cell (2,1). His strength becomes 9+4=13, and the slimes in cells (1,1) and (3,1) become newly adjacent to him.
• Absorb the slime in cell (1,2). His strength becomes 13+6=19, and the slime in cell (1,3) becomes newly adjacent to him.
• Absorb the slime in cell (1,3). His strength becomes 19+9=28.

After these actions, his strength is 28.

No matter how he acts, it is impossible to get a strength greater than 28, so print 28.

Note that Takahashi can only absorb slimes whose strength is strictly less than half of his strength. For example, in the figure on the right above, he cannot absorb the slime in cell (1,1).

Sample Input 2

3 4 1
1 1
5 10 1 1
10 1 1 1
1 1 1 1

Sample Output 2

5

He cannot absorb any slimes.

Sample Input 3

8 10 2
1 5
388 130 971 202 487 924 247 286 237 316
117 166 918 106 336 928 493 391 235 398
124 280 425 955 212 988 227 222 307 226
336 302 478 246 950 368 291 236 170 101
370 200 204 141 287 410 388 314 205 460
291 104 348 337 404 399 416 263 415 339
105 420 302 334 231 481 466 366 401 452
119 432 292 403 371 417 351 231 482 184

Sample Output 3

1343

Problem Statement

There is a directed graph with N vertices and M edges. Each edge has two positive integer values: beauty and cost.

For i = 1, 2, \ldots, M, the i-th edge is directed from vertex u_i to vertex v_i, with beauty b_i and cost c_i. Here, the constraints guarantee that u_i \lt v_i.

Find the maximum value of the following for a path P from vertex 1 to vertex N.

• The total beauty of all edges on P divided by the total cost of all edges on P.

Here, the constraints guarantee that the given graph has at least one path from vertex 1 to vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• 1 \leq b_i, c_i \leq 10^4
• There is a path from vertex 1 to vertex N.
• All input values are integers.

Sample Input 1

5 7
1 2 3 6
1 3 9 5
2 3 1 5
2 4 5 3
2 5 1 9
3 4 4 8
4 5 2 7

Sample Output 1

0.7500000000000000

For the path P that passes through the 2-nd, 6-th, and 7-th edges in this order and visits vertices 1 \rightarrow 3 \rightarrow 4 \rightarrow 5, the total beauty of all edges on P divided by the total cost of all edges on P is (b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75, and this is the maximum possible value.

Sample Input 2

3 3
1 3 1 1
1 3 2 1
1 3 3 1

Sample Output 2

3.0000000000000000

Sample Input 3

10 20
3 4 1 2
7 9 4 5
2 4 4 5
4 5 1 4
6 9 4 1
9 10 3 2
6 10 5 5
5 6 1 2
5 6 5 2
2 3 2 3
6 10 4 4
4 6 3 4
4 8 4 1
3 5 3 2
2 4 3 2
3 5 4 2
1 5 3 4
1 2 4 2
3 7 2 2
7 8 1 3

Sample Output 3

1.8333333333333333