Problem Statement

You are given two strings S and T consisting of lowercase English letters. Here, S and T have equal lengths.

Let X be an empty array, and repeat the following operation until S equals T:

• Change one character in S, and append S to the end of X.

Find the array of strings X with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

Constraints

• S and T are strings consisting of lowercase English letters with length between 1 and 100, inclusive.
• The lengths of S and T are equal.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, S = adbe.

We can obtain X = ( acbe , acbc , bcbc ) by performing the following operations:

• Change S to acbe and append acbe to the end of X.

• Change S to acbc and append acbc to the end of X.

• Change S to bcbc and append bcbc to the end of X.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Problem Statement

This problem is an easier version of Problem G.

There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.

Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.

Constraints

• 1 \leq M \leq 100
• M is an integer.
• S_i is a string of length M consisting of digits.

Sample Input 1

10
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.

• Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays 8, the ((0 \bmod 10)+1=1)-st character of S_2.
• Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays 8, the ((2 \bmod 10)+1=3)-rd character of S_3.
• Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays 8, the ((6 \bmod 10)+1=7)-th character of S_1.

There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.

Sample Input 2

20
01234567890123456789
01234567890123456789
01234567890123456789

Sample Output 2

20

Note that he must stop all the reels and make them display the same character.

Sample Input 3

5
11111
22222
33333

Sample Output 3

-1

It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.

Problem Statement

You are given a string S consisting of three different characters: A, B, and C.

As long as S contains the string ABC as a consecutive substring, repeat the following operation:

Remove the leftmost occurrence of the substring ABC from S.

Print the final string S after performing the above procedure.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of the characters A, B, and C.

Sample Input 1

BAABCBCCABCAC

Sample Output 1

BCAC

For the given string S = BAABCBCCABCAC, the operations are performed as follows.

• In the first operation, the ABC from the 3-rd to the 5-th character in S = BAABCBCCABCAC is removed, resulting in S = BABCCABCAC.
• In the second operation, the ABC from the 2-nd to the 4-th character in S = BABCCABCAC is removed, resulting in S = BCABCAC.
• In the third operation, the ABC from the 3-rd to the 5-th character in S = BCABCAC is removed, resulting in S = BCAC.

Therefore, the final S is BCAC.

Sample Input 2

ABCABC

Sample Output 2

In this example, the final S is an empty string.

Sample Input 3

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

Sample Output 3

AAABBBCCC

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Some coins are placed on each cell, and there are A_{i,j} coins on cell (i,j).

Takahashi is initially at cell (1,1) and has x coins. Over the next H+W-1 days, several events will occur. On the k-th day (1\leq k\leq H+W-1), the following things happen in order:

1. Takahashi collects all the coins placed on the cell where he is currently located.
2. Hungry Takahashi consumes P_k coins from his hand to buy food. However, if he has fewer than P_k coins, he cannot buy food and collapses from hunger.
3. If k < H+W-1, Takahashi moves either one cell right or one cell down. He cannot leave the grid. If k=H+W-1, he does nothing.

When there exists a way for Takahashi to finish the next H+W-1 days without ever collapsing from hunger, find the minimum non-negative integer x that can be the number of coins Takahashi initially has.

Constraints

• H,W\geq 1
• H\times W \leq 2\times 10^5
• 1\leq A_{i,j}\leq 10^9
• 1\leq P_k\leq 10^9
• All input values are integers.

Sample Input 1

2 2
3 2
4 1
1 3 6

Sample Output 1

2

When x=2, Takahashi can act as follows to avoid collapsing from hunger:

• Initially, he is at cell (1,1) and has 2 coins.
• Day 1:
  1. He collects 3 coins placed on cell (1,1), so he has 5 coins.
  2. He consumes 1 coin to buy food, so he has 4 coins.
  3. He moves to cell (2,1) which is 1 below.
• Day 2:
  1. He collects 4 coins placed on cell (2,1), so he has 8 coins.
  2. He consumes 3 coins to buy food, so he has 5 coins.
  3. He moves to cell (2,2) which is 1 to the right.
• Day 3:
  1. He collects 1 coin placed on cell (2,2), so he has 6 coins.
  2. He consumes 6 coins to buy food, so he has 0 coins.

When x is 1 or less, Takahashi will collapse from hunger at some point no matter how he acts. Therefore, the answer is 2.

Sample Input 2

1 1
5
3

Sample Output 2

0

Even if Takahashi initially has no coins, he will not collapse from hunger.

Sample Input 3

4 7
35 29 36 88 58 15 25
99 7 49 61 67 4 57
96 92 3 49 49 36 90
72 89 40 44 24 53 45
55 43 23 71 77 6 94 19 27 21

Sample Output 3

20

Problem Statement

You are given an H \times W grid, where each cell contains # or ..
The information about the symbols written in each cell is given as H strings S_1,S_2,\dots,S_H of length W, where the cell in the i-th row from the top and j-th column from the left contains the same symbol as the j-th character of S_i.
Find the number of rectangular regions in this grid that satisfy all of the following conditions:

• The number of cells containing # and the number of cells containing . in the rectangular region are equal.

Formally, find the number of quadruples of integers (u,d,l,r) that satisfy all of the following conditions:

• 1 \le u \le d \le H
• 1 \le l \le r \le W
• When extracting the part of the grid from the u-th through d-th rows from the top and from the l-th through r-th columns from the left, the number of cells containing # and the number of cells containing . in the extracted part are equal.

You are given T test cases. Find the answer for each of them.

Constraints

• 1 \le T \le 25000
• 1 \le H,W
• The sum of H \times W over all test cases in one input does not exceed 3 \times 10^5.
• S_i is a string of length W consisting of # and ..

Sample Input 1

3
3 2
##
#.
..
6 6
..#...
..#..#
#.#.#.
.###..
######
.###..
15 50
.......................#...........###.###.###.###
....................#..#..#..........#.#.#...#.#..
.................#...#####...#.....###.#.#.###.###
..................#..##.##..#......#...#.#.#.....#
...................#########.......###.###.###.###
....................#.....#.......................
.###........##......#.....#..#...#.####.####.##..#
#..#.........#......#.....#..#...#.#....#....##..#
#..#.........#......#.....#..#...#.#....#....##..#
#.....##...###..##..#.....#..#...#.#....#....#.#.#
#....#..#.#..#.#..#.#..##.#..#...#.####.####.#.#.#
#....#..#.#..#.####.#....##..#...#.#....#....#.#.#
#....#..#.#..#.#....#.....#..#...#.#....#....#..##
#..#.#..#.#..#.#..#.#....#.#.#...#.#....#....#..##
.##...##...####.##...####..#..###..####.####.#..##

Sample Output 1

4
79
4032

This input contains 3 test cases.

For the 1st case, the following 4 rectangular regions satisfy the conditions in the problem statement:

• From the 1st to 2nd rows from the top, from the 2nd to 2nd columns from the left
• From the 2nd to 3rd rows from the top, from the 1st to 1st columns from the left
• From the 2nd to 2nd rows from the top, from the 1st to 2nd columns from the left
• From the 1st to 3rd rows from the top, from the 1st to 2nd columns from the left