作者： chenchen

Because Bessie is bored of playing with her usual text string where the only characters are 'C,' 'O,' and 'W,' Farmer John gave her Q new strings (1≤Q≤100), where the only characters are 'M' and 'O.' Bessie's favorite word out of the characters 'M' and 'O' is obviously "MOO," so she wants to turn each of the Q strings into "MOO" using the following operations:

Replace either the first or last character with its opposite (so that 'M' becomes 'O' and 'O' becomes 'M').
Delete either the first or last character.
Unfortunately, Bessie is lazy and does not want to perform more operations than absolutely necessary. For each string, please help her determine the minimum number of operations necessary to form "MOO" or output −1 if this is impossible.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains the value of Q.
The next Q lines of input each consist of a string, each of its characters either 'M' or 'O'. Each string has at least 1 and at most 100 characters.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the answer for each input string on a separate line.

SAMPLE INPUT:

3
MOMMOM
MMO
MOO

SAMPLE OUTPUT:

4
-1
0

A sequence of 4 operations transforming the first string into "MOO" is as follows:

Replace the last character with O (operation 1)
Delete the first character (operation 2)
Delete the first character (operation 2)
Delete the first character (operation 2)
The second string cannot be transformed into "MOO." The third string is already "MOO," so no operations need to be performed.

SCORING:

Inputs 2-4: Every string has length at most 3.
Inputs 5-11: No additional constraints.
Problem credits: Aryansh Shrivastava

With the hottest recorded summer ever at Farmer John's farm, he needs a way to cool down his cows. Thus, he decides to invest in some air conditioners.

Farmer John's N cows (1≤N≤20) live in a barn that contains a sequence of stalls in a row, numbered 1…100. Cow i occupies a range of these stalls, starting from stall s_i and ending with stall t_i. The ranges of stalls occupied by different cows are all disjoint from each-other. Cows have different cooling requirements. Cow i must be cooled by an amount c_i, meaning every stall occupied by cow i must have its temperature reduced by at least c_i units.

The barn contains M air conditioners, labeled 1…M (1≤M≤10). The ith air conditioner costs mi units of money to operate (1≤m_i≤1000) and cools the range of stalls starting from stall ai and ending with stall b_i. If running, the ith air conditioner reduces the temperature of all the stalls in this range by pi (1≤p_i≤106). Ranges of stalls covered by air conditioners may potentially overlap.

Running a farm is no easy business, so FJ has a tight budget. Please determine the minimum amount of money he needs to spend to keep all of his cows comfortable. It is guaranteed that if FJ uses all of his conditioners, then all cows will be comfortable.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N and M.

The next N lines describe cows. The ith of these lines contains s_i, t_i, and c_i.

The next M lines describe air conditioners. The ith of these lines contains a_i, b_i, p_i, and m_i.

For every input other than the sample, you can assume that M=10.

OUTPUT FORMAT (print output to the terminal / stdout):

Output a single integer telling the minimum amount of money FJ needs to spend to operate enough air conditioners to satisfy all his cows (with the conditions listed above).

SAMPLE INPUT:

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

SAMPLE OUTPUT:

10
One possible solution that results in the least amount of money spent is to select those that cool the intervals [2,9], [1,2], and [6,9], for a cost of 3+2+5=10.

Problem credits: Aryansh Shrivastava and Eric Hsu

Farmer John has N cows (2≤N≤105). Each cow has a breed that is either Guernsey or Holstein. As is often the case, the cows are standing in a line, numbered 1…N in this order.

Over the course of the day, each cow writes down a list of cows. Specifically, cow i's list contains the range of cows starting with herself (cow i) up to and including cow E_i (i≤E_i≤N).

FJ has recently discovered that each breed of cow has exactly one distinct leader. FJ does not know who the leaders are, but he knows that each leader must have a list that includes all the cows of their breed, or the other breed's leader (or both).

Help FJ count the number of pairs of cows that could be leaders. It is guaranteed that there is at least one possible pair.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The second line contains a string of length N, with the ith character denoting the breed of the ith cow (G meaning Guernsey and H meaning Holstein). It is guaranteed that there is at least one Guernsey and one Holstein.

The third line contains E₁…E_N.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the number of possible pairs of leaders.

SAMPLE INPUT:

4
GHHG
2 4 3 4

SAMPLE OUTPUT:

1
The only valid leader pair is (1,2). Cow 1's list contains the other breed's leader (cow 2). Cow 2's list contains all cows of her breed (Holstein).

No other pairs are valid. For example, (2,4) is invalid since cow 4's list does not contain the other breed's leader, and it also does not contain all cows of her breed.

SAMPLE INPUT:

3
GGH
2 3 3

SAMPLE OUTPUT:

2
There are two valid leader pairs, (1,3) and (2,3).

SCORING

Inputs 3-5: N≤100
Inputs 6-10: N≤3000
Inputs 11-17: No additional constraints.
Problem credits: Mythreya Dharani

Farmer Nhoj dropped Bessie in the middle of nowhere! At time t=0, Bessie is located at x=0 on an infinite number line. She frantically searches for an exit by moving left or right by 1 unit each second. However, there actually is no exit and after T seconds, Bessie is back at x=0, tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=.5,1.5,2.5,…,(N−1).5, given by an array A₀,A₁,…,A_N−1(1≤N≤10⁵, 1≤ A_i≤10⁶, ∑A_i≤10⁶). Bessie never reaches x>N nor x<0.

In particular, Bessie's route can be represented by a string of T=∑^N−1_i=0A_i Ls and Rs where the ith character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of LRs plus the number of occurrences of RLs.

