Problem Statement

There are non-negative integers A, B, C, D, E, and F, which satisfy A\times B\times C\geq D\times E\times F.
Find the remainder when (A\times B\times C)-(D\times E\times F) is divided by 998244353.

Constraints

• 0\leq A,B,C,D,E,F\leq 10^{18}
• A\times B\times C\geq D\times E\times F
• A, B, C, D, E, and F are integers.

Sample Input 1

2 3 5 1 2 4

Sample Output 1

22

Since A\times B\times C=2\times 3\times 5=30 and D\times E\times F=1\times 2\times 4=8,
we have (A\times B\times C)-(D\times E\times F)=22. Divide this by 998244353 and print the remainder, which is 22.

Sample Input 2

1 1 1000000000 0 0 0

Sample Output 2

1755647

Since A\times B\times C=1000000000 and D\times E\times F=0,
we have (A\times B\times C)-(D\times E\times F)=1000000000. Divide this by 998244353 and print the remainder, which is 1755647.

Sample Input 3

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

0

We have (A\times B\times C)-(D\times E\times F)=0. Divide this by 998244353 and print the remainder, which is 0.

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i. If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• 6 \leq N \leq 1000
• \lvert S_i\rvert =N
• S_i consists of # and ..

Sample Input 1

8
........
........
.#.##.#.
........
........
........
........
........

Sample Output 1

Yes

By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.

Sample Input 2

6
######
######
######
######
######
######

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

Sample Output 3

No

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

• Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 10^9
• 0 \leq A_i \lt M
• All values in the input are integers.

Sample Input 1

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1

11

Assume that he first puts the fourth card (5 is written) on the table and then performs the following.

• Put the fifth card (5 is written) on the table.
• Put the eighth card (6 is written) on the table.
• Put the second card (0 is written) on the table.
• Put the seventh card (0 is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2

1 10
4

Sample Output 2

0

Sample Input 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

Sample Output 3

99