Problem Statement

You are given a positive integer N.

Output N lines. The i-th line (1\le i\le N) should contain Fizz if i is a multiple of 3, and i if i is not a multiple of 3.

Constraints

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

Sample Input 1

4

Sample Output 1

1
2
Fizz
4

The first line should contain 1 since 1 is not a multiple of 3.

The second line should contain 2 since 2 is not a multiple of 3.

The third line should contain Fizz since 3 is a multiple of 3.

The fourth line should contain 4 since 4 is not a multiple of 3.

Sample Input 2

10

Sample Output 2

1
2
Fizz
4
5
Fizz
7
8
Fizz
10

Problem Statement

You are given an integer N. Compute and output the value of 2^N-2N.

Constraints

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

Sample Input 1

1

Sample Output 1

0

The value of N given in this input is 1, so output the value of 2^1 - 2 \times 1, which is 0.

Sample Input 2

2

Sample Output 2

0

The value of N given in this input is 2, so output the value of 2^2 - 2 \times 2, which is 0.

Sample Input 3

11

Sample Output 3

2026

The value of N given in this input is 11, so output the value of 2^{11} - 2 \times 11, which is 2026.

Problem Statement

There is a grid with H rows and W columns; initially, all cells are painted white. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

This grid is considered to be toroidal. That is, (i, 1) is to the right of (i, W) for each 1 \leq i \leq H, and (1, j) is below (H, j) for each 1 \leq j \leq W.

Takahashi is at (1, 1) and facing upwards. Print the color of each cell in the grid after Takahashi repeats the following operation N times.

• If the current cell is painted white, repaint it black, rotate 90^\circ clockwise, and move forward one cell in the direction he is facing. Otherwise, repaint the current cell white, rotate 90^\circ counterclockwise, and move forward one cell in the direction he is facing.

Constraints

• 1 \leq H, W \leq 100
• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

3 4 5

Sample Output 1

.#..
##..
....

The cells of the grid change as follows due to the operations:

....   #...   ##..   ##..   ##..   .#..
.... → .... → .... → .#.. → ##.. → ##..
....   ....   ....   ....   ....   ....

Sample Input 2

2 2 1000

Sample Output 2

..
..

Sample Input 3

10 10 10

Sample Output 3

##........
##........
..........
..........
..........
..........
..........
..........
..........
#........#

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
• 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
• The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
• All values in input are integers.

Sample Input 1

4
2 1 2
2 1 1
2 2 1
2 1 2

Sample Output 1

3

Sample Input 1 contains four sequences:

• Sequence 1 : (1, 2)
• Sequence 2 : (1, 1)
• Sequence 3 : (2, 1)
• Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

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

Sample Output 2

4

Sample Input 2 contains five sequences:

• Sequence 1 : (1)
• Sequence 2 : (1)
• Sequence 3 : (2)
• Sequence 4 : (1, 1)
• Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

1

Problem Statement

A repunit is an integer whose digits are all 1 in decimal representation. The repunits in ascending order are 1, 11, 111, \ldots.

Find the N-th smallest integer that can be expressed as the sum of exactly three repunits.

Constraints

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

Sample Input 1

5

Sample Output 1

113

The integers that can be expressed as the sum of exactly three repunits are 3, 13, 23, 33, 113, \ldots in ascending order. For example, 113 can be expressed as 113 = 1 + 1 + 111.

Note that the three repunits do not have to be distinct.

Sample Input 2

19

Sample Output 2

2333

Sample Input 3

333

Sample Output 3

112222222233

Problem Statement

There are zero or more sensors placed on a grid of H rows and W columns. Let (i, j) denote the square in the i-th row from the top and the j-th column from the left.
Whether each square contains a sensor is given by the strings S_1, S_2, \ldots, S_H, each of length W. (i, j) contains a sensor if and only if the j-th character of S_i is #.
These sensors interact with other sensors in the squares horizontally, vertically, or diagonally adjacent to them and operate as one sensor. Here, a cell (x, y) and a cell (x', y') are said to be horizontally, vertically, or diagonally adjacent if and only if \max(|x-x'|,|y-y'|) = 1.
Note that if sensor A interacts with sensor B and sensor A interacts with sensor C, then sensor B and sensor C also interact.

Considering the interacting sensors as one sensor, find the number of sensors on this grid.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W where each character is # or ..

Sample Input 1

5 6
.##...
...#..
....##
#.#...
..#...

Sample Output 1

3

When considering the interacting sensors as one sensor, the following three sensors exist:

• The interacting sensors at (1,2),(1,3),(2,4),(3,5),(3,6)
• The sensor at (4,1)
• The interacting sensors at (4,3),(5,3)

Sample Input 2

3 3
#.#
.#.
#.#

Sample Output 2

1

Sample Input 3

4 2
..
..
..
..

Sample Output 3

0

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

7

Problem Statement

Do there exist two circles C_1 and C_2 on the xy-plane satisfying all of the following conditions? Here, C_1 and C_2 may coincide.

• The two distinct points (P_x, P_y) and (Q_x, Q_y) lie on the circumference of C_1.
• The two distinct points (R_x, R_y) and (S_x, S_y) lie on the circumference of C_2.
• C_1 and C_2 have the same center.

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

Constraints

• 1 \leq T \leq 5 \times 10^4
• -10^9 \leq P_x,P_y,Q_x,Q_y,R_x,R_y,S_x,S_y \leq 10^9
• (P_x, P_y) \neq (Q_x, Q_y)
• (R_x, R_y) \neq (S_x, S_y)
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes
No

Consider the first test case. As shown in the figure below, if we let C_1 be the circle with center (1,0) and radius 1, and C_2 be the circle with center (1,0) and radius 2, the conditions are satisfied.

For the second test case, letting both C_1 and C_2 be the circle with center (0,0) and radius 1 satisfies the conditions.

Problem Statement

You are given a sequence X of length N where each element is between 1 and N, inclusive, and a sequence A of length N.
Print the result of performing the following operation K times on A.

• Replace A with B such that B_i = A_{X_i}.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 0 \le K \le 10^{18}
• 1 \le X_i \le N
• 1 \le A_i \le 2 \times 10^5

Sample Input 1

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

Sample Output 1

7 2 3 5 1 9 3

In this input, X=(5,2,6,3,1,4,6) and the initial sequence is A=(1,2,3,5,7,9,11).

• After one operation, the sequence is (7,2,9,3,1,5,9).
• After two operations, the sequence is (1,2,5,9,7,3,5).
• After three operations, the sequence is (7,2,3,5,1,9,3).

Sample Input 2

4 0
3 4 1 2
4 3 2 1

Sample Output 2

4 3 2 1

There may be cases where no operations are performed.

Sample Input 3

9 1000000000000000000
3 7 8 5 9 3 7 4 2
9 9 8 2 4 4 3 5 3

Sample Output 3

3 3 3 3 3 3 3 3 3

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

• At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• 1 \le N \le 1500
• 1 \le |X|,|Y_i|,|Z_i| \le 10^9
• The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

• He starts at coordinate 0.
• He moves to coordinate 3 to obtain the hammer of type 3.
• He moves to coordinate 5 to obtain the hammer of type 1.
• He moves to coordinate -2 to destroy the wall of type 1.
• He moves to coordinate -5 to destroy the wall of type 3.
• He moves to coordinate -10 to obtain the hammer of type 2.
• He moves to coordinate 8 to destroy the wall of type 2.
• He moves to coordinate 10, which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507