Problem Statement

Takahashi is working as an operations staff member for a figure skating regional qualifying competition.

In this competition, N athletes perform, and each athlete is scored by M judges. The score that athlete i (1 \leq i \leq N) receives from judge j (1 \leq j \leq M) is an integer S_{i,j}.

In figure skating scoring, to reduce the influence of extreme scores, each athlete's final score is calculated as follows:

• When M \geq 3: From the M scores the athlete received, the single highest score and the single lowest score are removed. Even if there are multiple scores with the same value, only one of each is removed. The average of the remaining M - 2 scores (the sum divided by M - 2) is computed, and the integer obtained by truncating the decimal part is the final score.
• When M = 1 or M = 2: Since removing scores would leave 0 or fewer remaining, no scores are removed. The average of all M scores (the sum divided by M) is computed, and the integer obtained by truncating the decimal part is the final score.

Here, "truncating the decimal part" means taking the largest integer that does not exceed the value (the floor function \lfloor \cdot \rfloor). Note that since all scores are 0 or greater, the final score is also a non-negative integer.

To qualify for the main competition, an athlete's final score must be at least the threshold score of K points. Athletes whose final score is less than K points are eliminated in the qualifying round.

On behalf of Takahashi, determine the number of athletes who are eliminated in the qualifying round.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 100
• 0 \leq K \leq 100
• 0 \leq S_{i,j} \leq 100 (1 \leq i \leq N, 1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 5 70
80 75 60 90 85
50 55 60 65 70
100 100 100 100 100

Sample Output 1

1

Sample Input 2

4 2 50
60 40
100 0
49 50
55 55

Sample Output 2

1

Sample Input 3

5 7 75
80 85 90 70 75 88 92
60 65 70 55 58 62 68
100 99 98 97 96 95 94
74 74 74 74 74 74 74
75 75 75 75 75 75 75

Sample Output 3

2

Problem Statement

Takahashi is the caretaker of a circular park. Along the perimeter of this park, N pillars are placed at equal intervals, numbered from 1 to N in clockwise order.

There is a plan to install one street light at the center of the park's circle. This street light has a special directional property and illuminates facing the direction of one of the pillars.

When the front direction of the street light is set to pillar i, the deviation angle with respect to pillar j is defined as follows. When viewing pillars i and j from the center of the circle, the deviation angle is the smaller of the clockwise and counterclockwise angles (in degrees). Since the N pillars are equally spaced, the central angle between adjacent pillars is \frac{360}{N} degrees. Let d(i, j) be the smaller of the number of pillar intervals counted clockwise from pillar i to pillar j and the number counted counterclockwise. Then,

d(i, j) = \min\bigl(|i - j|,\; N - |i - j|\bigr)

and the deviation angle is d(i, j) \times \frac{360}{N} degrees.

Among the N pillars on the park's perimeter, M of them have benches installed. The k-th bench is located at pillar S_k (S_1, S_2, \ldots, S_M are all distinct).

When the front direction of the street light is set to one of the pillars 1, 2, \ldots, N, the cost of that setting is defined as "the maximum deviation angle among those for each of the M pillars with benches." That is, the cost when the front direction is set to pillar i is

\max_{1 \leq k \leq M} \; d(i, S_k) \times \frac{360}{N}

Takahashi wants to choose the front direction of the street light so that the cost is minimized. Find the minimum value of the cost.

The answer should be output in the form P/Q as an irreducible fraction \frac{P}{Q} (P \geq 0, Q \geq 1, \gcd(P, Q) = 1). If the answer is 0, output 0/1. If the answer is an integer, output it in the form P/1 with denominator 1.

Constraints

• 2 \leq N \leq 10^9
• 1 \leq M \leq \min(N, 2 \times 10^5)
• 1 \leq S_k \leq N (1 \leq k \leq M)
• All S_k are distinct
• All inputs are integers

Sample Input 1

8 3
1 3 6

Sample Output 1

135/1

Sample Input 2

12 2
4 10

Sample Output 2

90/1

Sample Input 3

25 7
2 5 9 14 18 21 24

Sample Output 3

144/1

Sample Input 4

1000000000 12
1 12345678 98765432 200000000 333333333 400000001 555555555 666666666 777777777 888888888 999999999 1000000000

Sample Output 4

3800000007/25000000

Sample Input 5

2 1
2

Sample Output 5

0/1

Problem Statement

Takahashi is in charge of managing a flower bed in his garden. The flower bed has N flowers planted in a row, numbered flower 1, flower 2, \ldots, flower N from left to right. Before watering begins, the height of flower i is H_i.

Takahashi waters the flowers over M days. On day j (j = 1, 2, \ldots, M), he waters flowers L_j, L_j + 1, \ldots, R_j. Each watered flower increases in height by W_j per flower.

The height of flower i after all M days of watering are completed is called the final height of flower i. Flower i is considered "sufficiently grown" if its final height is at least the target height T_i.

Find the number of sufficiently grown flowers.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_i \leq 10^{18} (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
• 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

5 3
10 20 30 40 50
25 35 50 40 80
1 3 5
2 4 10
1 5 3

Sample Output 1

2

Sample Input 2

8 4
1 1 1 1 1 1 1 1
10 15 20 25 20 15 10 5
1 8 5
2 7 5
3 6 5
4 5 5

Sample Output 2

4

Sample Input 3

10 5
1000000000 500000000 1 999999999 100 200 300 400 500 600
1000000000000000000 1000000000 100 2000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 10 1000000000
1 5 1000000000
3 8 1000000000
1 10 1000000000
5 10 1000000000

Sample Output 3

9

Problem Statement

Takahashi and Aoki each manage a facility consisting of N rooms. The rooms in each facility are connected by corridors forming a tree structure, and in both facilities, room 1 is the entrance (root). Corridors can be traversed in both directions, and the parent-child relationships of the rooms are determined by taking room 1 as the root.

For a rooted tree consisting of N rooms, a traversal record is defined by the following procedure:

1. For each room, determine the order in which to visit its child rooms (rooms directly connected by a corridor that are farther from the root). This order may be chosen arbitrarily for each room.
2. Starting from an empty string, execute the following recursive procedure on the entrance (room 1), and the resulting string is the traversal record.

Recursive procedure for room v:

• First, append the character a to the end.
• Next, following the order determined in step 1, for each child room of room v, do the following in order: execute this recursive procedure on that child room (no characters are appended when returning to room v).
• Finally, append the character b to the end.

If room v has no children, nothing is done in the second step, and b is appended immediately after a.

The length of the string obtained in this way is always 2N.

Depending on the choice of visiting order of children, different traversal records may be obtained. A string that belongs to the intersection of the set of all traversal records obtainable from Takahashi's facility and the set of all traversal records obtainable from Aoki's facility is called a common traversal record.

Enumerate all common traversal records in lexicographic order. If the same string is obtained from different child visiting orders, output it only once without duplication. The character ordering is a < b.

Constraints

• 1 \leq N \leq 10
• 1 \leq UA_i, VA_i \leq N, UA_i \neq VA_i (1 \leq i \leq N-1)
• 1 \leq UB_i, VB_i \leq N, UB_i \neq VB_i (1 \leq i \leq N-1)
• The corridors of Takahashi's facility form a tree structure (N rooms connected by N-1 undirected edges)
• The corridors of Aoki's facility form a tree structure (N rooms connected by N-1 undirected edges)
• All input values are integers

Sample Input 1

3
1 2
1 3
1 2
1 3

Sample Output 1

1
aababb

Sample Input 2

3
1 2
2 3
1 2
1 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

2
aaababbaabbb
aaabbaababbb

Sample Input 4

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

Sample Output 4

12
aaaabbabbaaabbbaabbb
aaaabbabbaabbaaabbbb
aaaabbbaaabbabbaabbb
aaaabbbaabaabbbaabbb
aaaabbbaabbaaabbabbb
aaaabbbaabbaabaabbbb
aaabaabbbaaabbbaabbb
aaabaabbbaabbaaabbbb
aaabbaaabbabbaaabbbb
aaabbaaabbbaaabbabbb
aaabbaaabbbaabaabbbb
aaabbaabaabbbaaabbbb

Sample Input 5

1

Sample Output 5

1
ab

Problem Statement

Takahashi is trying to create a long banner by connecting multiple signs in a horizontal row as decoration for a cultural festival. He has N signs, and the i-th sign has the string S_i written on it. Here, the length (number of characters) of string S_i is denoted as |S_i|.

Takahashi connects these signs in order from the 1-st to the N-th, from left to right. When connecting them, to save space, he overlaps adjacent signs as much as possible.

Specifically, when connecting the i-th sign (i \geq 2), he considers positive integers l that satisfy all of the following conditions regarding the string S_{i-1} of the previous sign and the string S_i of the current sign:

• 1 \leq l < |S_{i-1}| and l < |S_i|. (That is, neither string is completely contained in the overlap, and each has at least 1 character remaining outside the overlap.)
• The last l characters of S_{i-1} match the first l characters of S_i.

If such a positive integer l exists, let L_i be its maximum value. If none exists, let L_i = 0.

When connecting the i-th sign, the first L_i characters of S_i are overlapped with the end of the previous sign. When L_i = 0, it is simply concatenated to the end without any overlap. In either case, the number of characters newly added to the banner from S_i is |S_i| - L_i.

Find the total number of characters of the entire banner when all N signs are connected in order (where overlapping portions are counted only once).

The total number of characters can be calculated by the following formula:

|S_1| + \sum_{i=2}^{N} (|S_i| - L_i)

Example

Consider the case where S_1 = abcabc and S_2 = abcxyz.

We check for matches between the suffix of S_1 and the prefix of S_2. By the condition on l, we have 1 \leq l < 6. When l = 3, the last 3 characters of S_1, abc, match the first 3 characters of S_2, abc. For l = 4, 5, there is no match. Therefore, the maximum l satisfying the conditions is 3, and L_2 = 3.

The connected result is abcabcxyz, and the total number of characters is 6 + (6 - 3) = 9.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq |S_i| \leq 10^6
• \displaystyle \sum_{i=1}^{N} |S_i| \leq 10^6
• S_i consists only of lowercase English letters.

Sample Input 1

3
abcabc
abcxyz
xyzabc

Sample Output 1

12

Sample Input 2

4
cat
dog
bird
fish

Sample Output 2

14

Sample Input 3

8
abracadabra
abraxyz
xyzxyz
yzalpha
alphabet
betamax
maximum
umami

Sample Output 3

36

Sample Input 4

20
aaaaab
abaaaa
aaaacaaa
caaad
aadbbb
bbbccc
cccdde
ddefgh
ghijklm
klmnop
opqrstu
stuvwx
vwxyzab
zabzab
abzabc
abcabcabc
bcabcx
xcdef
defdefg
fghello

Sample Output 4

71

Sample Input 5

1
a

Sample Output 5

1