Please help Farmer Nhoj find any route Bessie could have taken that is consistent with A and minimizes the number of direction changes. It is guaranteed that there is at least one valid route.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N. The second line contains A₀,A₁,…,A_N−1.

OUTPUT FORMAT (print output to the terminal / stdout):

Output a string S of length T=∑^N−1_i=0A_i where S_i is L or R, indicating the direction Bessie travels in during second i. If there are multiple routes minimizing the number of direction changes, output any.

SAMPLE INPUT:

2
2 4

SAMPLE OUTPUT:

RRLRLL
There is only 1 valid route, corresponding to the route 0→1→2→1→2→1→0. Since this is the only possible route, it also has the minimum number of direction changes.

SAMPLE INPUT:

3
2 4 4

SAMPLE OUTPUT:

RRRLLRRLLL

There are 3 possible routes:

RRLRRLRLLL
RRRLRLLRLL
RRRLLRRLLL
The first two routes have 5 direction changes, while the last one has only 3. Thus the last route is the only correct output.

SCORING:

Inputs 3-5: N≤2
Inputs 3-10: T=A₀+A₁+⋯+A_N−1≤5000
Inputs 11-20: No additional constraints.

Problem credits: Brandon Wang and Claire Zhang

**Note: The time limit for this problem is 8s, four times the default.**

Farmer John has a big square field split up into an (N+1)×(N+1) (1≤N≤1500) grid of cells. Let cell (i,j) denote the cell in the ith row from the top and jth column from the left. There is one cow living in every cell (i,j) such that 1≤i,j≤N, and each such cell also contains a signpost pointing either to the right or downward. Also, every cell (i,j) such that either i=N+1 or j=N+1, except for (N+1,N+1), contains a vat of cow feed. Each vat contains cow feed of varying price; the vat at (i,j) costs c_i,j(1≤c_i,j≤500) to feed each cow.

Every day at dinner time, Farmer John rings the dinner bell, and each cow keeps following the directions of the signposts until it reaches a vat, and is then fed from that vat. Then the cows all return to their original positions for the next day.

To maintain his budget, Farmer John wants to know the total cost to feed all the cows each day. However, during every day, before dinner, the cow in in some cell (i,j) flips the direction of its signpost (from right to down or vice versa). The signpost remains in this direction for the following days as well, unless it is flipped back later.

Given the coordinates of the signpost that is flipped on each day, output the cost for every day (with Q days in total, 1≤Q≤1500).

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N (1≤N≤1500).
The next N+1 lines contain the rows of the grid from top to bottom, containing the initial directions of the signposts and the costs c_i,j of each vat. The first N of these lines contain a string of N directions R or D (representing signposts pointing right or down, respectively), followed by the cost ci,N+1. The (N+1)-th line contains N costs cN+_1,j.

The next line contains Q (1≤Q≤1500).

Then follow Q additional lines, each consisting of two integers i and j (1≤i,j≤N), which are the coordinates of the cell whose signpost is flipped on the corresponding day.

OUTPUT FORMAT (print output to the terminal / stdout):

Q+1 lines: the original value of the total cost, followed by the value of the total cost after each flip.

SAMPLE INPUT:

2
RR 1
DD 10
100 500
4
1 1
1 1
1 1
2 1

SAMPLE OUTPUT:

602
701
602
701
1501

Before the first flip, the cows at (1,1) and (1,2) cost 1 to feed, the cow at (2,1) costs 100 to feed, and the cow at (2,2) costs 500 to feed, for a total cost of 602. After the first flip, the direction of the signpost at (1,1) changes from R to D, and the cow at (1,1) now costs 100 to feed (while the others remain unchanged), so the total cost is now 701. The second and third flips switch the same sign back and forth. After the fourth flip, the cows at (1,1) and (2,1) now cost 500 to feed, for a total cost of 1501.

SCORING:

Inputs 2-4: 1≤N,Q≤50
Inputs 5-7: 1≤N,Q≤250
Inputs 2-10: The initial direction in each cell, as well as the queries, are uniformly randomly generated.
Inputs 11-15: No additional constraints.
Problem credits: Benjamin Qi

Bessie is using the latest and greatest innovation in text-editing software, miV! She starts with an input string consisting solely of upper and lowercase English letters and wishes to transform it into some output string. With just one keystroke, miV allows her to replace all occurrences of one English letter c1 in the string with another English letter c2. For example, given the string aAbBa, if Bessie selects c1 as 'a' and c2 as 'B', the given string transforms into BAbBB.

Bessie is a busy cow, so for each of T (1≤T≤10) independent test cases, output the minimum number of keystrokes required to transform her input string into her desired output string.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the number of independent test cases.
The following T pairs of lines contain an input and output string of equal length. All characters are upper or lowercase English letters (either A through Z or a through z). The sum of the lengths of all strings does not exceed 105.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the minimum number of keystrokes required to change the input string into the output string, or −1 if it is impossible to do so.

SAMPLE INPUT:

4
abc
abc
BBC
ABC
abc
bbc
ABCD
BACD

SAMPLE OUTPUT:

0
-1
1
3

The first input string is the same as its output string, so no keystrokes are required.

The second input string cannot be changed into its output string because Bessie cannot change one 'B' to 'A' while keeping the other as 'B'.

The third input string can be changed into its output string by changing 'a' to 'b'.

The last input string can be changed into its output string like so: ABCD→EBCD→EACD→BACD.

SCORING:

Inputs 2-6: Every string has a length at most 50.
Inputs 7-9: All strings consist only of lowercase letters 'a' through 'e'
Inputs 10-15: No additional constraints.
Problem credits: Benjamin Qi