Problem Statement

Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?

Constraints

• X and Y are integers.
• 1 \le X,Y \le 1000

Sample Input 1

80 94

Sample Output 1

2

• After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
• After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
• After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.

Sample Input 2

1000 63

Sample Output 2

0

The envelope may already have a stamp with enough value.

Sample Input 3

270 750

Sample Output 3

48

Problem Statement

AtCoder Regular Contest (ARC) currently has two divisions: Div. 1 and Div. 2. In ARC Div. 1, participants whose rating is between 1600 and 2999, inclusive, are rated. In ARC Div. 2, participants whose rating is between 1200 and 2399, inclusive, are rated.

You are given positive integers R and X.

Determine whether a person with rating R is rated in ARC Div. X.

Constraints

• 1 \le R \le 4229
• 1 \le X \le 2
• All input values are integers.

Sample Input 1

2000 1

Sample Output 1

Yes

Because 2000 lies between 1600 and 2999, a person with rating 2000 is rated in ARC Div. 1.

Sample Input 2

1000 1

Sample Output 2

No

Because 1000 is less than 1600, a person with rating 1000 is not rated in ARC Div. 1.

Sample Input 3

1500 2

Sample Output 3

Yes

Because 1500 lies between 1200 and 2399, a person with rating 1500 is rated in ARC Div. 2.

Sample Input 4

2800 2

Sample Output 4

No

Because 2800 exceeds 2399, a person with rating 2800 is not rated in ARC Div. 2.

Problem Statement

People 1,2,\dots,N (where N is odd) conducted M votes where each person chooses either 0 or 1.
Each person's vote for each round is given as N strings S_1,S_2,\dots,S_N of length M consisting of 0 and 1, where the j-th character of S_i represents person i's vote content for the j-th vote.

In each vote, people who were in the minority receive 1 point.
More precisely, points are given according to the following rules:

• Suppose x people chose 0 and y people chose 1 in that vote.
  • If x=0 or y=0, everyone receives 1 point for that vote.
  • Otherwise, if x<y, only people who voted 0 in that vote receive 1 point.
  • Otherwise, only people who voted 1 in that vote receive 1 point.
  • Note that since N is odd, x=y never occurs.

After finishing M votes, find all people who have the highest total score from those votes.

Constraints

• N is an odd number satisfying 1 \le N \le 99.
• M is an integer satisfying 1 \le M \le 100.
• S_i is a string of length M consisting of 0 and 1.

Sample Input 1

3 5
11100
10101
01110

Sample Output 1

2 3

In this case, three people conducted five votes.

• In the 1st vote, person 1 voted 1, person 2 voted 1, person 3 voted 0. Thus, only person 3 receives 1 point.
• In the 2nd vote, person 1 voted 1, person 2 voted 0, person 3 voted 1. Thus, only person 2 receives 1 point.
• In the 3rd vote, person 1 voted 1, person 2 voted 1, person 3 voted 1. Thus, everyone receives 1 point.
• In the 4th vote, person 1 voted 0, person 2 voted 0, person 3 voted 1. Thus, only person 3 receives 1 point.
• In the 5th vote, person 1 voted 0, person 2 voted 1, person 3 voted 0. Thus, only person 2 receives 1 point.

As a result, person 1 received a total of 1 points, person 2 received a total of 3 points, and person 3 received a total of 3 points.
Therefore, persons 2 and 3 have the highest total score. Output these in ascending order of person number.

Sample Input 2

5 4
0000
0000
0000
0000
0000

Sample Output 2

1 2 3 4 5

Sample Input 3

7 8
11010011
01000000
01111100
10111000
10011110
10100101
10010110

Sample Output 3

1 2 3

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
• 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
• The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
• All values in input are integers.

Sample Input 1

4
2 1 2
2 1 1
2 2 1
2 1 2

Sample Output 1

3

Sample Input 1 contains four sequences:

• Sequence 1 : (1, 2)
• Sequence 2 : (1, 1)
• Sequence 3 : (2, 1)
• Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

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

Sample Output 2

4

Sample Input 2 contains five sequences:

• Sequence 1 : (1)
• Sequence 2 : (1)
• Sequence 3 : (2)
• Sequence 4 : (1, 1)
• Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

1

Problem Statement

