Problem Statement

Takahashi is developing a reservation management system for a cooking class. In this system, the start time of each reservation is managed as a pair of hours and minutes.

However, due to a bug in the input form, invalid data may be registered where the minute value is 60 or greater, or the hour value is 24 or greater. For example, time data such as 25 hours 80 minutes may exist.

Takahashi decided to create a program to normalize these invalid time data. Normalization means treating the given time data (hours H, minutes M) as the time exactly (60H + M) minutes after 0 hours 0 minutes of a certain day, and converting it into the form "D days later, h hours m minutes" (where 0 \leq h \leq 23, 0 \leq m \leq 59, D \geq 0).

The normalization calculation can be performed by the following steps. Execute Step 1, then Step 2, in order.

1. Carry-over of minutes: Carry over the minute value M into hours, using 60 minutes = 1 hour. Specifically, the hour value after carry-over is H' = H + \lfloor M / 60 \rfloor, and the normalized minute value is m = M \bmod 60.
2. Carry-over of hours: Carry over the hour value H' obtained in Step 1 into days, using 24 hours = 1 day. Specifically, the normalized number of days is D = \lfloor H' / 24 \rfloor, and the normalized hour value is h = H' \bmod 24.

Through the above, the normalized number of days D (D = 0 means the reference day itself), hours h (0 \leq h \leq 23), and minutes m (0 \leq m \leq 59) are determined.

Given the start time data of N reservations, normalize each of them and output the normalized number of days D, hours h, and minutes m.

Constraints

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

Sample Input 1

3
10 30
25 80
0 90

Sample Output 1

0 10 30
1 2 20
0 1 30

Sample Input 2

4
23 59
24 0
0 1440
48 120

Sample Output 2

0 23 59
1 0 0
1 0 0
2 2 0

Sample Input 3

8
0 0
12 30
23 59
24 60
100 200
0 1500
50 0
47 61

Sample Output 3

0 0 0
0 12 30
0 23 59
1 1 0
4 7 20
1 1 0
2 2 0
2 0 1

Sample Input 4

15
0 0
1 0
0 1
23 59
24 0
24 1
0 60
25 80
100 100
999 999
10000 10000
123456 789012
1000000000 1000000000
999999999 999999999
500000000 500000000

Sample Output 4

0 0 0
0 1 0
0 0 1
0 23 59
1 0 0
1 0 1
0 1 0
1 2 20
4 5 40
42 7 39
423 14 40
5691 22 12
42361111 2 40
42361111 1 39
21180555 13 20

Sample Input 5

1
0 0

Sample Output 5

0 0 0

Problem Statement

Takahashi's class has a training camp planned for M days. Each day of the camp has a fixed snack budget, and the snack budget for day j (1 \leq j \leq M) is S_j yen.

For the snacks to bring to the camp, he must choose exactly 1 type of product from the N types of products available at the store, and during the camp he will purchase and eat one of that snack each day. The price of product i is R_i yen.

Takahashi wants to choose a product such that the price of the snack is within the budget on every day. In other words, he wants to choose a product i such that R_i \leq S_j holds for every day j.

Find the number of products that satisfy this condition.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^6
• 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

5 3
100 200 300 400 500
350 300 450

Sample Output 1

3

Sample Input 2

3 4
100 200 300
50 60 70 80

Sample Output 2

0

Sample Input 3

12 8
120 500 450 300 800 450 100 700 600 250 449 451
1000 900 450 800 700 600 500 550

Sample Output 3

7

Sample Input 4

30 20
1500 999 1000 1001 750 2000 50 300 1200 980 1100 1020 999 100 5000 250 875 1000 1 450 650 700 800 900 10000 1050 990 995 996 997
2000 1500 1200 1100 1050 1000 1300 1400 1600 1700 1800 1900 1250 1150 1080 1020 1010 1005 1000 3000

Sample Output 4

21

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

1

Problem Statement

Takahashi is participating in a gem collecting event held on a straight shopping street. There are N shops lined up in a row from left to right on the street, and the i-th shop (1 \leq i \leq N) has A_i gems placed in it.

Takahashi starts at shop S. According to the event rules, Takahashi must make exactly K moves. In one move, he moves from his current shop to an adjacent shop. That is, when he is currently at shop p (1 \leq p \leq N), he can move to shop p-1 if p-1 \geq 1, or to shop p+1 if p+1 \leq N. He cannot go to the left of shop 1 or to the right of shop N. He may visit the same shop multiple times.

