Problem Statement

You are given an integer N between 1 and 9, inclusive, as input.

Concatenate N copies of the digit N and print the resulting string.

Constraints

• N is an integer between 1 and 9, inclusive.

Sample Input 1

3

Sample Output 1

333

Concatenate three copies of the digit 3 to yield the string 333.

Sample Input 2

9

Sample Output 2

999999999

Problem Statement

In the ceremony commemorating ABC400, we want to arrange 400 people in a rectangular formation of A rows and B columns without any gaps.

You are given a positive integer A. Print the value of a positive integer B for which such an arrangement is possible. If there is no such positive integer B, print -1.

Constraints

• A is an integer between 1 and 400, inclusive.

Sample Input 1

10

Sample Output 1

40

We can arrange 400 people in 10 rows and 40 columns.

Sample Input 2

11

Sample Output 2

-1

Sample Input 3

400

Sample Output 3

1

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

Takahashi has N teeth, one in each of the holes numbered 1, 2, \dots, N.
Dentist Aoki will perform Q treatments on these teeth and holes.
In the i-th treatment, hole T_i is treated as follows:

• If there is a tooth in hole T_i, remove the tooth from hole T_i.
• If there is no tooth in hole T_i (i.e., the hole is empty), grow a tooth in hole T_i.

After all treatments are completed, how many teeth does Takahashi have?

Constraints

• All input values are integers.
• 1 \le N, Q \le 1000
• 1 \le T_i \le N

Sample Input 1

30 6
2 9 18 27 18 9

Sample Output 1

28

Initially, Takahashi has 30 teeth, and Aoki performs six treatments.

• In the first treatment, hole 2 is treated. There is a tooth in hole 2, so it is removed.
• In the second treatment, hole 9 is treated. There is a tooth in hole 9, so it is removed.
• In the third treatment, hole 18 is treated. There is a tooth in hole 18, so it is removed.
• In the fourth treatment, hole 27 is treated. There is a tooth in hole 27, so it is removed.
• In the fifth treatment, hole 18 is treated. There is no tooth in hole 18, so a tooth is grown.
• In the sixth treatment, hole 9 is treated. There is no tooth in hole 9, so a tooth is grown.

The final count of teeth is 28.

Sample Input 2

1 7
1 1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

Sample Output 3

5

Problem Statement

You are given a grid of H rows and W columns.
Let (i,j) denote the cell at row i (1 \leq i \leq H) from the top and column j (1 \leq j \leq W) from the left.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W, as follows:

• If the j-th character of S_i is #, cell (i,j) is painted black.
• If the j-th character of S_i is ., cell (i,j) is painted white.
• If the j-th character of S_i is ?, cell (i,j) is not yet painted.

Takahashi wants to paint each not-yet-painted cell white or black so that all the black cells form a rectangle.
More precisely, he wants there to exist a quadruple of integers (a,b,c,d) (1 \leq a \leq b \leq H, 1 \leq c \leq d \leq W) such that:

For each cell (i,j) (1 \leq i \leq H, 1 \leq j \leq W), if a \leq i \leq b and c \leq j \leq d, the cell is black;
otherwise, the cell is white.

Determine whether this is possible.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of #, ., ?.
• There is at least one cell that is already painted black.

Sample Input 1

3 5
.#?#.
.?#?.
?...?

Sample Output 1

Yes

The grid is in the following state. ? indicates a cell that are not yet painted.

By painting cells (1,3), (2,2), and (2,4) black and cells (3,1) and (3,5) white, the black cells can form a rectangle as follows:

Therefore, print Yes.

Sample Input 2

3 3
?##
#.#
##?

Sample Output 2

No

To form a rectangle with all black cells, you would need to paint cell (2,2) black, but it is already painted white.
Therefore, it is impossible to make all black cells form a rectangle, so print No.

Sample Input 3

1 1
#

Sample Output 3

Yes

Problem Statement

You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.

Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.

Sample Input 1

4

Sample Output 1

8

Here are the eight desired quadruples.

• (A,B,C,D)=(1,1,1,3)
• (A,B,C,D)=(1,1,3,1)
• (A,B,C,D)=(1,2,1,2)
• (A,B,C,D)=(1,2,2,1)
• (A,B,C,D)=(1,3,1,1)
• (A,B,C,D)=(2,1,1,2)
• (A,B,C,D)=(2,1,2,1)
• (A,B,C,D)=(3,1,1,1)

Sample Input 2

292

Sample Output 2

10886

Sample Input 3

19876

Sample Output 3

2219958

Problem Statement

There are N pigeons labeled 1, 2, \ldots, N and N nests labeled 1, 2, \ldots, N.

Initially, pigeon i (1 \leq i \leq N) is in nest i.

You will perform Q operations on these pigeons.

There are three types of operations:

