作者： chenchen

Farmer John has N (1≤N≤105) cows, the breed of each being either a Guernsey or a Holstein. They have lined up horizontally with the cows occupying positions labeled from 1…N.

Since all the cows are hungry, FJ decides to plant grassy patches on some of the positions 1…N. Guernseys and Holsteins prefer different types of grass, so if Farmer John decides to plant grass at some location, he must choose to planting either Guernsey-preferred grass or Holstein-preferred grass --- he cannot plant both at the same location. Each patch of grass planted can feed an unlimited number of cows of the appropriate breed.

Each cow is willing to move a maximum of K (0≤K≤N−1) positions to reach a patch. Find the minimum number of patches needed to feed all the cows. Also, print a configuration of patches that uses the minimum amount of patches needed to feed the cows. Any configuration that satisfies the above conditions will be considered correct.

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

Each input contains T test cases, each describing an arrangement of cows. The first line of input contains T (1≤T≤10). Each of the T test cases follow.
Each test case starts with a line containing N and K. The next line will contain a string of length N, where each character denotes the breed of the ith cow (G meaning Guernsey and H meaning Holstein).

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

For each of the T test cases, please write two lines of output. For the first line, print the minimum number of patches needed to feed the cows. For the second line, print a string of length N that describes a configuration that feeds all the cows with the minimum number of patches. The ith character, describing the ith position, should be a '.' if there is no patch, a 'G' if there is a patch that feeds Guernseys, and a 'H' if it feeds Holsteins. Any valid configuration will be accepted.

SAMPLE INPUT:

6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

SAMPLE OUTPUT:

5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HG

Note that for some test cases, there are multiple acceptable configurations that manage to feed all cows while using the minimum number of patches. For example, in the fourth test case, another acceptable answer would be:

.GH..

This corresponds to placing a patch feeding Guernseys on the 2nd position and a patch feeding Holsteins on the third position. This uses the optimal number of patches and ensures that all cows are within 3 positions of a patch they prefer.

SCORING:

Inputs 2 through 4 have N≤10.
Inputs 5 through 8 have N≤40.
Inputs 9 through 12 have N≤105.

Problem credits: Mythreya Dharani

Farmer John is planning to open a new university for cows!

There are N (1≤N≤105) cows who could potentially attend this university. Each cow is willing to pay a maximum tuition of ci (1≤ci≤106). Farmer John can set the tuition that all cows must pay to enroll. If this tuition is greater than the maximum a cow is willing to pay, then the cow will not attend the university. Farmer John wants to make the most possible money so he can pay his instructors a fair wage. Please determine how much money he can make, and how much tuition he should charge.

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

The first line contains N. The second line contains N integers c1,c2,…,cN, where ci is the maximum tuition cow i is willing to pay.

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

Please output the maximum amount of money Farmer John can make and the optimal tuition he should charge. If there are multiple solutions, output the solution with the smallest optimal tuition.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long" in Java, a "long long" in C/C++).

SAMPLE INPUT:

4
1 6 4 6

SAMPLE OUTPUT:

12 4
If Farmer John charges 4, then 3 cows will attend, allowing him to make 3⋅4=12.

SCORING:

Test cases 2 through 4 have ci≤1,000.
Test cases 5 through 8 have N≤5,000.
Test cases 9 through 12 have no additional constraints.
Problem credits: Freddie Tang

Bessie has an array a1,…,aN, where 1≤N≤300 and 0≤ai≤109 for all i. She won't tell you a itself, but she will tell you the range of each subarray of a. That is, for each pair of indices i≤j, Bessie tells you ri,j=maxa[i…j]−mina[i…j]. Given these values of r, please construct an array that could have been Bessie's original array. The values in your array should be in the range [−109,109].

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

The first line contains N.
Another N lines follow. The ith of these lines contains the integers ri,i,ri,i+1,…,ri,N.

It is guaranteed that there is some array a with values in the range [0,109] such that for all i≤j, ri,j=maxa[i…j]−mina[i…j].

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

Output one line containing N integers b1,b2,…,bN in the range [−109,109] representing your array. They must satisfy ri,j=maxb[i…j]−minb[i…j] for all i≤j.

SAMPLE INPUT:

3
0 2 2
0 1
0

SAMPLE OUTPUT:

1 3 2
For example, r1,3=maxa[1…3]−mina[1…3]=3−1=2.

SAMPLE INPUT:

3
0 1 1
0 0
0

SAMPLE OUTPUT:

0 1 1
This example satisfies the constraints for subtask 1.

SAMPLE INPUT:

4
0 1 2 2
0 1 1
0 1
0

SAMPLE OUTPUT:

1 2 3 2
This example satisfies the constraints for subtask 2.

