Problem Statement

There are N buildings aligned in a row. The i-th building from the left has a height of H_i.

Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.

Constraints

• 1 \leq N \leq 100
• 1 \leq H_i \leq 100
• All input values are integers.

Sample Input 1

4
3 2 5 2

Sample Output 1

3

The building taller than the first one from the left is the third one from the left.

Sample Input 2

3
4 3 2

Sample Output 2

-1

No building is taller than the first one from the left.

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

6

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

1. If there are no groups in the queue, start the attraction and end the guidance.
2. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
   • If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
   • Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
3. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

• 1\leq N\leq 100
• 1\leq K\leq 100
• 1\leq A_i\leq K\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

4

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

• Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
• Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
• After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
• Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

7

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

8

Problem Statement

For positive integers x and y, define f(x, y) as the remainder of (x + y) divided by 10^8.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression:

Constraints

• 2 \leq N \leq 3\times 10^5
• 1 \leq A_i < 10^8
• All input values are integers.

Sample Input 1

3
3 50000001 50000002

Sample Output 1

100000012

• f(A_1,A_2)=50000004
• f(A_1,A_3)=50000005
• f(A_2,A_3)=3

Thus, the answer is f(A_1,A_2) + f(A_1,A_3) + f(A_2,A_3) = 100000012.

Note that you are not asked to compute the remainder of the sum divided by 10^8.

Sample Input 2

5
1 3 99999999 99999994 1000000

Sample Output 2

303999988

Problem Statement

For positive integers x and y, define f(x, y) as follows:

• Interpret the decimal representations of x and y as strings and concatenate them in this order to obtain a string z. The value of f(x, y) is the value of z when interpreted as a decimal integer.

For example, f(3, 14) = 314 and f(100, 1) = 1001.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression modulo 998244353:

Constraints

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

Sample Input 1

3
3 14 15

Sample Output 1

2044

• f(A_1, A_2) = 314
• f(A_1, A_3) = 315
• f(A_2, A_3) = 1415

Thus, the answer is f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044.

Sample Input 2

5
1001 5 1000000 1000000000 100000

Sample Output 2

625549048

Be sure to calculate the value modulo 998244353.

Problem Statement

For strings x and y, define f(x, y) as follows:

• f(x, y) is the length of the longest common prefix of x and y.

You are given N strings (S_1, \ldots, S_N) consisting of lowercase English letters. Find the value of the following expression:

Constraints

• 2 \leq N \leq 3\times 10^5
• S_i is a string consisting of lowercase English letters.
• 1 \leq |S_i|
• |S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5
• All input numbers are integers.

Sample Input 1

3
ab abc arc

Sample Output 1

4

• f(S_1,S_2)=2
• f(S_1,S_3)=1
• f(S_2,S_3)=1

Thus, the answer is f(S_1,S_2) + f(S_1,S_3) + f(S_2,S_3) = 4.

Sample Input 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

Sample Output 2

32

Problem Statement

Tiles are laid out on a coordinate plane. There are two types of tiles: small tiles of size 1\times1 and large tiles of size K\times K, laid out according to the following rules:

• For each pair of integers (i,j), the square \lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained within either one small tile or one large tile.
  • If \left\lfloor\dfrac iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor is even, it is contained within a small tile.
  • Otherwise, it is contained within a large tile.

Tiles include their boundaries, and no two different tiles have a positive area of intersection.

For example, when K=3, tiles are laid out as follows:

Takahashi starts at the point (S_x+0.5,S_y+0.5) on the coordinate plane.

He can repeat the following movement any number of times:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he crosses from one tile to another, he must pay a toll of 1.

Determine the minimum toll Takahashi must pay to reach the point (T_x+0.5,T_y+0.5).

Constraints

• 1\leq K\leq10^{16}
• 0\leq S_x\leq2\times10^{16}
• 0\leq S_y\leq2\times10^{16}
• 0\leq T_x\leq2\times10^{16}
• 0\leq T_y\leq2\times10^{16}
• All input values are integers.

Sample Input 1

3
7 2
1 6

Sample Output 1

5

For example, he can move as follows, paying a toll of 5.

• Move up by 3. Pay a toll of 1.
• Move left by 2. Pay a toll of 1.
• Move up by 1. Pay a toll of 1.
• Move left by 4. Pay a toll of 2.

The toll paid cannot be 4 or less, so print 5.

Sample Input 2

1
41 42
13 56

Sample Output 2

42

When he moves the shortest distance, he will always pay a toll of 42.

The toll paid cannot be 41 or less, so print 42.

Sample Input 3

100
100 99
199 1

Sample Output 3

0

There are cases where no toll needs to be paid.

Sample Input 4

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

Sample Output 4

79154049

Problem Statement

The Kingdom of AtCoder has N towns: towns 1, 2, \ldots, N. To move from town i to town j, you must pay a toll of C \times |i-j| yen.

Takahashi, a merchant, is considering participating in zero or more of M upcoming markets.

The i-th market (1 \leq i \leq M) is described by the pair of integers (T_i, P_i), where the market is held in town T_i and he will earn P_i yen if he participates.

For all 1 \leq i < M, the i-th market ends before the (i+1)-th market begins. The time it takes for him to move is negligible.

He starts with 10^{10^{100}} yen and is initially in town 1. Determine the maximum profit he can make by optimally choosing which markets to participate in and how to move.

Formally, let 10^{10^{100}} + X be his final amount of money if he maximizes the amount of money he has after the M markets. Find X.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq C \leq 10^9
• 1 \leq M \leq 2 \times 10^5
• 1 \leq T_i \leq N (1 \leq i \leq M)
• 1 \leq P_i \leq 10^{13} (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

6 3
4
5 30
2 10
4 25
2 15

Sample Output 1

49

For example, Takahashi can increase his money by 49 yen by acting as follows:

• Move to town 5. His money becomes 10^{10^{100}} - 12 yen.
• Participate in the first market. His money becomes 10^{10^{100}} + 18 yen.
• Move to town 4. His money becomes 10^{10^{100}} + 15 yen.
• Participate in the third market. His money becomes 10^{10^{100}} + 40 yen.
• Move to town 2. His money becomes 10^{10^{100}} + 34 yen.
• Participate in the fourth market. His money becomes 10^{10^{100}} + 49 yen.

It is impossible to increase his money to 10^{10^{100}} + 50 yen or more, so print 49.

Sample Input 2

6 1000000000
4
5 30
2 10
4 25
2 15

Sample Output 2

0

The toll fee is so high that it is optimal for him not to move from town 1.

Sample Input 3

50 10
15
37 261
28 404
49 582
19 573
18 633
3 332
31 213
30 377
50 783
17 798
4 561
41 871
15 525
16 444
26 453

Sample Output 3

5000

Sample Input 4

50 1000000000
15
30 60541209756
48 49238708511
1 73787345006
24 47221018887
9 20218773368
34 40025202486
14 28286410866
24 82115648680
37 62913240066
14 92020110916
24 20965327730
32 67598565422
39 79828753874
40 52778306283
40 67894622518

Sample Output 4

606214471001

Note that the output value may exceed the range of a 32-bit integer.