Problem Statement

There is a bottle of disinfectant that can disinfect exactly M hands.

N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.

Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq H_i \leq 100
• All input values are integers.

Sample Input 1

5 10
2 3 2 5 3

Sample Output 1

3

The aliens disinfect their hands in the following steps:

• The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
• The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
• The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
• The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.

Thus, the first three aliens can disinfect all of their hands, so print 3.

Sample Input 2

5 10
2 3 2 3 5

Sample Output 2

4

Sample Input 3

1 5
1

Sample Output 3

1

All aliens can disinfect their hands.

Problem Statement

There are N buildings aligned in a row. The i-th building from the left has a height of H_i.

Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.

Constraints

• 1 \leq N \leq 100
• 1 \leq H_i \leq 100
• All input values are integers.

Sample Input 1

4
3 2 5 2

Sample Output 1

3

The building taller than the first one from the left is the third one from the left.

Sample Input 2

3
4 3 2

Sample Output 2

-1

No building is taller than the first one from the left.

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

6

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

There are N customers numbered 1 to N, and M canned juices numbered 1 to M.

Customer i (1 \leq i \leq N) has a wish list of length L_i. The j-th item (1 \leq j \leq L_i) from the top of customer i's wish list is canned juice X_{i,j}. For any customer i, the numbers X_{i, 1}, \dots, X_{i, L_i} on customer i's wish list are distinct.

Customers 1, \dots, N, in this order, will now choose their beverages, following the procedure below.

• If the customer's wish list contains a canned juice that has not yet been chosen by anyone at that point, they choose the canned juice whose number appears earliest in their wish list. Otherwise, they choose water.

Determine which beverage each customer gets.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq L_i \leq M (1 \leq i \leq N)
• 1 \leq X_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq L_i)
• X_{i, 1}, \dots, X_{i, L_i} are distinct. (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
2
0
5

Among the numbers on customer 1's wish list, the canned juices not yet chosen by anyone are 3, 1, 2. The one appearing earliest in the list is 3, so customer 1 chooses canned juice 3.

Among the numbers on customer 2's wish list, the canned juices not yet chosen by anyone are 2, 1. The one appearing earliest in the list is 2, so customer 2 chooses canned juice 2.

For the numbers on customer 3's wish list, all corresponding canned juices have already been chosen by someone at that point. Thus, customer 3 chooses water.

Among the numbers on customer 4's wish list, the canned juices not yet chosen by anyone are 5, 1. The one appearing earliest in the list is 5, so customer 4 chooses canned juice 5.

Sample Input 2

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

Sample Output 2

3
5
1
4
2
0

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

• 1 \leq N \leq 2\times 10^5
• The records are consistent. That is:
  • 1\leq A_i \leq 2i-1.
  • A_i are distinct integers.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

• Amoeba 1 is zero generations away from amoeba 1.
• Amoeba 2 is one generation away from amoeba 1.
• Amoeba 3 is one generation away from amoeba 1.
• Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
• Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

• 4 \leq N \leq 2000
• 0 \leq x_i, y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output 1

3

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.

Sample Input 2

4
0 1
1 2
2 3
3 4

Sample Output 2

0

Sample Input 3

7
0 1
1 0
2 0
2 1
2 2
3 0
3 2

Sample Output 3

1

Problem Statement

You are given an integer M and N pairs of integers (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
For all i, it holds that 1 \leq A_i \lt B_i \leq M.

A sequence S is said to be a good sequence if the following conditions are satisfied:

• S is a contiguous subsequence of the sequence (1,2,3,..., M).
• For all i, S contains at least one of A_i and B_i.

Let f(k) be the number of possible good sequences of length k.
Enumerate f(1), f(2), \dots, f(M).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq M
• All values in input are integers.

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

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

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

5 9
1 5
1 7
5 6
5 8
2 6

Sample Output 3

0 0 1 2 4 4 3 2 1

Problem Statement

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

Find the number, modulo 998244353, of integer sequences B=(B_1, B_2, \ldots, B_N) that can be obtained by rearranging A and satisfy the following condition:

• B_{i+1}\geq B_i-D holds for all i\ (1\leq i\leq N-1).

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq D\leq 10^6
• 1\leq A_i\leq 10^6
• All input values are integers.

Sample Input 1

4 1
5 2 1 2

Sample Output 1

3

The integer sequences satisfying the condition are (1,2,2,5),(2,1,2,5),(2,2,1,5), which are three sequences.

Sample Input 2

5 10
20 40 60 80 100

Sample Output 2

1

Sample Input 3

15 12345
18270 31252 27543 31406 22271 13402 12279 25697 18349 27615 39360 22790 32581 23990 36154

Sample Output 3

858152905