Problem Statement

Takahashi has recorded the number of steps he walked for N weeks. He walked A_i steps on the i-th day.

Find the total number of steps Takahashi walked each week.
More precisely, find the sum of the steps for the first week (the 1-st through 7-th day), the sum of the steps for the second week (the 8-th through 14-th day), and so on.

Constraints

• 1 \leq N \leq 10
• 0 \leq A_i \leq 10^5
• All input values are integers.

Sample Input 1

2
1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000

Sample Output 1

28000 35000

For the first week, he walked 1000+2000+3000+4000+5000+6000+7000=28000 steps, and for the second week, he walked 2000+3000+4000+5000+6000+7000+8000=35000 steps.

Sample Input 2

3
14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148

Sample Output 2

314333 419427 335328

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.

The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.

Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.

1. Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
2. Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.

Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.

• The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
• The cut-out sheet coincides sheet X without rotating or flipping.

Constraints

• 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
• H_A, W_A, H_B, W_B, H_X, W_X are integers.
• A_i is a string of length W_A consisting of . and #.
• B_i is a string of length W_B consisting of . and #.
• X_i is a string of length W_X consisting of . and #.
• Sheets A, B, and X each contain at least one black square.

Sample Input 1

3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...

Sample Output 1

Yes

First, paste sheet A onto sheet C, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots.......\cdots
  ..#....  
  .......  
     \vdots

Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots..#....\cdots
  ..#....  
  .......  
     \vdots

Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.

...
#.#
.#.
.#.
...

This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.

Therefore, print Yes.

Sample Input 2

2 2
#.
.#
2 2
#.
.#
2 2
##
##

Sample Output 2

No

Note that sheets A and B may not be rotated or flipped when pasting them.

Sample Input 3

1 1
#
1 2
##
1 1
#

Sample Output 3

No

No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition. Therefore, print No.

Sample Input 4

3 3
###
...
...
3 3
#..
#..
#..
3 3
..#
..#
###

Sample Output 4

Yes

Problem Statement

You are given a string S of length N consisting of lowercase English letters and the characters ( and ).
Print the string S after performing the following operation as many times as possible.

• Choose and delete a contiguous substring of S that starts with (, ends with ), and does not contain ( or ) other than the first and last characters.

It can be proved that the string S after performing the operation as many times as possible is uniquely determined without depending on how it is performed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• S is a string of length N consisting of lowercase English letters and the characters ( and ).

Sample Input 1

8
a(b(d))c

Sample Output 1

ac

Here is one possible procedure, after which S will be ac.

• Delete the substring (d) formed by the fourth to sixth characters of S, making it a(b)c.
• Delete the substring (b) formed by the second to fourth characters of S, making it ac.
• The operation can no longer be performed.

Sample Input 2

