Problem Statement

Streamer Takahashi has decided to stream from L o'clock to R o'clock (using the 24-hour clock).

He has N listeners, and the i-th listener can watch the stream from X_i o'clock to Y_i o'clock.

How many listeners can watch Takahashi's stream from beginning to end?

Constraints

• 1\leq N\leq 100
• 0\leq L\lt R\leq 23
• 0\leq X_i\lt Y_i\leq 23
• All input values are integers.

Sample Input 1

5 19 22
17 23
20 23
19 22
0 23
12 20

Sample Output 1

3

The listeners who can watch Takahashi's stream from beginning to end are the 1st, 3rd, and 4th listeners.

Sample Input 2

3 12 13
0 1
0 1
0 1

Sample Output 2

0

No listeners can watch Takahashi's stream from beginning to end.

Sample Input 3

10 8 14
5 20
14 21
9 21
5 23
8 10
0 14
3 8
2 6
0 16
5 20

Sample Output 3

5

Problem Statement

You are given an integer Y between 1583 and 2023.

Find the number of days in the year Y of the Gregorian calendar.

Within the given range, the year Y has the following number of days:

• if Y is not a multiple of 4, then 365 days;

• if Y is a multiple of 4 but not a multiple of 100, then 366 days;

• if Y is a multiple of 100 but not a multiple of 400, then 365 days;

• if Y is a multiple of 400, then 366 days.

Constraints

• Y is an integer between 1583 and 2023, inclusive.

Sample Input 1

2023

Sample Output 1

365

2023 is not a multiple of 4, so it has 365 days.

Sample Input 2

1992

Sample Output 2

366

1992 is a multiple of 4 but not a multiple of 100, so it has 366 days.

Sample Input 3

1800

Sample Output 3

365

1800 is a multiple of 100 but not a multiple of 400, so it has 365 days.

Sample Input 4

1600

Sample Output 4

366

1600 is a multiple of 400, so it has 366 days.

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.

Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.

• When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
• Otherwise, if the mug is empty, fill the mug with water.
• Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

• 1\leq K\leq 100
• 1\leq G<M\leq 1000
• G, M, and K are integers.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

• Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
• Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
• Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
• Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
• Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.

Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

Problem Statement

You are given a length-N sequence A=(A_1,A_2,\ldots,A_N) of positive integers.

Determine whether A is a geometric progression.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
3 6 12 24 48

Sample Output 1

Yes

A=(3,6,12,24,48).
A is a geometric progression with first term 3, common ratio 2, and five terms.
Therefore, print Yes.

Sample Input 2

3
1 2 3

Sample Output 2

No

A=(1,2,3).
Since A_1 : A_2 = 1 : 2 \neq 2 : 3 = A_2 : A_3, A is not a geometric progression.
Therefore, print No.

Sample Input 3

2
10 8

Sample Output 3

Yes

A is a geometric progression with first term 10, common ratio 0.8, and two terms.
Therefore, print Yes.

Problem Statement

There are N cups, each containing a colorless and transparent liquid.
Specifically, the i-th (1\leq i\leq N) cup contains A_i ml of liquid.
It is known that exactly K of these cups contain sake (rice wine), and the rest contain water.
However, it is not known which cups contain sake.

Takahashi can choose some (one or more) cups and drink all the liquid in them.
Find the minimum number of cups he needs to choose to ensure he drinks at least X ml of sake, regardless of which cups contain sake.
If such a choice is impossible, print -1.

Constraints

• 1 \leq K \leq N \leq 3\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 3\times 10^{14}
• All input values are integers.

Sample Input 1

3 2 5
10 6 8

Sample Output 1

2

Consider the case where Takahashi chooses the first and third cups and drinks them.

Two out of the three cups contain sake, so the following three cases are possible:

• If the first and second cups contain sake

He drinks 10 ml of sake and 8 ml of water.

• If the first and third cups contain sake

He drinks 18 ml of sake.

• If the second and third cups contain sake

He drinks 8 ml of sake and 10 ml of water.

Thus, in all cases, he can drink at least 5 ml of sake.
On the other hand, it is impossible to satisfy the condition by choosing only one cup without knowing which cups contain sake.

Therefore, print 2.

Sample Input 2

2 1 8
6 10

Sample Output 2

-1

If the first cup contained sake, it is impossible to drink 8 ml or more of sake no matter which cups are chosen.
Therefore, print -1.

Sample Input 3

5 3 3000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5

Problem Statement

There are N cells, cell 1, cell 2,\ldots, cell N, arranged in a line. Cell i has an integer A_i\ (i \le A_i \le N) written on it.

For each of s=1,2,\ldots,N, solve the following problem.