SAMPLE INPUT:

4
0 1 1 2
0 0 2
0 2
0

SAMPLE OUTPUT:

1 2 2 0

SCORING:

Test 5 satisfies r1,N≤1.
Tests 6-8 satisfy ri,i+1=1 for all 1≤i<N.
Tests 9-14 satisfy no additional constraints.
Problem credits: Danny Mittal

Farmer John and his archnemesis Farmer Nhoj are playing a game in a circular barn. There are N (1≤N≤105) rooms in the barn, and the ith room initially contains ai cows (1≤ai≤5⋅106). The game is played as follows:
Both farmers will always be in the same room. After entering a room, each farmer takes exactly one turn, with Farmer John going first. Both farmers initially enter room 1.
If there are zero cows in the current room, then the farmer to go loses. Otherwise, the farmer to go chooses an integer P, where P must either be 1 or a prime number at most the number of cows in the current room, and removes P cows from the current room.
After both farmers have taken turns, both farmers move to the next room in the circular barn. That is, if the farmers are in room i, then they move to room i+1, unless they are in room N, in which case they move to room 1.
Determine the farmer that wins the game if both farmers play optimally.

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

The input contains T test cases. The first line contains T (1≤T≤1000). Each of the T test cases follow.
Each test case starts with a line containing N, followed by a line containing a1,…,aN.

It is guaranteed that the sum of all N is at most 2⋅105.

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

For each test case, output the farmer that wins the game, either "Farmer John" or "Farmer Nhoj."

SAMPLE INPUT:

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

SAMPLE OUTPUT:

Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj

For the first test case, Farmer John can remove 1, 2, or 3 cows from the first room. Whichever number he removes, Nhoj can remove the remaining cow(s), forcing FJ to lose when they circle back to the first room.

For the second test case, FJ can remove 5 cows, forcing Nhoj to work with only 4 cows remaining. Now, Nhoj can either remove 1, 2, or 3 cows. This is now similar to the first test case.

For the third and fourth test cases, FJ can immediately remove all the cows from the first room, forcing Nhoj to lose.

For the fifth test case, FJ can remove 1, 2, or 3, cows from the first room, and Nhoj can remove the rest right after. When they circle back around to the first room, FJ will lose.

SCORING:

Inputs 2-4 satisfy N=1.
Inputs 1, 2, and 5-7 satisfy ai≤1000.
Inputs 8-20 satisfy no additional constraints.
Problem credits: Chongtian Ma, Jesse Choe, and Yuval Vaknin

Note: the time limit for this problem is 4s, two times the default. The memory limit is also twice the default.
Farmer John's farm has N barns (2≤N≤2⋅105) numbered 1…N. There are N−1 roads, where each road connects two barns and it is possible to get from any barn to any other barn via some sequence of roads. Currently, the jth barn has hj hay bales (1≤hj≤109).

To please his cows, Farmer John would like to move the hay such that each barn has an equal number of bales. He can select any pair of barns connected by a road and order his farmhands to move any positive integer number of bales less than or equal to the number of bales currently at the first barn from the first barn to the second.

Please determine a sequence of orders Farmer John can issue to complete the task in the minimum possible number of orders. It is guaranteed that a sequence of orders exists.

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

The first line of input contains the value of N.

The second line of input contains the space-separated values of hj for j=1…N.

The final N−1 lines of input each contain two space-separated barn numbers ui vi, indicating that there is a bidirectional road connecting ui and vi.

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

Output the minimum possible number of orders, followed a sequence of orders of that length, one per line.
Each order should be formatted as three space-separated positive integers: the source barn, the destination barn, and the third describes the number of hay bales to move from the source to the destination.

If there are multiple solutions, output any.

SAMPLE INPUT:

4
2 1 4 5
1 2
2 3
2 4

SAMPLE OUTPUT:

3
3 2 1
4 2 2
2 1 1

In this example, there are a total of twelve hay bales and four barns, meaning each barn must have three hay bales at the end. The sequence of orders in the sample output can be verbally translated as below:

From barn 3 to barn 2, move 1 bale.
From barn 4 to barn 2, move 2 bales.
From barn 2 to barn 1, move 1 bale.

SCORING:

Test cases 2-8 satisfy N≤5000
Test cases 7-10 satisfy vi=ui+1
Test cases 11-16 satisfy no additional constraints
Problem credits: Aryansh Shrivastava

Farmer John has N cows (2≤N≤105), conveniently labeled 1…N. There are M (1≤M≤2⋅105) pairs of friends among these cows.
A group of cows is called a "friendship group" if every cow in the group is reachable from every other cow in the group via a chain of friendships that lies solely within the group (friendships connecting to cows outside the group have no impact). The "strength" of a friendship group is the minimum number of friends of any cow in the group within the group times the number of cows in the group (again, note that friendships connecting to cows outside the group do not count for this definition).

