Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

• 1 \leq N \leq 10^{11}
• N is an integer.

Sample Input 1

4

Sample Output 1

5

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

100

Sample Output 2

323

Sample Input 3

100000000000

Sample Output 3

5745290566750

Problem Statement

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

Answer Q queries given in the following format.

• You are given integers L, R, and X. Find the number of elements among A_L, \ldots, A_R whose values are equal to X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq N
• 1 \leq Q \leq 2\times 10^5
• 1\le L \leq R \leq N, 1 \leq X \leq N, for each query.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2
0
0
1

In the first query, two of (A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5) have values equal to 1.

In the second query, zero of (A_2,A_3,A_4) =(1,4,1) have values equal to 3.

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. The dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i gains frustration of k, where k is the minimum integer such that Dish i is in front of either Person (i-k) \bmod N or Person (i+k) \bmod N.
Find the minimum possible sum of frustration of the N people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

2

The figure below shows the table after one operation.

Here, the sum of their frustration is 2 because:

• Person 0 gains a frustration of 1 since Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 gains a frustration of 0 since Dish 1 is in front of Person 1\ (=(1+0) \bmod 4);
• Person 2 gains a frustration of 0 since Dish 2 is in front of Person 2\ (=(2+0) \bmod 4);
• Person 3 gains a frustration of 1 since Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

We cannot make the sum of their frustration less than 2, so the answer is 2.

Sample Input 2

3
0 1 2

Sample Output 2

0

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

20

Problem Statement

We have a grid with H rows and W columns. Each square is painted either white or black. For each integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, the color of the square at the i-th row from the top and j-th column from the left (we simply denote this square by Square (i, j)) is represented by A_{i, j}. Square (i, j) is white if A_{i, j} = 0, and black if A_{i, j} = 1.

You may perform the following operations any number of (possibly 0) times in any order:

• Choose an integer i such that 1 \leq i \leq H, pay R_i yen (the currency in Japan), and invert the color of each square in the i-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)
• Choose an integer j such that 1 \leq j \leq W, pay C_j yen, and invert the color of each square in the j-th column from the left in the grid.

Print the minimum total cost to satisfy the following condition:

• There exists a path from Square (1, 1) to Square (H, W) that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square (1, 1) and Square (H, W)) have the same color.

We can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem.

Constraints

• 2 \leq H, W \leq 2000
• 1 \leq R_i \leq 10^9
• 1 \leq C_j \leq 10^9
• A_{i, j} \in \lbrace 0, 1\rbrace
• All values in input are integers.

Sample Input 1

3 4
4 3 5
2 6 7 4
0100
1011
1010

Sample Output 1

9

We denote a white square by 0 and a black square by 1. On the initial grid, you can pay R_2 = 3 yen to invert the color of each square in the 2-nd row from the top to make the grid:

0100
0100
1010

Then, you can pay C_2 = 6 yen to invert the color of each square in the 2-nd row from the left to make the grid:

0000
0000
1110

Now, there exists a path from Square (1, 1) to Square (3, 4) such that all squares in the path have the same color (such as the path (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)). The total cost paid is 3+6 = 9 yen, which is the minimum possible.

Sample Input 2

15 20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78
39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18
01011100110000001111
10101111100010011000
11011000011010001010
00010100011111010100
11111001101010001011
01111001100101011100
10010000001110101110
01001011100100101000
11001000100101011000
01110000111011100101
00111110111110011111
10101111111011101101
11000011000111111001
00011101011110001101
01010000000001000000

Sample Output 2

125