Problem Statement

You have a bankbook from The Terrifying Bank. The deposit passbook of the bank has a terrifyingly scary property that the commission fee changes according to the withdrawal amount.

To withdraw money from the passbook, you need to specify the withdrawal amount in units of 1\,000 yen, and pay a commission fee of C yen per 1\,000 yen of withdrawal amount separately from the balance. Withdrawals are not allowed if they would leave the balance below 0 yen.

When the balance of your passbook from the bank is X yen, what is the maximum amount of money you can withdraw from it?

Constraints

• 1 \leq X \leq 10^7
• 1 \leq C \leq 999
• All input values are integers.

Sample Input 1

650000 8

Sample Output 1

644000

The commission fee required to withdraw 644\,000 yen is 644\,000 \times \displaystyle\frac{8}{1000} = 5\,152 yen, so since 644\,000 + 5\,152 \leq 650\,000, you can withdraw 644\,000 yen.

On the other hand, the commission fee required to withdraw 645\,000 yen is 645\,000 \times \displaystyle\frac{8}{1000} = 5\,160 yen, so since 645\,000 + 5\,160 > 650\,000, you cannot withdraw 645\,000 yen.

Sample Input 2

1003 4

Sample Output 2

0

It is possible that no money can be withdrawn at all.

Sample Input 3

10000000 24

Sample Output 3

9765000

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

There are two people, one in room 0 and the other in room N. Each person can move between rooms i - 1 and i only when door i is unlocked.

Find the number of rooms that neither of the two people can reach.

Constraints

• 2 \leq N \leq 100
• L_i \in \lbrace 0, 1 \rbrace
• All input values are integers.

Sample Input 1

5
0 1 0 0 1

Sample Output 1

3

The rooms that neither of the two people can reach are rooms 2, 3, 4, which is 3 rooms.

Sample Input 2

3
1 0 1

Sample Output 2

2

Sample Input 3

8
0 0 1 1 0 1 0 0

Sample Output 3

3

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

Takahashi is initially in room R, and can move between rooms i - 1 and i only when door i is unlocked. Also, he can perform a switching operation on door i only when he is in room i - 1 or room i. When a switching operation is performed on door i, if the door is unlocked, it becomes locked, and if it is locked, it becomes unlocked.

Find the minimum number of switching operations needed to make all doors locked.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq R \leq N
• L_i \in \lbrace 0, 1 \rbrace
• All input values are integers.

Sample Input 1

6 3
1 0 0 1 0 0

Sample Output 1

6

Takahashi can make all doors locked with six switching operations by acting as follows:

• Move to room 2.
• Perform a switching operation on door 2 to lock door 2.
• Move to room 3.
• Perform a switching operation on door 4 to unlock door 4.
• Perform a switching operation on door 3 to lock door 3.
• Move to room 4.
• Perform a switching operation on door 4 to lock door 4.
• Move to room 5.
• Perform a switching operation on door 5 to lock door 5.
• Perform a switching operation on door 6 to lock door 6.

Sample Input 2

2 1
0 0

Sample Output 2

2

Sample Input 3

8 2
0 1 0 0 1 0 1 1

Sample Output 3

8

Problem Statement

There is a restaurant that can accommodate at most K customers simultaneously. In front of this restaurant, there is a side street where one queue is managed.

At time 0, there are no customers in the restaurant, and the queue is also empty.

Today, N groups of customers are scheduled to come, and they are numbered from 1 to N in the order of their arrival. Group i consists of C_i people, joins the end of the queue at time A_i, and leaves the restaurant B_i time units after entering.

Each group enters the restaurant by leaving the queue at the earliest time when both of the following two conditions are satisfied simultaneously:

• The group is at the front of the queue. In other words, the group is the earliest to have joined among those still in the queue at that point.
• When the number of people in that group and all groups currently in the restaurant (including those entering at exactly that time and excluding those leaving) are combined, there are K or fewer people.