There are N dominoes numbered from 1 to N. The size of domino i is S_i.
Consider arranging some dominoes in a line from left to right and then toppling them. When domino i falls to the right, if the size of the domino placed immediately to the right of domino i is at most 2 S_i, then that domino also falls to the right.

You decided to choose two or more dominoes and arrange them in a line from left to right. The arrangement of dominoes must satisfy the following conditions:

• The leftmost domino is domino 1.
• The rightmost domino is domino N.
• When only domino 1 is toppled to the right, domino N eventually falls to the right as well.

Does an arrangement of dominoes satisfying the conditions exist? If it exists, what is the minimum number of dominoes that need to be arranged?

You are given T test cases, solve the problem for each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
4
1 3 2 5
2
1 100
10
298077099 766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 917827435

Sample Output 1

4
-1
3

For the 1st test case, arranging the dominoes from left to right in the order domino 1, domino 3, domino 2, domino 4 satisfies the conditions in the problem statement. Specifically, for the 3rd condition, when only domino 1 is toppled to the right, the dominoes fall in the following order:

• Domino 3 is placed to the right of domino 1. Since the size of domino 3, S_3 = 2, is not greater than S_1 \times 2 = 1 \times 2 = 2, domino 3 also falls to the right.
• Domino 2 is placed to the right of domino 3. Since the size of domino 2, S_2 = 3, is not greater than S_3 \times 2 = 2 \times 2 = 4, domino 2 also falls to the right.
• Domino 4 is placed to the right of domino 2. Since the size of domino 4, S_4 = 5, is not greater than S_2 \times 2 = 3 \times 2 = 6, domino 4 also falls to the right.

It is impossible to achieve the conditions in the problem statement by arranging 3 or fewer dominoes, so the answer is 4.

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

• L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
• \displaystyle \sum_{i=1}^N X_i = 0.

Constraints

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

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9

Problem Statement

Takahashi is playing a game.

The game consists of N stages numbered 1,2,\ldots,N. Initially, only stage 1 can be played.

For each stage i ( 1\leq i \leq N-1 ) that can be played, you can perform one of the following two actions at stage i:

• Spend A_i seconds to clear stage i. This allows you to play stage i+1.
• Spend B_i seconds to clear stage i. This allows you to play stage X_i.

Ignoring the times other than the time spent to clear the stages, how many seconds will it take at the minimum to be able to play stage N?

Constraints

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

Sample Input 1

5
100 200 3
50 10 1
100 200 5
150 1 2

Sample Output 1

350

By acting as follows, you will be allowed to play stage 5 in 350 seconds.

• Spend 100 seconds to clear stage 1, which allows you to play stage 2.
• Spend 50 seconds to clear stage 2, which allows you to play stage 3.
• Spend 200 seconds to clear stage 3, which allows you to play stage 5.

Sample Input 2

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

Sample Output 2

90

Sample Input 3

6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1

Sample Output 3

5000000000

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits in the decimal notation of n. For example, the digit sum of 2024 is 2+0+2+4=8.
A positive integer n is called a good integer when n is divisible by its digit sum. For example, 2024 is a good integer because it is divisible by its digit sum of 8.
You are given a positive integer N. How many good integers are less than or equal to N?

Constraints

• 1 \leq N \leq 10^{14}
• N is an integer.

Sample Input 1

20

Sample Output 1

13

There are 13 good integers less than or equal to 20: 1,2,3,4,5,6,7,8,9,10,12,18,20.

Sample Input 2

2024

Sample Output 2

409

Sample Input 3

9876543210

Sample Output 3

547452239

Problem Statement

We have a grid with 10^9 rows and 10^9 columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For i=1,2,\ldots,N, a positive integer x_i is written on (r_i,c_i). On the other 10^{18}-N squares, 0 is written.

You choose a square (R,C) and compute the sum S of the integers written on the 2 \times 10^9 - 1 squares that share a row or column with (R,C).

Find the maximum possible value of S.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq r_i,c_i,x_i \leq 10^9
• (r_i,c_i) \neq (r_j,c_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4
1 1 2
1 2 9
2 1 8
3 2 3

Sample Output 1

20

If you choose (2,2) as (R,C), then S will be 20, which is the maximum possible value.

Sample Input 2

1
1 1000000000 1

Sample Output 2

1

Sample Input 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

Sample Output 3

1510053068