Problem Statement

You are given a string S consisting of lowercase English letters and the character ..
Print the last substring when S is split by .s.
In other words, print the longest suffix of S that does not contain ..

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and ..
• S contains at least one ..
• S does not end with ..

Sample Input 1

atcoder.jp

Sample Output 1

jp

The longest suffix of atcoder.jp that does not contain . is jp.

Sample Input 2

translate.google.com

Sample Output 2

com

S may contain multiple .s.

Sample Input 3

.z

Sample Output 3

z

S may start with ..

Sample Input 4

..........txt

Sample Output 4

txt

S may contain consecutive .s.

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

A bus is in operation. The number of passengers on the bus is always a non-negative integer.

At some point in time, the bus had zero or more passengers, and it has stopped N times since then. At the i-th stop, the number of passengers increased by A_i. Here, A_i can be negative, meaning the number of passengers decreased by -A_i. Also, no passengers got on or off the bus other than at the stops.

Find the minimum possible current number of passengers on the bus that is consistent with the given information.

Constraints

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

Sample Input 1

4
3 -5 7 -4

Sample Output 1

3

If the initial number of passengers was 2, the current number of passengers would be 2 + 3 + (-5) + 7 + (-4) = 3, and the number of passengers on the bus would have always been a non-negative integer.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Sample Input 3

4
-1 1000000000 1000000000 1000000000

Sample Output 3

3000000000

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

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N.

Find the maximum length of a subsequence of A such that the absolute difference between any two adjacent terms is at most D.

A subsequence of a sequence A is a sequence that can be obtained by deleting zero or more elements from A and arranging the remaining elements in their original order.

Constraints

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

Sample Input 1

4 2
3 5 1 2

Sample Output 1

3

The subsequence (3, 1, 2) of A has absolute differences of at most 2 between adjacent terms.

Sample Input 2

5 10
10 20 100 110 120

Sample Output 2

3

Sample Input 3

11 7
21 10 3 19 28 12 11 3 3 15 16

Sample Output 3

6

Problem Statement

You are given N integers A_1, A_2, \dots, A_N.
Find the number of triples of integers (i, j, k) that satisfy the following conditions:

• 1 \le i, j, k \le N
• A_i \times A_j = A_k

Constraints

• 1 \le N \le 1000
• \color{red}{1 \le A_i < 10^{1000}}

Sample Input 1

5
2
3
6
12
24

Sample Output 1

6

The following six triples (i, j, k) satisfy the conditions in the problem statement:

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

Sample Input 2

11
1
2
3
4
5
6
123456789123456789
123456789123456789
987654321987654321
987654321987654321
121932631356500531347203169112635269

Sample Output 2

40

Note that the values of each integer A_i can be huge.

Sample Input 3

9
4
4
4
2
2
2
1
1
1

Sample Output 3

162

Note that there may be duplicates among the values of A_i.

Problem Statement

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

Answer the following Q queries. The i-th query is as follows:

• Find the sum of the elements among A_{L_i},A_{L_i+1},\dots,A_{R_i} that are not greater than X_i.

Here, you need to answer these queries online.
That is, only after you answer the current query is the next query revealed.

For this reason, instead of the i-th query itself, you are given encrypted inputs \alpha_i, \beta_i, \gamma_i for the query. Restore the original i-th query using the following steps and then answer it.

• Let B_0=0 and B_i = (the answer to the i-th query).
• Then, the query can be decrypted as follows:
  • L_i = \alpha_i \oplus B_{i-1}
  • R_i = \beta_i \oplus B_{i-1}
  • X_i = \gamma_i \oplus B_{i-1}

Here, x \oplus y denotes the bitwise XOR of x and y.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 1 \le Q \le 2 \times 10^5
• For the encrypted inputs, the following holds:
  • 0 \le \alpha_i, \beta_i, \gamma_i \le 10^{18}
• For the decrypted queries, the following holds:
  • 1 \le L_i \le R_i \le N
  • 0 \le X_i \le 10^9

Sample Input 1

8
2 0 2 4 0 2 0 3
5
1 8 3
10 12 11
3 3 2
3 6 5
12 0 11

Sample Output 1

9
2
0
8
5

The given sequence is A=(2,0,2,4,0,2,0,3).
This input contains five queries.

• Initially, B_0=0.
• The first query is \alpha = 1, \beta = 8, \gamma = 3.
  • After decryption, we get L_i = \alpha \oplus B_0 = 1, R_i = \beta \oplus B_0 = 8, X_i = \gamma \oplus B_0 = 3.
  • The answer to this query is 9. This becomes B_1.
• The next query is \alpha = 10, \beta = 12, \gamma = 11.
  • After decryption, we get L_i = \alpha \oplus B_1 = 3, R_i = \beta \oplus B_1 = 5, X_i = \gamma \oplus B_1 = 2.
  • The answer to this query is 2. This becomes B_2.
• The next query is \alpha = 3, \beta = 3, \gamma = 2.
  • After decryption, we get L_i = \alpha \oplus B_2 = 1, R_i = \beta \oplus B_2 = 1, X_i = \gamma \oplus B_2 = 0.
  • The answer to this query is 0. This becomes B_3.
• The next query is \alpha = 3, \beta = 6, \gamma = 5.
  • After decryption, we get L_i = \alpha \oplus B_3 = 3, R_i = \beta \oplus B_3 = 6, X_i = \gamma \oplus B_3 = 5.
  • The answer to this query is 8. This becomes B_4.
• The next query is \alpha = 12, \beta = 0, \gamma = 11.
  • After decryption, we get L_i = \alpha \oplus B_4 = 4, R_i = \beta \oplus B_4 = 8, X_i = \gamma \oplus B_4 = 3.
  • The answer to this query is 5. This becomes B_5.