Find the time when each group enters the restaurant.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq K \leq 10^7
• 1 \leq A_i, B_i \leq 10^7 (1 \leq i \leq N)
• A_1 < \dots < A_N
• 1 \leq C_i \leq K (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4 10
30 300 3
60 45 4
90 45 5
120 45 2

Sample Output 1

30
60
105
120

The entry and exit of each group proceed as follows:

• At time 30, group 1 joins the queue and immediately enters, making the number of customers in the restaurant 3.
• At time 60, group 2 joins the queue and immediately enters, making the number of customers in the restaurant 7.
• At time 90, group 3 joins the queue.
• At time 105, group 2 leaves, making the number of customers in the restaurant 3. Immediately after, group 3 enters, making the number of customers in the restaurant 8.
• At time 120, group 4 joins the queue and immediately enters, making the number of customers in the restaurant 10.
• At time 150, group 3 leaves, making the number of customers in the restaurant 5.
• At time 165, group 4 leaves, making the number of customers in the restaurant 3.
• At time 330, group 1 leaves, making the number of customers in the restaurant 0.

Sample Input 2

4 10
30 300 10
60 45 2
90 45 3
120 45 4

Sample Output 2

30
330
330
330

The entry and exit of each group proceed as follows:

• At time 30, group 1 joins the queue and immediately enters, making the number of customers in the restaurant 10.
• At time 60, group 2 joins the queue.
• At time 90, group 3 joins the queue.
• At time 120, group 4 joins the queue.
• At time 330, group 1 leaves, making the number of customers in the restaurant 0. Immediately after, groups 2,3,4 enter, making the number of customers in the restaurant 9.
• At time 375, groups 2,3,4 leave, making the number of customers in the restaurant 0.

Sample Input 3

10 24
279290 9485601 1
1094410 8022270 4
1314176 7214745 5
1897674 5924694 10
1921802 5769841 4
2506394 2765234 2
2558629 2727489 9
2681289 4061363 5
3022540 2291905 3
4407692 1313036 8

Sample Output 3

279290
1094410
1314176
1897674
1921802
7691643
7822368
8528921
8528921
10549857

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N.

Q queries are given, so find the answer for each.

In the i-th query, integers L_i and R_i are given, so find \displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j as the answer.

Constraints

• 1 \leq N, Q \leq 3 \times 10^5
• 1 \leq A_i \leq 100
• 1 \leq L_i \leq R_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

24
44
74
3

We explain the first query.

The value to be calculated is \displaystyle\sum_{l = 2}^{4}\sum_{r = l}^{4}\sum_{j = l}^{r} A_j.

• When l = 2, r = 2, \displaystyle\sum_{j = l}^{r} A_j = 1.

• When l = 2, r = 3, \displaystyle\sum_{j = l}^{r} A_j = 4.

• When l = 2, r = 4, \displaystyle\sum_{j = l}^{r} A_j = 7.

• When l = 3, r = 3, \displaystyle\sum_{j = l}^{r} A_j = 3.

• When l = 3, r = 4, \displaystyle\sum_{j = l}^{r} A_j = 6.

• When l = 4, r = 4, \displaystyle\sum_{j = l}^{r} A_j = 3.

From the above, the value to be calculated is (1 + 4 + 7) + (3 + 6) + 3 = 24.

Problem Statement

AtCoder Island has N species of cicadas. Cicadas of species i (1 \leq i \leq N) have mass outbreaks only in years that are multiples of A_i.

Among the Y years from year 1 to year Y, find how many years have mass outbreaks of exactly M species of cicadas.

Constraints

• 1 \leq M \leq N \leq 20
• 1 \leq Y \leq 10^{18}
• 1 \leq A_i \leq 10^{18} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 2 16
4 2 3

Sample Output 1

4

From years 1 to 16, each species of cicada has mass outbreaks in the following years:

• Species 1 cicadas have mass outbreaks in years 4,8,12,16.
• Species 2 cicadas have mass outbreaks in years 2,4,6,8,10,12,14,16.
• Species 3 cicadas have mass outbreaks in years 3,6,9,12,15.

From years 1 to 16, exactly two species of cicadas have mass outbreaks four times in years 4,6,8,16.

Sample Input 2

2 1 122333444422333
1429 73651

Sample Output 2

87266392324

The answer may not fit in a 32-bit integer.

Sample Input 3

20 3 832725971730072237
19639596380058 49098990950145 32732660633430 114564312217005 68738587330203 45825724886802 252041486877411 180029633483865 108017780090319 72011853393546 468077047058049 297867211764213 212762294117295 127657376470377 85104917646918 723391799998803 612100753845141 389518661537817 278227615384155 166936569230493

Sample Output 3

24231

Input values may not fit in a 32-bit integer.

Problem Statement

Find the minimum possible value of a positive integer n that satisfies the following two conditions:

• n is a multiple of K.
• The decimal representation of n contains S as a substring.

T test cases are given, so find the answer for each.

Constraints

• T is an integer.
• 1 \leq T \leq 200
• K is an integer.
• 1 \leq K \leq 10^9
• S is a string consisting of digits (0 - 9).
• The first character of S is not 0.
• 1 \leq |S| \leq 5 \times 10^5
• For each input file, the sum of |S| over all test cases is at most 5 \times 10^5.

Sample Input 1

4
271
414
15
23
155521
1000
920950937
999999999999999999999

Sample Output 1

34146
1230
100000003
1000000999999999999999999999

In the first test case, among positive integers that are multiples of 271, the minimum one whose decimal representation contains 414 as a substring is 34146.

In the second test case, among positive integers that are multiples of 15, the minimum one whose decimal representation contains 23 as a substring is 1230.

In the third test case, among positive integers that are multiples of 155521, the minimum one whose decimal representation contains 1000 as a substring is 100000003.

In the fourth test case, among positive integers that are multiples of 920950937, the minimum one whose decimal representation contains 999999999999999999999 as a substring is 1000000999999999999999999999.