For each shop Takahashi visits (including shop S where he starts), he can collect the A_i gems placed there. However, even if he visits the same shop multiple times, he can only collect the gems on the first visit.

Determine the maximum total number of gems Takahashi can collect when he makes exactly K moves.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq S \leq N
• 1 \leq K \leq 10^9
• 0 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

5 3 2
10 20 30 40 50

Sample Output 1

120

Sample Input 2

4 1 3
5 100 1 10

Sample Output 2

116

Sample Input 3

12 6 8
3 15 8 20 7 50 6 12 30 4 25 10

Sample Output 3

144

Sample Input 4

30 17 25
12 0 45 23 78 5 90 34 11 67 8 56 100 3 29 74 41 62 18 95 7 36 84 21 50 69 14 88 2 31

Sample Output 4

922

Sample Input 5

2 1 1000000000
1000000000 0

Sample Output 5

1000000000

Problem Statement

Takahashi belongs to a university research lab and is trying to choose research topics to work on this semester. The lab has N candidate research topics, each numbered from 1 to N. Working on research topic i requires a cost of C_i for preparing experimental equipment and materials, and the value of academic results obtained from working on it is estimated to be P_i.

There are M prerequisite relationships among the research topics. The j-th prerequisite relationship is represented by the pair (U_j, V_j), meaning that if you work on research topic U_j, you must also work on research topic V_j (the converse does not necessarily hold). Note that prerequisite relationships may contain cycles. For example, a situation where research topic A requires B as a prerequisite and B requires A as a prerequisite is possible. In this case, you cannot choose only one of A and B; you must either choose both or choose neither.

Takahashi selects a set S (S \subseteq \{1, 2, \ldots, N\}) of research topics to work on. S must satisfy all prerequisite relationships. That is, for all j = 1, 2, \ldots, M, if research topic U_j is included in S, then research topic V_j must also be included in S. S may be the empty set.

Takahashi's goal is to maximize the total value of results obtained from the chosen research topics minus the total cost, namely

\sum_{i \in S} (P_i - C_i)

If S is the empty set, this value is 0.

Find this maximum value.

Constraints

• 1 \leq N \leq 15
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq P_i \leq 1000 (1 \leq i \leq N)
• 1 \leq C_i \leq 1000 (1 \leq i \leq N)
• 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
• U_j \neq V_j (1 \leq j \leq M)
• There are no duplicate prerequisite relationships. That is, all pairs (U_j, V_j) are distinct. However, it is possible that (U_j, V_j) = (V_k, U_k) for some j, k (i.e., reverse relationships may coexist).
• Prerequisite relationships may contain cycles. That is, the directed graph defined by the prerequisite relationships is not necessarily acyclic.
• All inputs are integers.

Sample Input 1

3 1
10 3
5 8
8 2
1 2

Sample Output 1

10

Sample Input 2

2 1
1 5
2 6
1 2

Sample Output 2

0

Sample Input 3

6 5
20 13
15 19
18 14
10 13
25 10
8 20
1 2
2 1
3 4
5 6
6 5

Sample Output 3

7

Sample Input 4

10 12
50 30
40 45
30 10
25 40
60 20
35 50
20 15
45 25
10 30
55 35
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
10 1
4 7
8 10

Sample Output 4

70

Sample Input 5

1 0
5 3

Sample Output 5

2

Problem Statement

Takahashi is investigating integers from 1 to N.

When a positive integer k is written in decimal notation, the product of all its digits is called the "digit product" of k. For example, the digit product of 123 is 1 \times 2 \times 3 = 6, the digit product of 205 is 2 \times 0 \times 5 = 0, and the digit product of 9 is 9.

Takahashi wants to know the number of integers between 1 and N (inclusive) whose digit product is not 0 and whose digit product is a multiple of M. Find this count on behalf of Takahashi.

Note that 0 is not a multiple of any positive integer (that is, integers whose digit product is 0 are never counted).

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq M \leq 500
• N and M are integers

Sample Input 1

25 6

Sample Output 1

3

Sample Input 2

20 7

Sample Output 2

2

Sample Input 3

12345 36

Sample Output 3

2767

Sample Input 4

987654321012345678 420

Sample Output 4

127763436760690150

Sample Input 5

1 1

Sample Output 5

1