5
a(b)(

Sample Output 2

a(

Sample Input 3

2
()

Sample Output 3

The string S after the procedure may be empty.

Sample Input 4

6
)))(((

Sample Output 4

)))(((

Problem Statement

There are N people numbered from 1 to N standing in a circle. Person 1 is to the right of person 2, person 2 is to the right of person 3, ..., and person N is to the right of person 1.

We will give each of the N people an integer between 0 and M-1, inclusive.
Among the M^N ways to distribute integers, find the number, modulo 998244353, of such ways that no two adjacent people have the same integer.

Constraints

• 2 \leq N,M \leq 10^6
• N and M are integers.

Sample Input 1

3 3

Sample Output 1

6

There are six desired ways, where the integers given to persons 1,2,3 are (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).

Sample Input 2

4 2

Sample Output 2

2

There are two desired ways, where the integers given to persons 1,2,3,4 are (0,1,0,1),(1,0,1,0).

Sample Input 3

987654 456789

Sample Output 3

778634319

Be sure to find the number modulo 998244353.

Problem Statement

There are N rooms numbered 1, 2, \ldots, N, each with one person living in it, and M corridors connecting two different rooms. The i-th corridor connects room U_i and room V_i with a length of W_i.

One day (we call this day 0), the K people living in rooms A_1, A_2, \ldots, A_K got (newly) infected with a virus. Furthermore, on the i-th of the following D days (1\leq i\leq D), the infection spread as follows.

People who were infected at the end of the night of day (i-1) remained infected at the end of the night of day i.
For those who were not infected, they were newly infected if and only if they were living in a room within a distance of X_i from at least one room where an infected person was living at the end of the night of day (i-1). Here, the distance between rooms P and Q is defined as the minimum possible sum of the lengths of the corridors when moving from room P to room Q using only corridors. If it is impossible to move from room P to room Q using only corridors, the distance is set to 10^{100}.

For each i (1\leq i\leq N), print the day on which the person living in room i was newly infected. If they were not infected by the end of the night of day D, print -1.

Constraints

• 1 \leq N\leq 3\times 10^5
• 0 \leq M\leq 3\times 10^5
• 1 \leq U_i < V_i\leq N
• All (U_i,V_i) are different.
• 1\leq W_i\leq 10^9
• 1 \leq K\leq N
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1 \leq D\leq 3\times 10^5
• 1\leq X_i\leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
1
2

The infection spreads as follows.

• On the night of day 0, the person living in room 1 gets infected.
• The distances between room 1 and rooms 2,3,4 are 2,3,5, respectively. Thus, since X_1=3, the people living in rooms 2 and 3 are newly infected on the night of day 1.
• The distance between rooms 3 and 4 is 2. Thus, since X_2=3, the person living in room 4 also gets infected on the night of day 2.

Therefore, the people living in rooms 1,2,3,4 were newly infected on days 0,1,1,2, respectively, so print 0,1,1,2 in this order on separate lines.

Sample Input 2

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

Sample Output 2

0
1
2
-1
2
0
-1

Sample Input 3

5 1
1 2 5
2
1 3
3
3 7 5

Sample Output 3

0
2
0
-1
-1

Note that it is not always possible to move between any two rooms using only corridors.

Problem Statement

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

Takahashi can perform the following two operations any number of times, possibly zero, in any order.

• Choose an integer i such that 1\leq i\leq N-1, and decrease A_i by 1 and increase A_{i+1} by 1.
• Choose an integer i such that 1\leq i\leq N-1, and increase A_i by 1 and decrease A_{i+1} by 1.

Find the minimum number of operations required to make the sequence A satisfy the following condition:

• \lvert A_i-A_j\rvert\leq 1 for any pair (i,j) of integers between 1 and N, inclusive.

Constraints

• 2 \leq N \leq 5000
• \lvert A_i \rvert \leq 10^9
• All input values are integers.

Sample Input 1

3
2 7 6

Sample Output 1

4

You can make A satisfy the condition with four operations as follows.

• Choose i=1, and increase A_1 by 1 and decrease A_2 by 1, making A=(3,6,6).
• Choose i=1, and increase A_1 by 1 and decrease A_2 by 1, making A=(4,5,6).
• Choose i=2, and increase A_2 by 1 and decrease A_3 by 1, making A=(4,6,5).
• Choose i=1, and increase A_1 by 1 and decrease A_2 by 1, making A=(5,5,5).

This is the minimum number of operations required, so print 4.

Sample Input 2

3
-2 -5 -2

Sample Output 2

2

You can make A satisfy the condition with two operations as follows:

• Choose i=1, and decrease A_1 by 1 and increase A_2 by 1, making A=(-3,-4,-2).
• Choose i=2, and increase A_2 by 1 and decrease A_3 by 1, making A=(-3,-3,-3).

This is the minimum number of operations required, so print 2.

Sample Input 3

5
1 1 1 1 -7

Sample Output 3

13

By performing the operations appropriately, with 13 operations you can make A=(0,0,-1,-1,-1), which satisfies the condition in the problem statement. It is impossible to satisfy it with 12 or fewer operations, so print 13.

Problem Statement

There is a length L string S consisting of uppercase and lowercase English letters displayed on an electronic bulletin board with a width of W. The string S scrolls from right to left by a width of one character at a time.

The display repeats a cycle of L+W-1 states, with the first character of S appearing from the right edge when the last character of S disappears from the left edge.

For example, when W=5 and S= ABC, the board displays the following seven states in a loop:

• ABC..
• BC...
• C....
• ....A
• ...AB
• ..ABC
• .ABC.

(. represents a position where no character is displayed.)

More precisely, there are distinct states for k=0,\ldots,L+W-2 in which the display is as follows.

• Let f(x) be the remainder when x is divided by L+W-1. The (i+1)-th position from the left of the board displays the (f(i+k)+1)-th character of S when f(i+k)<L, and nothing otherwise.

You are given a length W string P consisting of uppercase English letters, lowercase English letters, ., and _.
Find the number of states among the L+W-1 states of the board that coincide P except for the positions with _.
More precisely, find the number of states that satisfy the following condition.

• For every i=1,\ldots,W, one of the following holds.
  • The i-th character of P is _.
  • The character displayed at the i-th position from the left of the board is equal to the i-th character of P.
  • Nothing is displayed at the i-th position from the left of the board, and the i-th character of P is ..

Constraints

• 1 \leq L \leq W \leq 3\times 10^5
• L and W are integers.
• S is a string of length L consisting of uppercase and lowercase English letters.
• P is a string of length W consisting of uppercase and lowercase English letters, ., and _.

Sample Input 1

3 5
ABC
..___

Sample Output 1

3

There are three desired states, where the board displays ....A, ...AB, ..ABC.

Sample Input 2

11 15
abracadabra
__.._________ab

Sample Output 2

2

Sample Input 3

20 30
abaababbbabaabababba
__a____b_____a________________

Sample Output 3

2

Sample Input 4

1 1
a
_

Sample Output 4

1