Please find the maximum strength over all friendship groups.

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

The first line contains N and M.
The next M lines contain two integers ui and vi denoting that cows ui and vi are friends (1≤ui,vi≤N, ui≠vi). No unordered pair of cows appears more than once.

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

One line containing the maximum strength over all friendship groups.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

12
The maximum strength can be observed to be with the group of cows numbered 1,2,3,4. The minimum number of friends of any cow in this group within the group is 3, so the answer is 4⋅3=12.

SCORING:

For 1≤T≤3, test case T satisfies N≤16.
For 4≤T≤9, test case T satisfies N≤1000.
For 10≤T≤20, test case T satisfies no additional constraints.
Problem credits: Benjamin Qi

There are NN (1≤N≤20001≤N≤2000) evenly spaced mountains in a row on the edge of Farmer John's farm. These can be expressed as an array of heights h1,h2,…,hNh1,h2,…,hN. For a mountain ii, you can see another mountain jj if there are no mountains strictly higher than the line of sight connecting the tops of mountain jj and ii. Formally, for two mountains i<ji<j, they can see each other if there is no kk such that i<k<ji<k<j and (k,hk)(k,hk) is above the line segment connecting (i,hi)(i,hi) and (j,hj)(j,hj). There are QQ (1≤Q≤20001≤Q≤2000) updates where the height of one mountain increases. Find the total number of unordered pairs of mountains that see each other after each update.

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

Line 11 contains NN.Line 22 contains NN heights h1,h2,…,hNh1,h2,…,hN (for each ii, 0≤hi≤1090≤hi≤109).

Line 33 contains QQ.

Lines 44 to 3+Q3+Q contain xx, yy (1≤x≤N1≤x≤N, 1≤y1≤y) where xx is the index of the mountain and yy is the amount the height increases by. It is guaranteed that the new height of the mountain is at most 109109.

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

QQ lines, with the total number of unordered pairs of mountains that see each other after each update.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

7
10
7

Initially, the following pairs of mountains can see each other: (1,2)(1,2), (2,3)(2,3), (2,5)(2,5), (3,4)(3,4), (3,5)(3,5), (4,5)(4,5), a total of 66.

After the first update, mountain 44 has a height of 44, which doesn't block any visibility but does make it so that 44 can now see 22, making the new answer 77.

After the second update, mountain 11 has a height of 55, which doesn't block any visibility but does make it so that 11 can now see 33, 44, and 55, making the new answer 1010.

After the third update, mountain 33 has a height of 55, which blocks mountain 11 from seeing mountain 44, blocks mountain 22 from seeing mountains 44 and 55, and doesn't allow itself to see any more mountains since it can already see all of them, making the new answer 77.

SCORING:

Tests 2-5 satisfy N,Q≤100N,Q≤100.

Tests 6-11 satisfy Q≤10Q≤10.

Tests 12-21 have no additional constraints.

Problem credits: Joe Li and Larry Xing

Bessie wants to watch Bovine Genomics: The Documentary, but she doesn’t want to go alone. Unfortunately, her friends aren’t enthusiastic enough to go with her! Therefore, Bessie needs to bribe her friends to accompany her to the movie theater. She has two tools in her bribery arsenal: mooney and ice cream cones.

Bessie has NN (1≤N≤20001≤N≤2000) friends. However, not all friends are created equal! Friend ii has a popularity score of PiPi (1≤Pi≤20001≤Pi≤2000), and Bessie wants to maximize the sum of the popularity scores of the friends accompanying her. Friend ii is only willing to accompany Bessie if she gives them CiCi (1≤Ci≤20001≤Ci≤2000) moonies. They will also offer her a discount of 11 mooney if she gives them XiXi (1≤Xi≤20001≤Xi≤2000) ice cream cones. Bessie can get as many whole-number discounts as she wants from a friend, as long as the discounts don’t cause the friend to give her mooney.

Bessie has AA moonies and BB ice cream cones at her disposal (0≤A,B≤20000≤A,B≤2000). Help her determine the maximum sum of the popularity scores she can achieve if she spends her mooney and ice cream cones optimally!

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

Line 11 contains three numbers NN, AA, and BB, representing the number of friends, the amount of mooney, and the number of ice cream cones Bessie has respectively.

Each of the next NN lines contains three numbers, PiPi, CiCi, and XiXi, representing popularity (PiPi), mooney needed to bribe friend ii to accompany Bessie (CiCi), and ice cream cones needed to receive a discount of 11 mooney from friend ii (XiXi).

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

