Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

• S is a string consisting of v and w.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

vvwvw

Sample Output 1

7

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12

Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

• abc is a 3-digit integer abc none of whose digits is 0.

Sample Input 1

123

Sample Output 1

666

We have 123+231+312=666.

Sample Input 2

999

Sample Output 2

2997

We have 999+999+999=2997.

Problem Statement

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq D \leq 100
• N and D are integers.
• S_i is a string of length D consisting of o and x.

Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

2

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.

Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

1

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)

Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

0

Print 0 if no day can be chosen.

Sample Input 4

1 7
ooooooo

Sample Output 4

7

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

5

Problem Statement

There are two grids S and T, each with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell of grids S and T is colored either white or black. Cell (i,j) of S is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies to T.

You may perform the following two types of operations any number of times in any order. Find the minimum number of operations required to make grid S identical to grid T.

• Choose one cell of grid S and change its color.
• Rotate the entire grid S 90 degrees clockwise.

Constraints

• 1 \le N \le 100
• N is an integer.
• Each of S_{i,j} and T_{i,j} is . or #.

Sample Input 1

4
###.
..#.
..#.
..#.
...#
...#
###.
....

Sample Output 1

2

You can match S to T in two operations as shown below.

Sample Input 2

13
.#..###..##..
#.#.#..#.#.#.
#.#.###..#...
###.#..#.#.#.
#.#.###..##..
.............
..#...#....#.
.##..#.#..##.
#.#..#.#.#.#.
####.#.#.####
..#..#.#...#.
..#...#....#.
.............
.............
.#....#...#..
.#...#.#..#..
####.#.#.####
.#.#.###..#.#
.##....#..##.
.#....#...#..
.............
..##..###.#.#
.#.#.#..#.###
.#.#..###.#.#
.#.#.#..#.#.#
..##..###..#.

Sample Output 2

5

Problem Statement

A single-player card game is popular in AtCoder Inc. Each card in the game has a lowercase English letter or the symbol @ written on it. There is plenty number of cards for each kind. The game goes as follows.

1. Arrange the same number of cards in two rows.
2. Replace each card with @ with one of the following cards: a, t, c, o, d, e, r.
3. If the two rows of cards coincide, you win. Otherwise, you lose.

To win this game, you will do the following cheat.

• Freely rearrange the cards within a row whenever you want after step 1.

You are given two strings S and T, representing the two rows you have after step 1. Determine whether it is possible to win with cheating allowed.

Constraints

• S and T consist of lowercase English letters and @.
• The lengths of S and T are equal and between 1 and 2\times 10^5, inclusive.

Sample Input 1

ch@ku@ai
choku@@i

Sample Output 1

Yes

You can replace the @s so that both rows become chokudai.

Sample Input 2

ch@kud@i
akidu@ho

Sample Output 2

Yes

You can cheat and replace the @s so that both rows become chokudai.

Sample Input 3

aoki
@ok@

Sample Output 3

No

You cannot win even with cheating.

Sample Input 4

aa
bb

Sample Output 4

No

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

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

Problem Statement

There is an infinitely large grid. One cell of the grid is named cell (0,0).

The cell located r cells down and c cells right from cell (0,0) is called cell (r,c).
Here, "r cells down" means "|r| cells up" when r is negative, and "c cells right" means "|c| cells left" when c is negative.

Specifically, the cells around cell (0,0) are as follows:

Initially, Takahashi is at cell (R_t,C_t) and Aoki is at cell (R_a,C_a). They will each make N moves according to strings S and T of length N consisting of U, D, L, R.
For each i, Takahashi's and Aoki's i-th moves occur simultaneously: Takahashi moves one cell up if the i-th character of S is U, down if D, left if L, and right if R; Aoki moves similarly according to the i-th character of T.

Find the number of times Takahashi and Aoki are at the same cell immediately after a move during the N moves.

Since N is very large, S and T are given in the form ((S'_1, A_1),\ldots,(S'_M,A_M)) and ((T'_1,B_1),\ldots,(T'_L,B_L)), where S is the string obtained by concatenating "A_1 copies of character S'_1, \dots, A_M copies of character S'_M" in this order, and T is given similarly.

Constraints

• -10^9 \leq R_t,C_t,R_a,C_a \leq 10^9
• 1\leq N \leq 10^{14}
• 1\leq M,L \leq 10^5
• Each of S'_i and T'_i is one of U, D, L, R.
• 1 \leq A_i,B_i \leq 10^9
• A_1+\dots+A_M=B_1+\dots+B_L=N
• All given values are integers.

Sample Input 1

0 0 4 2
3 2 1
R 2
D 1
U 3

Sample Output 1

1

In this case, S= RRD and T= UUU, and the movements proceed as follows:

• Initially, Takahashi is at cell (0,0) and Aoki is at cell (4,2).
• After the 1st move, Takahashi is at cell (0,1) and Aoki is at cell (3,2).
• After the 2nd move, Takahashi is at cell (0,2) and Aoki is at cell (2,2).
• After the 3rd move, Takahashi is at cell (1,2) and Aoki is at cell (1,2).

Thus, the number of times Takahashi and Aoki are at the same cell immediately after a move is 1.

Sample Input 2

1000000000 1000000000 -1000000000 -1000000000
3000000000 3 3
L 1000000000
U 1000000000
U 1000000000
D 1000000000
R 1000000000
U 1000000000

Sample Output 2

1000000001

From the 2000000000-th move to the 3000000000-th move, Takahashi and Aoki are at the same cell immediately after a move for 1000000001 times.

Sample Input 3

3 3 3 2
1 1 1
L 1
R 1

Sample Output 3

0

Sample Input 4

0 0 0 0
1 1 1
L 1
R 1

Sample Output 4

0

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

You are given a string S consisting of digits and positive integers L and R for each of T test cases. Solve the following problem.

For a positive integer x, let us define f(x) as the number of contiguous substrings of the decimal representation of x (without leading zeros) that equal S.

For instance, if S= 22, we have f(122) = 1, f(123) = 0, f(226) = 1, and f(222) = 2.

Find \displaystyle \sum_{k=L}^{R} f(k).

Constraints

• 1 \le T \le 1000
• S is a string consisting of digits whose length is between 1 and 16, inclusive.
• L and R are integers satisfying 1 \le L \le R < 10^{16}.

Sample Input 1

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

Sample Output 1

12
0
14888888888888889
12982260572545
10987664021
1

This input contains six test cases.

• In the first test case, S= 22, L=23, R=234.
  • f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1.
  • f(222)=2.
  • Thus, the answer is 12.
• In the second test case, S= 0295, L=295, R=295.
  • Note that f(295)=0.