Problem Statement

There are N bridges in AtCoder Village. The height of the bridge numbered i is H_i (i is an integer between 1 and N).
Every two different bridges in the village have different heights.

Print the number representing the highest bridge in the village.

Constraints

• 1\leq N \leq 100
• 1\leq H_i \leq 10^9
• All H_i are different.
• All values in the input are integers.

Sample Input 1

3
50 80 70

Sample Output 1

2

The village has three bridges.
The first, second, and third bridges have heights of 50, 80, and 70, respectively, so the second bridge is the highest.
Thus, 2 should be printed.

Sample Input 2

1
1000000000

Sample Output 2

1

The village has only one bridge, so the first bridge is the highest.

Sample Input 3

10
22 75 26 45 72 81 47 29 97 2

Sample Output 3

9

The village has ten bridges, and the ninth bridge (with a height of 97) is the highest.

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

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

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

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

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

Sample Output 2

3

Problem Statement

A function f(x) defined for non-negative integers x satisfies the following conditions.

• f(0) = 1.
• f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) for any positive integer k.

Here, \lfloor A \rfloor denotes the value of A rounded down to an integer.

Find f(N).

Constraints

• N is an integer satisfying 0 \le N \le 10^{18}.

Sample Input 1

2

Sample Output 1

3

We have f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3.

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

Problem Statement

Takahashi is playing sugoroku, a board game.

The board has N+1 squares, numbered 0 to N. Takahashi starts at square 0 and goes for square N.

The game uses a roulette wheel with M numbers from 1 to M that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square N, he turns around at square N and goes back by the excessive number of squares.

For instance, assume that N=4 and Takahashi is at square 3. If the wheel shows 4, the excessive number of squares beyond square 4 is 3+4-4=3. Thus, he goes back by three squares from square 4 and arrives at square 1.

When Takahashi arrives at square N, he wins and the game ends.

Find the probability, modulo 998244353, that Takahashi wins when he may spin the wheel at most K times.

Constraints

• M \leq N \leq 1000
• 1 \leq M \leq 10
• 1 \leq K \leq 1000
• All values in the input are integers.

Sample Input 1

2 2 1

Sample Output 1

499122177

Takahashi wins in one spin if the wheel shows 2. Therefore, the probability of winning is \frac{1}{2}.

We have 2\times 499122177 \equiv 1 \pmod{998244353}, so the answer to be printed is 499122177.

Sample Input 2

10 5 6

Sample Output 2

184124175

Sample Input 3

100 1 99

Sample Output 3

0

Problem Statement

You are given an integer array A=(a_1,a_2,\ldots,a_N).
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of A, and delete it from the array.

For each x=1,2,\ldots,M, solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of A equal x. If it is impossible to make the sum of elements of A equal x, print -1 instead.

Note that the sum of elements of an empty array is 0.

Constraints

• 1 \leq N,M \leq 3000
• 1 \leq a_i \leq 3000
• All values in the input are integers.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For x=1, delete a_2,a_3,a_4, and the sum of elements of A becomes x.
• For x=2, delete a_3,a_4, then delete a_1, and the sum of elements of A becomes x.
• For x=3, delete a_3,a_4, and the sum of elements of A becomes x.
• For x=4, delete a_1,a_2,a_3, and the sum of elements of A becomes x.
• For x=5, delete a_2,a_3, and the sum of elements of A becomes x.

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

Sample Output 3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1

Problem Statement

There are N kinds of items, each with infinitely many copies. The i-th kind of item has a weight of A_i, a volume of B_i, and a value of C_i.

Level X Takahashi can carry items whose total weight is at most X and whose total volume is at most X. Under this condition, it is allowed to carry any number of items of the same kind, or omit some kinds of items.

Let f(X) be the maximum total value of items Level X Takahashi can carry. It can be proved that the limit \displaystyle\lim_{X\to \infty} \frac{f(X)}{X} exists. Find this limit.

Constraints

• 1\leq N\leq 2\times 10^5
• 10^8\leq A_i,B_i,C_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2
100000000 200000000 100000000
200000000 100000000 100000000

Sample Output 1

0.6666666666666667

When X=300000000, Takahashi can carry items whose total weight is at most 300000000 and whose total volume is at most 300000000.

He can carry, for instance, one copy of the 1-st item and one copy of the 2-nd item. Then, the total value of the items is 100000000+100000000=200000000. This is the maximum achievable value, so \dfrac{f(300000000)}{300000000}=\dfrac{2}{3}.

It can also be proved that \displaystyle\lim_{X\to \infty} \frac{f(X)}{X} equals \dfrac{2}{3}. Thus, the answer is 0.6666666....

Sample Input 2

1
500000000 300000000 123456789

Sample Output 2

0.2469135780000000

Problem Statement

There are N monsters along a number line. At the coordinate i (1\leq i\leq N) is a monster with a stamina of A_i.
Additionally, at the coordinate i, there is a permanent shield of a strength B_i.
This shield persists even when the monster at the same coordinate has a health of 0 or below.

Takahashi, a magician, can perform the following operation any number of times.

• Choose integers l and r satisfying 1\leq l\leq r\leq N.
• Then, consume \max(B_l, B_{l+1}, \ldots, B_r) MP (magic points) to decrease by 1 the stamina of each of the monsters at the coordinates l,l+1,\ldots,r.

When choosing l and r, it is fine if some of the monsters at the coordinates l,l+1,\ldots,r already have a stamina of 0 or below.
Note, however, that the shields at all those coordinates still exist.

Takahashi wants to make the stamina of every monster 0 or below.
Find the minimum total MP needed to achieve his objective.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

5
4 3 5 1 2
10 40 20 60 50

Sample Output 1

210

Takahashi can achieve his objective as follows.

• Choose (l,r)=(1,5). Consume \max(10,40,20,60,50)=60 MP, and the staminas of the monsters are (3,2,4,0,1).
• Choose (l,r)=(1,5). Consume \max(10,40,20,60,50)=60 MP, and the staminas of the monsters are (2,1,3,-1,0).
• Choose (l,r)=(1,3). Consume \max(10,40,20)=40 MP, and the staminas of the monsters are (1,0,2,-1,0).
• Choose (l,r)=(1,1). Consume \max(10)=10 MP, and the staminas of the monsters are (0,0,2,-1,0).
• Choose (l,r)=(3,3). Consume \max(20)=20 MP, and the staminas of the monsters are (0,0,1,-1,0).
• Choose (l,r)=(3,3). Consume \max(20)=20 MP, and the staminas of the monsters are (0,0,0,-1,0).

Here, he consumes a total of 60+60+40+10+20+20=210 MP, which is the minimum possible.

Sample Input 2

1
1000000000
1000000000

Sample Output 2

1000000000000000000

Sample Input 3

10
522 4575 6426 9445 8772 81 3447 629 3497 7202
7775 4325 3982 4784 8417 2156 1932 5902 5728 8537

Sample Output 3

77917796