Output the maximum sum of the popularity scores of the friends accompanying Bessie, assuming she spends her moonie and ice cream cones optimally.

SAMPLE INPUT:

3 10 8
5 5 4
6 7 3
10 6 3

SAMPLE OUTPUT:

15

Bessie can give 44 moonies and 44 ice cream cones to cow 11, and 66 moonies and 33 ice cream cones to cow 33, in order to get cows 11 and 33 to accompany her for a total popularity of 5+10=155+10=15.

SCORING:

Test cases 2-4 satisfy N≤5N≤5 and Ci=1Ci=1

Test cases 5-7 satisfy B=0B=0

Test cases 8-10 satisfy N,A,B,Pi,Ci,Xi≤50N,A,B,Pi,Ci,Xi≤50

Test cases 11-15 satisfy N,A,B,Pi,Ci,Xi≤200N,A,B,Pi,Ci,Xi≤200

Test cases 16-20 satisfy no further constraints

Problem credits: Timothy Feng, Nathan Wang, and Sam Zhang

The United Cows of Farmer John (UCFJ) are at the annual hoofball championships! UCFJ's team of NN(1≤N≤7500)(1≤N≤7500) cows won a gold medal in hoofball, narrowly beating out Farmer Nhoj's team.

The cows have already lined up for the awards ceremony. They want FJ to take N(N+1)2N(N+1)2 group photos, one for each contiguous subsequence of the lineup.

However, FJ, as the coach of the team, is very particular about how the cows should be lined up. Specifically, he refuses to take a picture of a subsequence unless it forms a *palindrome,* meaning that the breed of the iith cow from the left end of the subsequence must be the same as the breed of the iith cow from the right end of the subsequence for all positive integers iiless than or equal to the length of the subsequence. Each cow's breed is either Guernsey or Holstein.

For each of the N(N+1)2N(N+1)2 contiguous subsequences of the lineup, count the minimum number of transpositions necessary to rearrange that subsequence into a palindrome (or −1−1if it is impossible to do so). A single transposition consists of taking two adjacent cows in the subsequence and swapping them. Output the sum of all these counts.

Note that the number of transpositions needed is calculated independently for each contiguous subsequence (the cows return to their initial positions between photos).

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

The lineup, represented by a string of Gs and Hs of length NN.

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

The sum of the aforementioned quantity over all N(N+1)2N(N+1)2contiguous subsequences of the lineup.

SAMPLE INPUT:

GHHGGHHGH

SAMPLE OUTPUT:

The first four contiguous subsequences are G, GH, GHH, and GHHG. Both G and GHHG are already palindromes, so they contribute 00 to the sum. GHH can be rearranged into a palindrome using a single transposition, so it contributes 11 to the sum. GH cannot be rearranged into a palindrome using any number of transpositions, so it contributes −1−1 to the sum.

Another contiguous subsequence that contributes to the sum is HHGG. This can be rearranged into a palindrome using two transpositions.

SCORING:

There are fifteen test cases aside from the sample, one for each of N∈[100,200,500,1000,2000,5000,5000,5000,5000,5000,7500,7500,7500,7500,7500]N∈[100,200,500,1000,2000,5000,5000,5000,5000,5000,7500,7500,7500,7500,7500].

Problem credits: Mythreya Dharani and Benjamin Qi

Note: the time limit for this problem is 3s, 50% larger than the default. The memory limit is twice the default.

There are initially MM (1≤M≤2⋅1051≤M≤2⋅105) pairs of friends among FJ's NN (2≤N≤2⋅1052≤N≤2⋅105) cows labeled 1…N1…N. The cows are leaving the farm for vacation one by one. On day ii, the ii-th cow leaves the farm, and all pairs of the ii-th cow's friends still present on the farm become friends. How many new friendships are formed in total?

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

The first line contains NN and MM.The next MM lines contain two integers uiui and vivi denoting that cows uiui and vivi are friends (1≤ui,vi≤N1≤ui,vi≤N, ui≠viui≠vi). No unordered pair of cows appears more than once.

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

One line containing the total number of new friendships formed. Do not include pairs of cows that were already friends at the beginning.

SAMPLE INPUT:

7 6
1 3
1 4
7 1
2 3
2 4
3 5

SAMPLE OUTPUT:

5

On day 11, three new friendships are formed: (3,4)(3,4), (3,7)(3,7), and (4,7)(4,7).

On day 33, two new friendships are formed: (4,5)(4,5) and (5,7)(5,7).

SCORING:

Test cases 2-3 satisfy N≤500N≤500.

Test cases 4-7 satisfy N≤104N≤104.

Test cases 8-17 satisfy no additional constraints.
Problem credits: Benjamin Qi