Problem Statement

You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.

Constraints

• 1 \leq N \leq 1000
• -10^9 \leq A_i, B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3 5
2 -6
-5 0
314159265 123456789

Sample Output 1

8
-4
-5
437616054

• The first line should contain A_1 + B_1 = 3 + 5 = 8.
• The second line should contain A_2 + B_2 = 2 + (-6) = -4.
• The third line should contain A_3 + B_3 = (-5) + 0 = -5.
• The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.

Problem Statement

N people labeled 1,2,\dots,N took an exam, and person i scored A_i points.
Only those who scored at least L points pass this exam.
Determine how many people out of the N have passed the exam.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le L \le 1000
• 0 \le A_i \le 1000

Sample Input 1

5 60
60 20 100 90 40

Sample Output 1

3

Five people took the exam. You need to score at least 60 points to pass.

• Person 1 scored 60 points, so they passed.
• Person 2 scored 20 points, so they did not pass.
• Person 3 scored 100 points, so they passed.
• Person 4 scored 90 points, so they passed.
• Person 5 scored 40 points, so they did not pass.

From the above, we can see that three people have passed.

Sample Input 2

4 80
79 78 77 76

Sample Output 2

0

There may be cases no one has passed.

Sample Input 3

10 50
31 41 59 26 53 58 97 93 23 84

Sample Output 3

6

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N and a sequence B=(B_1,B_2,\dots,B_M) of length M. Here, all elements of A and B are pairwise distinct. Determine whether the sequence C=(C_1,C_2,\dots,C_{N+M}) formed by sorting all elements of A and B in ascending order contains two consecutive elements appearing in A.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq A_i, B_j \leq 200
• A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_M are distinct.
• All input values are integers.

Sample Input 1

3 2
3 2 5
4 1

Sample Output 1

Yes

C=(1,2,3,4,5). Since 2 and 3 from A occur consecutively in C, print Yes.

Sample Input 2

3 2
3 1 5
4 2

Sample Output 2

No

C=(1,2,3,4,5). Since no two elements from A occur consecutively in C, print No.

Sample Input 3

1 1
1
2

Sample Output 3

No

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

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

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

Sample Output 2

1 2 200000
1

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le W \le 3 \times 10^8
• 1 \le A_i \le 10^9
• 1 \le B_i \le 1000

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

Problem Statement

You are given an integer N and a string S consisting of 0, 1, and ?. Let T be the set of values that can be obtained by replacing each ? in S with 0 or 1 and interpreting the result as a binary integer. For instance, if S= ?0?, we have T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace.

Print (as a decimal integer) the greatest value in T less than or equal to N. If T does not contain a value less than or equal to N, print -1 instead.

Constraints

• S is a string consisting of 0, 1, and ?.
• The length of S is between 1 and 60, inclusive.
• 1\leq N \leq 10^{18}
• N is an integer.

Sample Input 1

?0?
2

Sample Output 1

1

As shown in the problem statement, T=\lbrace 0,1,4,5\rbrace. Among them, 0 and 1 are less than or equal to N, so you should print the greatest of them, 1.

Sample Input 2

101
4

Sample Output 2

-1

We have T=\lbrace 5\rbrace, which does not contain a value less than or equal to N.

Sample Input 3

?0?
1000000000000000000

Sample Output 3

5

Problem Statement

You are given an undirected graph with N vertices and M edges. The vertices are numbered 1,2,\ldots,N, and the i‑th edge (1 \le i \le M) connects vertices u_i and v_i.

For each k = 1,2,\ldots,N, solve the following problem:

Consider the following operation.

• Choose one vertex, and delete that vertex together with all edges incident to it.

Determine whether one can repeat this operation to satisfy the following condition:

• The set of vertices reachable from vertex 1 by traversing edges consists exactly of the k vertices 1,2,\ldots,k.

If it is possible, find the minimum number of operations required to do so.

Constraints

• 1 \le N \le 2 \times 10^{5}
• 0 \le M \le 3 \times 10^{5}
• 1 \le u_i < v_i \le N\ (1 \le i \le M)
• (u_i,v_i) \ne (u_j,v_j)\ (1 \le i < j \le M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
3
3
2
1
0

For example, for k = 2, deleting the three vertices 3, 4, 5 makes the set of vertices reachable from vertex 1 equal to the two vertices 1, 2. It is impossible with two or fewer deletions, so print 3 on the 2nd line.

For k = 6, deleting zero vertices makes the set of vertices reachable from vertex 1 equal to the six vertices 1,2,\ldots,6, so print 0 on the 6th line.

Sample Input 2

5 4
1 5
2 3
3 4
4 5

Sample Output 2

1
-1
-1
-1
0

Sample Input 3

2 0

Sample Output 3

0
-1

There may be no edges.

Sample Input 4

11 25
6 9
5 9
2 3
1 9
10 11
4 5
9 10
8 9
7 8
3 5
1 7
6 10
4 7
7 9
1 10
4 11
3 8
2 7
3 4
1 8
2 8
3 7
2 10
1 6
6 11

Sample Output 4

5
-1
-1
-1
-1
-1
4
3
2
1
0

Problem Statement

Takahashi has 2N teeth: N upper teeth and N lower teeth.

The length of the i-th upper tooth from the left (1 \leq i \leq N) is U _ i, and the length of the i-th lower tooth from the left (1 \leq i \leq N) is D _ i.

His teeth are said to “fit together well” if both of the following conditions are satisfied:

• There exists an integer H such that U _ i + D _ i = H for every integer i with 1 \leq i \leq N.
• \lvert U _ i - U _ {i+1} \rvert \leq X for every integer i with 1 \leq i < N.

He can perform the following operation any number of times:

• Pay 1 yen to use a tooth-grinding machine, choose exactly one tooth whose length is positive, and reduce its length by 1.

No other method may be used to change the lengths of the teeth.

Find the minimum total amount of money he needs to pay to make his teeth fit together well.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq U _ i \leq 10^9 \ (1 \leq i \leq N)
• 1 \leq D _ i \leq 10^9 \ (1 \leq i \leq N)
• 1 \leq X \leq 10^9
• All input values are integers.

Sample Input 1

4 3
3 1
4 1
5 9
2 6

Sample Output 1

15

Initially, Takahashi’s teeth have the following lengths:

For example, you can make them fit together well in the following way:

It costs 15 yen to achieve these lengths.

It is impossible to make them fit together well with 14 yen or less, so print 15.

Sample Input 2

4 1000000000
3 3
3 3
3 3
3 3

Sample Output 2

0

It is possible that the teeth already fit together well without any changes.

Sample Input 3

4 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1 1

Sample Output 3

5999999994

Note that the answer may exceed the 32-bit integer range.

Sample Input 4

15 128
748 169
586 329
972 529
432 519
408 587
138 249
656 114
632 299
984 755
404 772
155 506
832 854
353 465
387 374
567 385

Sample Output 4

9460