Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

• 1 \leq a, b, c \leq 100
• All values in input are integers.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes

Problem Statement

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq N\times 26
• All values in input are integers.

Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.

Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.

Problem Statement

We have a sequence of length N consisting of positive integers: A=(A_1,\ldots,A_N). Any two adjacent terms have different values.

Let us insert some numbers into this sequence by the following procedure.

1. If every pair of adjacent terms in A has an absolute difference of 1, terminate the procedure.
2. Let A_i, A_{i+1} be the pair of adjacent terms nearest to the beginning of A whose absolute difference is not 1.
   • If A_i < A_{i+1}, insert A_i+1,A_i+2,\ldots,A_{i+1}-1 between A_i and A_{i+1}.
   • If A_i > A_{i+1}, insert A_i-1,A_i-2,\ldots,A_{i+1}+1 between A_i and A_{i+1}.
3. Return to step 1.

Print the sequence when the procedure ends.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• A_i \neq A_{i+1}
• All values in the input are integers.

Sample Input 1

4
2 5 1 2

Sample Output 1

2 3 4 5 4 3 2 1 2

The initial sequence is (2,5,1,2). The procedure goes as follows.

• Insert 3,4 between the first term 2 and the second term 5, making the sequence (2,3,4,5,1,2).
• Insert 4,3,2 between the fourth term 5 and the fifth term 1, making the sequence (2,3,4,5,4,3,2,1,2).

Sample Input 2

6
3 4 5 6 5 4

Sample Output 2

3 4 5 6 5 4

No insertions may be performed.

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

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

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

Problem Statement

There is a deck consisting of N face-down cards with an integer from 1 through N written on them. The integer on the i-th card from the top is P_i.

Using this deck, you will perform N moves, each consisting of the following steps:

• Draw the topmost card from the deck. Let X be the integer written on it.
• Stack the drawn card, face up, onto the card with the smallest integer among the face-up topmost cards on the table with an integer greater than or equal to X written on them. If there is no such card on the table, put the drawn card on the table, face up, without stacking it onto any card.
• Then, if there is a pile consisting of K face-up cards on the table, eat all those cards. The eaten cards all disappear from the table.

For each card, find which of the N moves eats it. If the card is not eaten until the end, report that fact.

Constraints

• All values in input are integers.
• 1 \le K \le N \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N) (i.e. a sequence obtained by rearranging (1,2,\dots,N)).

Sample Input 1

5 2
3 5 2 1 4

Sample Output 1

4
3
3
-1
4

In this input, P=(3,5,2,1,4) and K=2.

• In the 1-st move, the card with 3 written on it is put on the table, face up, without stacked onto any card.
• In the 2-nd move, the card with 5 written on it is put on the table, face up, without stacked onto any card.
• In the 3-rd move, the card with 2 written on it is stacked, face up, onto the card with 3 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 2 and 3 from the top are written, so these cards are eaten.
• In the 4-th move, the card with 1 written on it is stacked, face up, onto the card with 5 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 1 and 5 from the top are written, so these cards are eaten.
• In the 5-th move, the card with 4 written on it is put on the table, face up, without stacked onto any card.
• The card with 4 written on it was not eaten until the end.

Sample Input 2

5 1
1 2 3 4 5

Sample Output 2

1
2
3
4
5

If K=1, every card is eaten immediately after put on the table within a single move.

Sample Input 3

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

Sample Output 3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

Problem Statement

You have a grid with H rows from top to bottom and W columns from left to right. We denote by (i, j) the square at the i-th row from the top and j-th column from the left. (i,j)\ (1\leq i\leq H,1\leq j\leq W) has an integer A _ {i,j} between 1 and N written on it.

You are given integers h and w. For all pairs (k,l) such that 0\leq k\leq H-h and 0\leq l\leq W-w, solve the following problem:

• If you black out the squares (i,j) such that k\lt i\leq k+h and l\lt j\leq l+w, how many distinct integers are written on the squares that are not blacked out?

Note, however, that you do not actually black out the squares (that is, the problems are independent).

Constraints

• 1 \leq H,W,N \leq 300
• 1 \leq h \leq H
• 1 \leq w \leq W
• (h,w)\neq(H,W)
• 1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4 4 3
5 3 4

The given grid is as follows:

For example, when (k,l)=(0,0), four distinct integers 1,3,4, and 5 are written on the squares that are not blacked out, so 4 is the answer.

Sample Input 2

5 6 9 3 4
7 1 5 3 9 5
4 5 4 5 1 2
6 1 6 2 9 7
4 7 1 5 8 8
3 4 3 3 5 3

Sample Output 2

8 8 7
8 9 7
8 9 8

Sample Input 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

Sample Output 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17

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