• Type 1: You are given integers a and b (1 \leq a \leq N, 1 \leq b \leq N). Take pigeon a out of its current nest and move it to nest b.
• Type 2: You are given integers a and b (1 \leq a < b \leq N). Move all pigeons in nest a to nest b, and move all pigeons in nest b to nest a. These two moves happen simultaneously.
• Type 3: You are given an integer a (1 \leq a \leq N). Pigeon a reports the label of the nest it is currently in.

Print the result of each Type 3 operation in the order the operations are given.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq Q \leq 3 \times 10^5
• Every operation is of Type 1, 2, or 3.
• All operations are valid according to the problem statement.
• There is at least one Type 3 operation.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
5
2
5

In the operations given, the pigeons move as shown in the figure below:

The nest numbers to be reported for the Type 3 operations are 4,5,2,5. Print 4, 5, 2, 5 on separate lines.

Sample Input 2

1 2
1 1 1
3 1

Sample Output 2

1

The destination nest of a Type 1 operation may be the same as the nest the pigeon is currently in.

Sample Input 3

30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8

Sample Output 3

3
15
7

Problem Statement

There is an island of size H \times W, surrounded by the sea.
The island is divided into H rows and W columns of 1 \times 1 sections, and the elevation of the section at the i-th row from the top and the j-th column from the left (relative to the current sea level) is A_{i,j}.

Starting from now, the sea level rises by 1 each year.
Here, a section that is vertically or horizontally adjacent to the sea or a section sunk into the sea and has an elevation not greater than the sea level will sink into the sea.
Here, when a section newly sinks into the sea, any vertically or horizontally adjacent section with an elevation not greater than the sea level will also sink into the sea simultaneously, and this process repeats for the newly sunk sections.

For each i=1,2,\ldots, Y, find the area of the island that remains above sea level i years from now.

Constraints

• 1 \leq H, W \leq 1000
• 1 \leq Y \leq 10^5
• 1 \leq A_{i,j} \leq 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

9
7
6
5
4

Let (i,j) denote the section at the i-th row from the top and the j-th column from the left. Then, the following happens:

• After 1 year, the sea level is higher than now by 1, but there are no sections with an elevation of 1 that are adjacent to the sea, so no sections sink. Thus, the first line should contain 9.
• After 2 years, the sea level is higher than now by 2, and (1,2) sinks into the sea. This makes (2,2) adjacent to a sunken section, and its elevation is not greater than 2, so it also sinks. No other sections sink at this point. Thus, two sections sink, and the second line should contain 9-2=7.
• After 3 years, the sea level is higher than now by 3, and (2,1) sinks into the sea. No other sections sink. Thus, the third line should contain 6.
• After 4 years, the sea level is higher than now by 4, and (2,3) sinks into the sea. No other sections sink. Thus, the fourth line should contain 5.
• After 5 years, the sea level is higher than now by 5, and (3,2) sinks into the sea. No other sections sink. Thus, the fifth line should contain 4.

Therefore, print 9, 7, 6, 5, 4 in this order, each on a new line.

Sample Input 2

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

Sample Output 2

15
7
0

Problem Statement

As the factory manager of Keyence, you want to monitor several sections on a conveyor belt. There are a total of N sections you want to monitor, and the length of the i-th section is D_i meters.

There are two types of sensors to choose from, and below is some information about each sensor.

• Type-j sensor (1\leq j \leq 2): Can monitor a section of length L_j meters. The price is C_j per sensor, and you can use at most K_j sensors of this type in total.

You can divide one section into several sections for monitoring. It is fine if the sections monitored by the sensors overlap, or if they monitor more than the length of the section you want to monitor. For example, when L_1=4 and L_2=2, you can use one type-1 sensor to monitor a section of length 3 meters, or use one type-1 and one type-2 sensor to monitor a section of length 5 meters.

Determine whether it is possible to monitor all N sections, and if it is possible, find the minimum total cost of the necessary sensors.

Constraints

• 1\leq N \leq 100
• 1\leq D_i,L_j \leq 10^5
• 1\leq C_j \leq 10^9
• 1\leq K_j \leq 10^3
• All input values are integers.

Sample Input 1

3
3 5 10
4 3 3
2 2 6

Sample Output 1

17

You can monitor all sections by using three type-1 sensors and four type-2 sensors as follows.

• Use one type-1 sensor to monitor the first section.
• Use one type-1 and one type-2 sensor to monitor the second section.
• Use one type-1 and three type-2 sensors to monitor the third section.

In this case, the total cost of the necessary sensors is 3\times 3 + 2\times 4 = 17, which is the minimum.

Sample Input 2

3
3 5 10
4 3 3
2 2 3

Sample Output 2

-1

Sample Input 3

2
4 8
3 1 100
4 10000 100

Sample Output 3

5

It is fine if one type of sensor is not used at all.