Problem Statement

There is a stack of N cards, and the i-th card from the top has an integer A_i written on it.

You take K cards from the bottom of the stack and place them on top of the stack, maintaining their order.

Print the integers written on the cards from top to bottom after the operation.

Constraints

• 1 \leq K < N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

3 4 5 1 2

Initially, the integers written on the cards are 1,2,3,4,5 from top to bottom.

After taking three cards from the bottom of the stack and placing them on top, the integers written on the cards become 3,4,5,1,2 from top to bottom.

Sample Input 2

6 2
1 2 1 2 1 2

Sample Output 2

1 2 1 2 1 2

The integers written on the cards are not necessarily distinct.

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

Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:

• It is a region consisting of nine horizontal rows and nine vertical columns.
• All the 18 cells in the top-left and bottom-right three-by-three regions are black.
• All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.

It is not allowed to rotate a TaK Code.

You are given a grid with N horizontal rows and M vertical columns. The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..

Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.

Constraints

• 9 \leq N,M \leq 100
• N and M are integers.
• S_i is a string of length M consisting of . and #.

Sample Input 1

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

Sample Output 1

1 1
1 10
7 7
10 2

A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.

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

Sample Input 2

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

Sample Output 2

1 1

Sample Input 3

18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

Sample Output 3

There may be no region that satisfies the conditions of TaK Code.

Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• A_i are distinct.
• All values in input are integers.

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

3

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

5

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9
• 0 \leq Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All X_i and Y_i are integers.
• S is a string of length N consisting of L and R.

Sample Input 1

3
2 3
1 1
4 1
RRL

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

2
1 1
2 1
RR

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Sample Output 3

Yes

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.

Find the number of integers i between 1 and N (inclusive) such that:

• A contains exactly K distinct integers greater than A_i.

Constraints

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

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

2
1
2
1
0
0

For example, we will find the answer for K=2.

• Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
• Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
• Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
• Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
• Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
• Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).

Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3

2
1
2
1
2
1
1
0
0
0

Problem Statement

You are given a sequence of non-negative integers A=(A_1,\ldots,A_N) of length N. Find the number of pairs of integers (i,j) that satisfy both of the following conditions:

• 1\leq i < j\leq N
• A_i A_j is a square number.

Here, a non-negative integer a is called a square number when it can be expressed as a=d^2 using some non-negative integer d.

Constraints

• All inputs are integers.
• 2\leq N\leq 2\times 10^5
• 0\leq A_i\leq 2\times 10^5

Sample Input 1

5
0 3 2 8 12

Sample Output 1

6

Six pairs of integers, (i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4), satisfy the conditions.

For example, A_2A_5=36, and 36 is a square number, so the pair (i,j)=(2,5) satisfies the conditions.

Sample Input 2

8
2 2 4 6 3 100 100 25

Sample Output 2

7

Problem Statement

You are given N points (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) on a two-dimensional plane, and a non-negative integer D.

Find the number of integer pairs (x, y) such that \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq D \leq 10^6
• -10^6 \leq x_i, y_i \leq 10^6
• (x_i, y_i) \neq (x_j, y_j) for i \neq j.
• All input values are integers.

Sample Input 1

2 3
0 0
1 0

Sample Output 1

8

The following figure visualizes the input and the answer for Sample 1. The blue points represent the input. The blue and red points, eight in total, satisfy the condition in the statement.

Sample Input 2

2 0
0 0
2 0

Sample Output 2

0

Sample Input 3

6 100
9 -6
10 -1
2 10
-1 7
-7 5
-1 -4

Sample Output 3

419

Problem Statement

You are given a positive integer N and a permutation P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).

You are given an integer K. Find the number of pairs of integers (l,r) satisfying the following two conditions.

• 1\le l\le r\le N
• The inversion number of the sequence (P _ l,P _ {l+1},\ldots,P _ r) equals K.

Constraints

• 1\le N\le5\times10 ^ 5
• 0\le K\le\dfrac{N(N-1)}2
• 1\le P _ i\le N\ (1\le i\le N)
• P _ i\ne P _ j\ (1\le i\lt j\le N)
• All input values are integers.

Sample Input 1

7 3
6 3 2 1 7 5 4

Sample Output 1

5

For example, the inversion number of the sequence (P _ 1,P _ 2,P _ 3)=(6,3,2) is 3, so (l,r)=(1,3) satisfies the conditions. The other pairs satisfying the conditions are (l,r)=(2,4),(2,5),(4,7),(5,7), so output 5.

Sample Input 2

4 1
1 2 3 4

Sample Output 2

0

The inversion number of every contiguous subsequence of P is 0, so there are no pairs (l,r) satisfying the conditions. Thus, output 0.

Sample Input 3

25 18
14 19 24 8 12 11 6 5 3 13 22 15 17 2 9 4 7 18 10 25 23 16 1 20 21

Sample Output 3

3