Problem Statement

Given integers R, C, and a 2 \times 2 matrix A, print A_{R,C}.

Constraints

• All values in input are integers.
• 1 \le R,C \le 2
• 0 \le A_{i,j} \le 100

Sample Input 1

1 2
1 0
0 1

Sample Output 1

0

We have A_{1,2}=0.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

4

We have A_{2,2}=4.

Sample Input 3

2 1
90 80
70 60

Sample Output 3

70

We have A_{2,1}=70.

Problem Statement

Team Takahashi and Team Aoki are playing a baseball game, with Team Takahashi batting first.
Currently, the game has finished through the top of the ninth inning, and the bottom of the ninth is about to begin.

Team Takahashi scored A_i runs in the top of the i-th inning (1\leq i\leq 9), and Team Aoki scored B_j runs in the bottom of the j-th inning (1\leq j\leq 8).
At the end of the top of the ninth, Team Takahashi's score is not less than Team Aoki's score.
Determine the minimum number of runs Team Aoki needs to score in the bottom of the ninth to win the game.

Here, if the game is tied at the end of the bottom of the ninth, it results in a draw. Therefore, for Team Aoki to win, they must score strictly more runs than Team Takahashi by the end of the bottom of the ninth.
Team Takahashi's score at any point is the total runs scored in the tops of the innings up to that point, and Team Aoki's score is the total runs scored in the bottoms of the innings.

Constraints

• 0\leq A_i, B_j\leq 99
• A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
• All input values are integers.

Sample Input 1

0 1 0 1 2 2 0 0 1
1 1 0 0 0 0 1 0

Sample Output 1

5

At the end of the top of the ninth inning, Team Takahashi has scored seven runs, and Team Aoki has scored three runs.
Therefore, if Team Aoki scores five runs in the bottom of the ninth, the scores will be 7-8, allowing them to win.
Note that scoring four runs would result in a draw and not a victory.

Sample Input 2

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Sample Output 2

1

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

Constraints

• 0 \leq N \leq 21
• N is an integer.

Sample Input 1

3

Sample Output 1

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

Sample Input 2

4

Sample Output 2

0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 0
0 1 1
0 1 2
0 1 3
0 2 0
0 2 1
0 2 2
0 3 0
0 3 1
0 4 0
1 0 0
1 0 1
1 0 2
1 0 3
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 3 0
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 2 0
3 0 0
3 0 1
3 1 0
4 0 0

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

• 2 \leq N \leq 100
• -1000 \leq x_i,y_i \leq 1000
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 0
0 1
1 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

5
315 271
-2 -621
-205 -511
-952 482
165 463

Sample Output 2

1455.7159750446

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

• 1 \leq K \leq N \leq 10^5
• 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
• All values in input are integers.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• 1 \leq N \leq 200000
• 1 \leq S_i,T_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

• if the j-th character of S_i is ., square (i,j) is ice;
• if the j-th character of S_i is #, square (i,j) is rock.

The outer periphery of this grid (all squares in the 1-st row, N-th row, 1-st column, M-th column) is rock.

Initially, the player rests on the square (2,2), which is ice.
The player can make the following move zero or more times.

• First, specify the direction of movement: up, down, left, or right.
• Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
  • if the next square in the direction of movement is ice, go to that square and keep moving;
  • if the next square in the direction of movement is rock, stay in the current square and stop moving.

Find the number of ice squares the player can touch (pass or rest on).

Constraints

• 3 \le N,M \le 200
• S_i is a string of length M consisting of # and ..
• Square (i, j) is rock if i=1, i=N, j=1, or j=M.
• Square (2,2) is ice.

Sample Input 1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

Sample Output 1

12

For instance, the player can rest on (5,5) by moving as follows:

• (2,2) \rightarrow (5,2) \rightarrow (5,5).

The player can pass (2,4) by moving as follows:

• (2,2) \rightarrow (2,5), passing (2,4) in the process.

The player cannot pass or rest on (3,4).

Sample Input 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

Sample Output 2

215

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

There is a grid with N rows and N columns. We denote by (i, j) the square at the i-th (1 \leq i \leq N) row from the top and j-th (1 \leq j \leq N) column from the left.
Square (i, j) has a non-negative integer a_{i, j} written on it.

When you are at square (i, j), you can move to either square (i+1, j) or (i, j+1). Here, you are not allowed to go outside the grid.

Find the number of ways to travel from square (1, 1) to square (N, N) such that the exclusive logical sum of the integers written on the squares visited (including (1, 1) and (N, N)) is 0.

Constraints

• 2 \leq N \leq 20
• 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
• All values in the input are integers.

Sample Input 1

3
1 5 2
7 0 5
4 2 3

Sample Output 1

2

The following two ways satisfy the condition:

• (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3);
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3).

Sample Input 2

2
1 2
2 1

Sample Output 2

0

Sample Input 3

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

Sample Output 3

24307