Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

• S is a string consisting of v and w.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

vvwvw

Sample Output 1

7

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12

Problem Statement

In the hexadecimal system, where the digits ABCDEF corresponding to 10,11,12,13,14, and 15 are used in addition to 0123456789, every integer between 0 and 255 is represented as a 1- or 2-digit numeral.
For example, 0 and 12 are represented as 1-digit hexadecimal numerals 0 and C; 99 and 255 are represented as 2-digit hexadecimals 63 and FF.

Given an integer N between 0 and 255, convert it to an exactly two-digit hexadecimal numeral, prepending leading 0s if necessary.

Notes

The judge is case-sensitive. Specifically, you cannot use abcdef as hexadecimal digits instead of ABCDEF.

Constraints

• 0 \leq N \leq 255
• N is an integer.

Sample Input 1

99

Sample Output 1

63

99 is represented as 63 in hexadecimal.

Sample Input 2

12

Sample Output 2

0C

12 is represented as C in hexadecimal.
Since we ask you to convert it to a two-digit hexadecimal numeral, the answer is 0C, where 0 is prepended to C.

Sample Input 3

0

Sample Output 3

00

Sample Input 4

255

Sample Output 4

FF

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.

Takahashi is initially standing on the leftmost platform.

Since he likes heights, he will repeat the following move as long as possible.

• If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.

Find the height of the final platform he will stand on.

Constraints

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

Sample Input 1

5
1 5 10 4 2

Sample Output 1

10

Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.

He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.

He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.

Thus, the height of the final platform Takahashi will stand on is 10.

Sample Input 2

3
100 1000 100000

Sample Output 2

100000

Sample Input 3

4
27 1828 1828 9242

Sample Output 3

1828

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

• C[a][b] is #.
• C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
• At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

• 3 \leq H, W \leq 100
• C[i][j] is # or ..
• No two different squares that comprise two different crosses share a corner.
• H and W are integers.

Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Problem Statement

Takahashi is a cashier.

There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The cash register initially displays 0. Whenever he types the key 00, the displayed number is multiplied by 100; whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.

Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?

Constraints

• 1\leq S\leq 10^{100000}
• S is an integer.

Sample Input 1

40004

Sample Output 1

4

For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.

• Type the key 4. It now displays 4.
• Type the key 00. It now displays 400.
• Type the key 0. It now displays 4000.
• Type the key 4. It now displays 40004.

He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.

Sample Input 2

1355506027

Sample Output 2

10

Sample Input 3

10888869450418352160768000001

Sample Output 3

27

Note that S may not fit into a 64-\operatorname{bit} integer type.

Problem Statement

We have a video game consisting of N stages. The i-th stage (1 \leq i \leq N) is composed of a movie lasting A_i minutes and gameplay lasting B_i minutes.

To clear the i-th stage for the first time, one must watch the movie and do the gameplay for that stage. For the second and subsequent times, one may skip the movie and do just the gameplay.

In the beginning, only the 1-st stage is unlocked, and clearing the i-th stage (1 \leq i \leq N - 1) unlocks the (i+1)-th stage.

Find the shortest time needed to clear a stage X times in total. Here, if the same stage is cleared multiple times, all of them count.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9 \, (1 \leq i \leq N)
• 1 \leq X \leq 10^9
• All values in input are integers.

Sample Input 1

3 4
3 4
2 3
4 2

Sample Output 1

18

Here is one way to clear a stage 4 times in 18 minutes:

• Clear Stage 1. It takes A_1 + B_1 = 7 minutes.
• Clear Stage 2. It takes A_2 + B_2 = 5 minutes.
• Clear Stage 2 again. It takes B_2= 3 minutes.
• Clear Stage 2 again. It takes B_2= 3 minutes.

It is impossible to clear a stage 4 times within 17 minutes.

Sample Input 2

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

Sample Output 2

1000000076

Problem Statement

You are given an undirected graph consisting of N vertices and M edges.
For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertex u_i and v_i that is initially passable if a_i = 1 and initially impassable if a_i = 0. Additionally, there are switches on K of the vertices: vertex s_1, vertex s_2, \ldots, vertex s_K.

Takahashi is initially on vertex 1, and will repeat performing one of the two actions below, Move or Hit Switch, which he may choose each time, as many times as he wants.

• Move: Choose a vertex adjacent to the vertex he is currently on via an edge, and move to that vertex.
• Hit Switch: If there is a switch on the vertex he is currently on, hit it. This will invert the passability of every edge in the graph. That is, a passable edge will become impassable, and vice versa.

Determine whether Takahashi can reach vertex N, and if he can, print the minimum possible number of times he performs Move before reaching vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• a_i \in \lbrace 0, 1\rbrace
• 1 \leq s_1 \lt s_2 \lt \cdots \lt s_K \leq N
• All values in the input are integers.

Sample Input 1

5 5 2
1 3 0
2 3 1
5 4 1
2 1 1
1 4 0
3 4

Sample Output 1

5

Takahashi can reach vertex N as follows.

• Move from vertex 1 to vertex 2.
• Move from vertex 2 to vertex 3.
• Hit the switch on vertex 3. This inverts the passability of every edge in the graph.
• Move from vertex 3 to vertex 1.
• Move from vertex 1 to vertex 4.
• Hit the switch on vertex 4. This again inverts the passability of every edge in the graph.
• Move from vertex 4 to vertex 5.

Here, Move is performed five times, which is the minimum possible number.

Sample Input 2

4 4 2
4 3 0
1 2 1
1 2 0
2 1 1
2 4

Sample Output 2

-1

The given graph may be disconnected or contain multi-edges. In this sample input, there is no way for Takahashi to reach vertex N, so you should print -1.

Problem Statement

Given is a sequence A of length N. You can do this operation any number of times: when the length of the sequence is at least 2, choose two adjacent values, delete them, and insert their sum where they were. How many sequences can result from zero or more operations? Find the count modulo 998244353.

Constraints

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

Sample Input 1

3
1 -1 1

Sample Output 1

4

The following four sequences can result from zero or more operations.

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

Sample Input 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

Sample Output 2

321