Problem Statement

Takahashi loves music and is building a database of lyrics from his favorite songs.

Takahashi has lyrics data for N songs. Each song is numbered from 1 to N, and the lyrics of the i-th song are represented by a string S_i consisting of lowercase English letters.

Takahashi decided to calculate a "summer score" for each song. The summer score of song i is defined as the number of times tanabata appears as a contiguous substring in the string S_i.

More precisely, letting S_i[j] denote the j-th character of S_i (1-indexed), the summer score is the number of integers j (1 \leq j \leq |S_i| - 7) such that S_i[j]S_i[j+1] \cdots S_i[j+7] matches tanabata. Here, |S_i| denotes the length of the string S_i. If |S_i| \leq 7, no such j exists, so the summer score is 0.

Among the N songs, find the number of the song with the maximum summer score. If there are multiple songs with the maximum summer score, output the one with the smallest number. Note that if all songs have a summer score of 0, likewise output the song with the smallest number (i.e., song 1).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq |S_i| \leq 10^5
• \sum_{i=1}^{N} |S_i| \leq 10^6
• S_i is a string consisting of lowercase English letters

Sample Input 1

3
tanabata
summer
tanabatatanabata

Sample Output 1

3

Sample Input 2

5
abctanabatadef
tanabata
xxxxxxxxxx
tanabatanabata
holiday

Sample Output 2

4

Sample Input 3

10
thesummerstarfestivaltanabataisbeautiful
tanabatatanabatatanabata
abcdefghijklmnopqrstuvwxyz
aaatanabatabbbtanabataccc
summerbeachsernlight
tanabatanabatanabatanabata
zzzzzzzzzzzzzzzzzzzzz
atanabatax
tanabata
mytanabatamemorytanabatadreamtanabatanight

Sample Output 3

6

Problem Statement

In the apartment building where Takahashi lives, N residents take turns watering the shared flower bed, with one person on duty each day. The residents are numbered from 1 to N.

The person on duty on day 1 is resident S, and from then on, duty rotates in order of their numbers: S, S+1, \ldots, N, 1, 2, \ldots. That is, the person on duty on day j (j = 1, 2, \ldots, D) is resident ((S - 1 + j - 1) \bmod N) + 1.

When resident i is on duty, they water the flower bed with A_i liters of water. Even if resident i is on duty multiple times, they use the same A_i liters of water each time.

Find the total amount of water (in liters) used on the flower bed over the D days from day 1 to day D.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq 10^{14}
• 1 \leq S \leq N
• 1 \leq A_i \leq 10^4
• All input values are integers.

Sample Input 1

4 6 2
3 1 4 2

Sample Output 1

15

Sample Input 2

5 3 5
10 20 30 40 50

Sample Output 2

80

Sample Input 3

8 25 6
7 2 9 4 5 1 8 3

Sample Output 3

118

Sample Input 4

20 12345678901234 13
15 230 7 89 154 321 48 76 205 19 410 63 97 182 54 268 11 340 125 72

Sample Output 4

1719753070941911

Sample Input 5

1 100000000000000 1
10000

Sample Output 5

1000000000000000000

Problem Statement

Takahashi is the manager of a delivery center. The delivery center has N delivery workers, numbered from 1 to N. The stamina value of delivery worker i is A_i.

Today there are M delivery requests, and delivery request j requires a delivery worker with a stamina value of at least B_j. Exactly one delivery worker must be assigned to each delivery request. Also, each delivery worker can be assigned to at most one delivery request.

Here, when delivery worker i is assigned to delivery request j, if A_i = B_j, then the assignment is called a perfect match. A perfect match is ideal because it makes full use of the delivery worker's stamina without waste.

Takahashi wants to achieve the following two goals in this order of priority:

1. Primary goal: Assign a delivery worker who meets the required stamina value to all M delivery requests (that is, delivery worker i assigned to delivery request j must satisfy A_i \geq B_j). If it is impossible to assign a delivery worker to every delivery request, output -1.
2. Secondary goal: Among all assignments that achieve the primary goal, maximize the number of perfect matches (pairs where A_i = B_j).

