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

You are given a real number X, which is representable using at most three decimal digits, with three decimal digits.
Round X to the nearest integer and print the result.

Constraints

• 0 \leq X < 100
• X is representable using at most three decimal digits.
• X has three decimal digits in input.

Sample Input 1

3.456

Sample Output 1

3

The digit in the first decimal place of 3.456 is 4, so we should round it down to 3.

Sample Input 2

99.500

Sample Output 2

100

Sample Input 3

0.000

Sample Output 3

0

Problem Statement

There is an exam structured as follows.

• The exam consists of N rounds called round 1 to N.
• In each round, you are given an integer score between 0 and 100, inclusive.
• Your final grade is the sum of the N-2 of the scores earned in the rounds excluding the highest and lowest.
  • Formally, let S=(S_1,S_2,\dots,S_N) be the sequence of the scores earned in the rounds sorted in ascending order, then the final grade is S_2+S_3+\dots+S_{N-1}.

Now, N-1 rounds of the exam have ended, and your score in round i was A_i.
Print the minimum score you must earn in round N for a final grade of X or higher.
If your final grade will never be X or higher no matter what score you earn in round N, print -1 instead.
Note that your score in round N can only be an integer between 0 and 100.

Constraints

• All input values are integers.
• 3 \le N \le 100
• 0 \le X \le 100 \times (N-2)
• 0 \le A_i \le 100

Sample Input 1

5 180
40 60 80 50

Sample Output 1

70

Your scores in the first four rounds were 40, 60, 80, and 50.
If you earn a score of 70 in round 5, the sequence of the scores sorted in ascending order will be S=(40,50,60,70,80), for a final grade of 50+60+70=180.
It can be shown that 70 is the minimum score you must earn for a final grade of 180 or higher.

Sample Input 2

3 100
100 100

Sample Output 2

0

Your scores in the first two rounds were 100 and 100.
If you earn a score of 0 in round 3, the sequence of the scores sorted in ascending order will be S=(0,100,100), for a final grade of 100.
Note that the highest score, 100, is earned multiple times, and only one of them is excluded. (The same goes for the lowest score.)
It can be shown that 0 is the minimum score you must earn for a final grade of 100 or higher.

Sample Input 3

5 200
0 0 99 99

Sample Output 3

-1

Your scores in the first four rounds were 0, 0, 99, and 99.
It can be shown that your final grade will never be 200 or higher no matter what score you earn in round 5.

Sample Input 4

10 480
59 98 88 54 70 24 8 94 46

Sample Output 4

45

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

• If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

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

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

• Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
• Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
• Person 3's ID has already been called out by person 1, so nothing happens.
• Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
• Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

• N is an integer.
• 2 \leq N \leq 2 \times 10^5
• S_i is a string consisting of lowercase English letters.
• |S_i| \geq 1
• \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3

• S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
• S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
• S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

Problem Statement

A positive integer X is called a good integer if and only if it satisfies the following condition:

• There exists a pair of positive integers (a,b) such that X = 2^a \times b^2.

For example, 400 is a good integer because 400 = 2^2 \times 10^2.

Given a positive integer N, find the number of good integers between 1 and N, inclusive.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

20

Sample Output 1

5

There are five good integers between 1 and 20: 2, 4, 8, 16, and 18.
Thus, print 5.

Sample Input 2

400

Sample Output 2

24

Sample Input 3

1234567890

Sample Output 3

42413

Note that the input might not fit in a 32-bit integer type.

Problem Statement

There is a grid with H rows and W columns, and each cell is painted white or black.
Let us denote the cell at the i-th row from the top (1\leq i\leq H) and the j-th column from the left (1\leq j\leq W) by cell (i,j).
The state of the grid is given by H strings S_1,S_2,\ldots,S_H of length W consisting of . and #.
If the j-th character of S_i is ., then cell (i,j) is white; if it is #, then cell (i,j) is black.

By repainting some black cells (possibly zero) to white, Takahashi wants to make the grid have no 2\times 2 subgrid consisting only of black cells. More precisely, he wants to satisfy the following condition.

For any integer pair (i,j) with 1\leq i\leq H-1 and 1\leq j\leq W-1, among cells (i,j), (i,j+1), (i+1,j), and (i+1,j+1), at least one is white.

Find the minimum number of cells that need to be repainted white in order for Takahashi to achieve his goal.

You are given T test cases; answer each of them.

Constraints

• 1\leq T\leq 100
• 2\leq H\leq 7
• 2\leq W\leq 7
• Each S_i is a string of length W consisting of . and #.
• T,H,W are integers.

Sample Input 1

2
5 5
####.
##.##
#####
.####
##.#.
2 2
..
..

Sample Output 1

3
0

For the first test case, the initial state of the grid is as shown in the left figure below. By repainting, for example, the three cells with numbers in the right figure below from black to white, the condition can be satisfied.

It is impossible to satisfy the condition by repainting two or fewer cells from the initial state, so output 3 on the 1-st line.

For the second test case, the grid already satisfies the condition from the beginning. Thus, output 0 on the 2-nd line.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

Each square contains an integer. For each i = 1, 2, \ldots, N, the square (r_i, c_i) contains a positive integer a_i. The other square contains a 0.

Initially, there is a piece on the square (R, C). Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied.

• The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved.
• The squares to and from which the piece is moved are in the same row or the same column.

For each i = 1, 2, \ldots, N, print the maximum number of times Takahashi can move the piece when (R, C) = (r_i, c_i).

Constraints

• 2 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq \min(2 \times 10^5, HW)
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• 1 \leq a_i \leq 10^9
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
0
2
0
3
1
0

The grid contains the following integers.

4 7 0
3 0 5
2 5 5

• When (R, C) = (r_1, c_1) = (1, 1), you can move the piece once by moving it as (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_2, c_2) = (1, 2), you cannot move the piece at all.
• When (R, C) = (r_3, c_3) = (2, 1), you can move the piece twice by moving it as (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_4, c_4) = (2, 3), you cannot move the piece at all.
• When (R, C) = (r_5, c_5) = (3, 1), you can move the piece three times by moving it as (3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_6, c_6) = (3, 2), you can move the piece once by moving it as (3, 2) \rightarrow (1, 2).
• When (R, C) = (r_7, c_7) = (3, 3), you cannot move the piece at all.

Sample Input 2

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

Sample Output 2

2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
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