• Initially, place a piece on cell s. After performing the operation "let x be the integer written on the cell where the piece is placed, and then move the piece to cell x" 10^{100} times, output the number of the cell where the piece is placed.

Constraints

• 1 \le N \le 5\times10^5
• i \le A_i \le N\ (1 \le i \le N)
• All input values are integers.

Sample Input 1

7
2 4 7 5 5 6 7

Sample Output 1

5 5 7 5 5 6 7

For s=1, the piece moves as shown in the following figure.

When the piece is placed on cell 5, the operation does not move the piece, so the answer for s=1 is 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5

It is possible that the piece never moves.

Sample Input 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

Sample Output 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15

Problem Statement

On the two-dimensional coordinate plane, there is an infinite tiling of 1 \times 1 squares.

Consider drawing a circle of radius R centered at the center of one of these squares. How many of these squares are completely contained inside the circle?

More precisely, find the number of integer pairs (i,j) such that all four points (i+0.5,j+0.5), (i+0.5,j-0.5), (i-0.5,j+0.5), and (i-0.5,j-0.5) are at a distance of at most R from the origin.

Constraints

• 1 \leq R \leq 10^{6}
• All input values are integers.

Sample Input 1

2

Sample Output 1

5

There are a total of five squares completely contained in the circle: the square whose center matches the circle’s center, plus the four squares adjacent to it.

Sample Input 2

4

Sample Output 2

37

Sample Input 3

26

Sample Output 3

2025

Problem Statement

You are given a weighted simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N, and edges are numbered 1 to M. Additionally, a positive integer K is given.
Edge i\ (1\leq i\leq M) connects vertices u_i and v_i and has a weight of w_i.

For a spanning tree T of this graph, the cost of T is defined as the sum, modulo K, of the weights of the edges in T. Find the minimum cost of a spanning tree of this graph.

Constraints

• 2\leq N\leq8
• N-1\leq M\leq\dfrac{N(N-1)}2
• 1\leq K\leq10^{15}
• 1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)
• 0\leq w_i\lt K\ (1\leq i\leq M)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

Sample Output 1

33

The given graph is shown below:

The cost of the spanning tree containing edges 1,3,5,6 is (99+86+81+95)\bmod{328}=361\bmod{328}=33. The cost of every spanning tree of this graph is at least 33, so print 33.

Sample Input 2

6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

Sample Output 2

325437688

Print the cost of the only spanning tree of this graph, which is 325437688.

Sample Input 3

8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

Sample Output 3

11360716373

Note that the input and the answer may not fit into a 32\operatorname{bit} integer.

Problem Statement

The Kingdom of AtCoder is composed of N towns and N-1 roads.
The towns are labeled as Town 1, Town 2, \dots, Town N. Similarly, the roads are labeled as Road 1, Road 2, \dots, Road N-1. Road i connects Towns A_i and B_i bidirectionally, and you have to pay the toll of C_i to go through it. For every pair of different towns (i, j), it is possible to go from Town A_i to Town B_j via the roads.

You are given a sequence D = (D_1, D_2, \dots, D_N), where D_i is the cost to do sightseeing in Town i. Let us define the travel cost E_{i,j} from Town i to Town j as the total toll incurred when going from Town i to Town j, plus D_{j}.

• More formally, E_{i,j} is defined as D_j + \displaystyle\sum_{l=0}^{k-1} c_l, where the shortest path between i and j is i = p_0, p_1, \dots, p_{k-1}, p_k = j and the toll for the road connecting Towns p_{l} and p_{l+1} is c_l.

For every i, find the maximum possible travel cost when traveling from Town i to another town.

• More formally, for every i, find \max_{1 \leq j \leq N, j \neq i} E_{i,j}.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N-1)
• 1 \leq B_i \leq N (1 \leq i \leq N-1)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• It is possible to travel from Town i to Town j via some number of roads, for a pair of integers (i,j) such that 1 \leq i \lt j \leq N.
• All values in input are integers.

Sample Input 1

3
1 2 2
2 3 3
1 2 3

Sample Output 1

8
6
6

The value of E_{i,j} for every ordered pair of towns (i,j) is as follows.

• E_{1,2} = 2 + 2 = 4
• E_{1,3} = 5 + 3 = 8
• E_{2,1} = 2 + 1 = 3
• E_{2,3} = 3 + 3 = 6
• E_{3,1} = 5 + 1 = 6
• E_{3,2} = 3 + 2 = 5

Sample Input 2

6
1 2 3
1 3 1
1 4 4
1 5 1
1 6 5
9 2 6 5 3 100

Sample Output 2

105
108
106
109
106
14

Sample Input 3

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

Sample Output 3

5000000006
4000000006
3000000006
3000000001
4000000001
5000000001