If the primary goal is achievable, output the maximum number of perfect matches.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
• All inputs are integers.

Sample Input 1

4 3
3 5 5 7
5 4 3

Sample Output 1

2

Sample Input 2

3 3
2 4 6
3 5 7

Sample Output 2

-1

Sample Input 3

10 7
1 3 3 4 6 6 8 10 10 12
3 5 6 6 9 10 11

Sample Output 3

4

Sample Input 4

20 15
2 5 5 7 8 10 10 12 15 15 18 20 21 25 30 30 35 40 45 50
1 5 6 10 10 14 15 19 20 22 30 31 35 44 50

Sample Output 4

8

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

1

Problem Statement

Takahashi is planning to set up a booth at a summer festival that runs for N days. Each day of the festival is numbered from 1 to N, and the expected sales for day i (1 \leq i \leq N) is A_i.

During the festival period, Takahashi will choose two booth periods. Each booth period consists of exactly K consecutive days, and the first booth period must be scheduled before the second booth period. Furthermore, due to ingredient procurement and equipment maintenance, the two booth periods must not overlap, and there must be at least one day of gap between them (at least one day that is not included in either booth period).

Specifically, if the first booth period runs from day s to day s+K-1, and the second booth period runs from day t to day t+K-1, then all of the following conditions must be satisfied:

• 1 \leq s and s + K - 1 \leq N (the first booth period fits within the festival period)
• 1 \leq t and t + K - 1 \leq N (the second booth period fits within the festival period)
• t \geq s + K + 1 (there is at least one day of gap between the last day s+K-1 of the first booth period and the first day t of the second booth period)

Takahashi wants to maximize the total expected sales over all days included in the two booth periods, that is,

\sum_{i=s}^{s+K-1} A_i + \sum_{i=t}^{t+K-1} A_i

Find the maximum value of this total.

Constraints

• 3 \leq N \leq 10^6
• 1 \leq K \leq \lfloor \frac{N-1}{2} \rfloor (i.e., 2K + 1 \leq N)
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

The constraint on K guarantees that there always exists at least one valid way to choose the two booth periods.

Sample Input 1

7 2
3 5 2 6 1 4 3

Sample Output 1

15

Sample Input 2

5 2
1 2 3 4 5

Sample Output 2

12

Sample Input 3

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

Sample Output 3

39

Sample Input 4

20 4
10 20 30 40 50 60 70 80 90 100 90 80 70 60 50 40 30 20 10 5

Sample Output 4

600

Sample Input 5

3 1
100 1 100

Sample Output 5

200

Problem Statement

Takahashi is in charge of maintaining a hiking course in a mountainous area. This course consists of N checkpoints lined up in a row, and the current elevation of the i-th checkpoint from the left is H_i.

For safety management, Aoki requires the following conditions for the maintenance of the course:

• The elevation of every checkpoint must be a non-negative integer.
• For any two adjacent checkpoints, the absolute difference in their elevations must be exactly 1. That is, if we denote the elevation of the i-th checkpoint after maintenance as H'_i, then |H'_i - H'_{i+1}| = 1 must hold for all 1 \le i \le N - 1.

Takahashi can freely reassign the elevation of each checkpoint to non-negative integers so that the conditions above are satisfied. However, since changing the elevation of a checkpoint requires large-scale construction, he wants to keep as many checkpoints at their current elevations as possible.

In other words, when we appropriately determine a sequence of non-negative integers H'_1, H'_2, \ldots, H'_N that satisfies the conditions above, find the maximum number of checkpoints for which H_i = H'_i.

Constraints

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

Sample Input 1

5
0 1 2 1 0

Sample Output 1

5

Sample Input 2

6
2 2 2 2 2 2

Sample Output 2

3

Sample Input 3

15
2 3 4 5 4 3 2 100 99 98 97 0 1 1000000000 999999999

Sample Output 3

7

Sample Input 4

50
0 1 0 1 2 3 10 9 8 20 19 18 17 16 15 14 13 12 11 10 0 0 0 5 4 3 2 1 0 1 2 100 101 102 103 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36

Sample Output 4

15

Sample Input 5

1
1000000000

Sample Output 5

1