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

Given integers A and B, print the value A^B.

Constraints

• 1 \leq A, B \leq 9
• All values in the input are integers.

Sample Input 1

4 3

Sample Output 1

64

4^3 = 64, so 64 should be printed.

Sample Input 2

5 5

Sample Output 2

3125

Sample Input 3

8 1

Sample Output 3

8

Problem Statement

How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?

Constraints

• 0 \leq S \leq 100
• 0 \leq T \leq 10000
• S and T are integers.

Sample Input 1

1 0

Sample Output 1

4

The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.

Sample Input 2

2 5

Sample Output 2

10

Sample Input 3

10 10

Sample Output 3

213

Sample Input 4

30 100

Sample Output 4

2471

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

You are given a string S consisting of uppercase English letters.
Apply the following procedure to S, and then output the resulting string:

As long as the string contains WA as a (contiguous) substring, repeat the following operation:

• Among all occurrences of WA in the string, replace the leftmost one with AC.

It can be proved under the constraints of this problem that this operation is repeated at most a finite number of times.

Constraints

• S is a string of uppercase English letters with length between 1 and 3\times 10^5, inclusive.

Sample Input 1

WACWA

Sample Output 1

ACCAC

Initially, the string is S= WACWA.
This string contains WA as a substring in two places: from the 1st to the 2nd character, and from the 4th to the 5th character.
In the first operation, we replace the leftmost occurrence (the substring from the 1st to the 2nd character) with AC, resulting in ACCWA.
After the first operation, the string contains WA as a substring in exactly one place: from the 4th to the 5th character.
In the second operation, we replace it with AC, resulting in ACCAC.
Since ACCAC does not contain WA as a substring, the procedure ends. Therefore, we output ACCAC.

Sample Input 2

WWA

Sample Output 2

ACC

Initially, the string is S= WWA.
This string contains WA as a substring in exactly one place: from the 2nd to the 3rd character.
In the first operation, we replace it with AC, resulting in WAC.
Then, after the first operation, the string contains WA in exactly one place: from the 1st to the 2nd character.
In the second operation, we replace it with AC, resulting in ACC.
Since ACC does not contain WA as a substring, the procedure ends. Therefore, we output ACC.

Sample Input 3

WWWWW

Sample Output 3

WWWWW

Since S does not contain WA as a substring from the start, no operations are performed and the procedure ends immediately. Therefore, we output WWWWW.

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

• 1 \leq N \leq 5 \times 10^5
• |A_i| \leq 10^9 (i=1,2,\dots,N)
• |B_j| \leq 10^9 (j=1,2,\dots,N)
• All input values are integers.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33

Problem Statement

You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:

• i \times j is a square number.

Constraints

• 1 \le N \le 2 \times 10^5
• N is an integer.

Sample Input 1

4

Sample Output 1

6

The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.

On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.

Sample Input 2

254

Sample Output 2

896

Problem Statement

There is a grid with H rows and W columns. Initially, all cells are painted with color 0.

You will perform the following operations in the order i = 1, 2, \ldots, M.

• If T_i = 1, repaint all cells in the A_i-th row with color X_i.

• If T_i = 2, repaint all cells in the A_i-th column with color X_i.

After all operations are completed, for each color i that exists on the grid, find the number of cells that are painted with color i.

Constraints

• 1 \leq H, W, M \leq 2 \times 10^5
• T_i \in \lbrace 1, 2 \rbrace
• 1 \leq A_i \leq H for each i such that T_i = 1,
• 1 \leq A_i \leq W for each i such that T_i = 2.
• 0 \leq X_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
0 5
2 4
5 3

The operations will change the colors of the cells in the grid as follows:

0000   0000   0000   0000   0000
0000 → 5555 → 5550 → 5550 → 5550 
0000   0000   0000   3333   2222

Eventually, there are five cells painted with color 0, four with color 2, and three with color 5.

Sample Input 2

1 1 5
1 1 1
1 1 10
2 1 100
1 1 1000
2 1 10000

Sample Output 2

1
10000 1

Sample Input 3

5 5 10
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
2 1 6
2 2 7
2 3 8
2 4 9
2 5 10

Sample Output 3

5
6 5
7 5
8 5
9 5
10 5

Problem Statement

There are N sequences of length M, denoted as A_1, A_2, \ldots, A_N. The i-th sequence is represented by M integers A_{i,1}, A_{i,2}, \ldots, A_{i,M}.

Two sequences X and Y of length M are said to be similar if and only if the number of indices i (1 \leq i \leq M) such that X_i = Y_i is odd.

Find the number of pairs of integers (i,j) satisfying 1 \leq i < j \leq N such that A_i and A_j are similar.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 2000
• 1 \leq A_{i,j} \leq 999
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 3 4
2 3 4

Sample Output 1

1

The pair (i,j) = (1,2) satisfies the condition because there is only one index k such that A_{1,k} = A_{2,k}, which is k=1.

The pairs (i,j) = (1,3), (2,3) do not satisfy the condition, making (1,2) the only pair that does.

Sample Input 2

6 5
8 27 27 10 24
27 8 2 4 5
15 27 26 17 24
27 27 27 27 27
27 7 22 11 27
19 27 27 27 27

Sample Output 2

5