Problem Statement

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at A o'clock every day.

Takahashi, who lives in the Kingdom of AtCoder, goes to bed at B o'clock and wakes up at C o'clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

Constraints

• 0\leq A,B,C\lt 24
• A, B, and C are pairwise different.
• All input values are integers.

Sample Input 1

21 8 14

Sample Output 1

Yes

Takahashi goes to bed at 8 o'clock and wakes up at 14 o'clock every day. He is awake at 21 o'clock, so he can shout his love for takoyaki every day. Therefore, print Yes.

Sample Input 2

0 21 7

Sample Output 2

No

Takahashi goes to bed at 21 o'clock and wakes up at 7 o'clock every day. He is not awake at 0 o'clock, so he cannot shout his love for takoyaki every day. Therefore, print No.

Sample Input 3

10 7 17

Sample Output 3

No

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

• First, he painted the part from X=L_1 to X=R_1 red.
• Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

• 0\leq L_1<R_1\leq 100
• 0\leq L_2<R_2\leq 100
• All values in input are integers.

Sample Input 1

0 3 1 5

Sample Output 1

2

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

0

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

0

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

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

Sample Input 2

5 1 5

Sample Output 2

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

Sample Input 3

4 4 1

Sample Output 3

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

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

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

Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

• 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
• 2 p: Find the coordinates of part p.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 2\times 10^5
• For the first type of query, C is one of R, L, U, and D.
• For the second type of query, 1\leq p \leq N.
• All numerical input values are integers.

Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

• If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.

• If the j-th character of S_i is ., then (i, j) is an empty cell without a player.

• If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

• Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

• N is an integer between 2 and 60, inclusive.
• S_i is a string of length N consisting of P, ., and #.
• There are exactly two pairs (i, j) where the j-th character of S_i is P.

Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

3

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

• Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).

• Choose up. Player 1 does not move, and Player 2 moves to (3, 2).

• Choose left. Player 1 does not move, and Player 2 moves to (3, 1).

Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

Sample Output 3

10

Problem Statement

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N, where all elements are initially set to 0. Also, there is a set S, which is initially empty.

Perform the following Q queries in order. Find the value of each element in the sequence A after processing all Q queries. The i-th query is in the following format:

• An integer x_i is given. If the integer x_i is contained in S, remove x_i from S. Otherwise, insert x_i to S. Then, for each j=1,2,\ldots,N, add |S| to A_j if j\in S.

Here, |S| denotes the number of elements in the set S. For example, if S=\lbrace 3,4,7\rbrace, then |S|=3.

Constraints

• 1\leq N,Q\leq 2\times10^5
• 1\leq x_i\leq N
• All given numbers are integers.

Sample Input 1

3 4
1 3 3 2

Sample Output 1

6 2 2

In the first query, 1 is inserted to S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(1,0,0).

In the second query, 3 is inserted to S, making S=\lbrace 1,3\rbrace. Then, |S|=2 is added to A_1 and A_3. The sequence becomes A=(3,0,2).

In the third query, 3 is removed from S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(4,0,2).

In the fourth query, 2 is inserted to S, making S=\lbrace 1,2\rbrace. Then, |S|=2 is added to A_1 and A_2. The sequence becomes A=(6,2,2).

Eventually, the sequence becomes A=(6,2,2).

Sample Input 2

4 6
1 2 3 2 4 2

Sample Output 2

15 9 12 7

Problem Statement

Let the similarity f(X,Y) between two strings X and Y be the length of their longest common prefix.
For example, the similarity between abc and axbc is 1, and the similarity between aaa and aaaa is 3.

You are given a string S of length N. Let S_i be the suffix of S beginning with the i-th character of S. For each k=1,\ldots,N, find f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N).

Constraints

• 1 \leq N \leq 10^6
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3
abb

Sample Output 1

3
3
2

S_1 is abb, S_2 is bb, and S_3 is b.

• For k=1: f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3.
• For k=2: f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3.
• For k=3: f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2.

Sample Input 2

11
mississippi

Sample Output 2

11
16
14
12
13
11
9
7
4
3
4