作者： chenchen

Bessie has opened a bakery!

In her bakery, Bessie has an oven that can produce a cookie in tC units of time or a muffin in tM units of time (1≤tC,tM≤109). Due to space constraints, Bessie can only produce one pastry at a time, so to produce A cookies and B muffins, it takes A⋅tC+B⋅tM units of time.

Bessie's N (1≤N≤100) friends would each like to visit the bakery one by one. The ith friend will order ai (1≤ai≤109) cookies and bi (1≤bi≤109) muffins immediately upon entering. Bessie doesn't have space to store pastries, so she only starts making pastries upon receiving an order. Furthermore, Bessie's friends are very busy, so the ith friend is only willing to wait ci (ai+bi≤ci≤2⋅1018) units of time before getting sad and leaving.

Bessie really does not want her friends to be sad. With one mooney, she can upgrade her oven so that it takes one less unit of time to produce a cookie or one less unit of time to produce a muffin. She can't upgrade her oven a fractional amount of times, but she can choose to upgrade her oven as many times as she needs before her friends arrive, as long as the time needed to produce a cookie and to produce a muffin both remain strictly positive.

For each of T (1≤T≤100) test cases, please help Bessie find out the minimum amount of moonies that Bessie must spend so that her bakery can satisfy all of her friends.

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

The first line contains T, the number of test cases.
Each test case starts with one line containing N, tC, tM. Then, the next N lines each contain three integers ai,bi,ci.

Consecutive test cases are separated by newlines.

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

The minimum amount of moonies that Bessie needs to spend for each test case, on separate lines.

SAMPLE INPUT:

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

SAMPLE OUTPUT:

11
6
In the first test case, Bessie can pay 11 moonies to decrease the time required to produce a cookie by 4 and a muffin by 7, so that her oven produces cookies in 3 units of time and muffins in 2 units of time. Then she can satisfy the first friend in 18 units of time, the second friend in 14 units of time, and the third friend in 5 units of time, so none of them will get sad and leave.

In the second test case, Bessie should decrease the time required to produce a cookie by 6 and a muffin by 0.

SCORING:

Inputs 2-4: N≤10,tC,tM≤1000
Inputs 5-11: No additional constraints.
Problem credits: Benjamin Qi

Farmer John wrote down N (1≤N≤300) digits on pieces of paper. For each i∈[1,N], the ith piece of paper contains digit ai (1≤ai≤9).

The cows have two favorite integers A and B (1≤A≤B<1018), and would like you to answer Q (1≤Q≤5⋅104) queries. For the ith query, the cows will move left to right across papers li…ri (1≤li≤ri≤N), maintaining an initially empty pile of papers. For each paper, they will either add it to the top of the pile, to the bottom of the pile, or neither. In the end, they will read the papers in the pile from top to bottom, forming an integer. Over all 3ri−li+1 ways for the cows to make choices during this process, count the number of ways that result in the cows reading an integer in [A,B] inclusive, and output this number modulo 109+7.

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

The first line contains three space-separated integers N, A, and B.

The second line contains N space-separated digits a1,a2,…,aN.

The third line contains an integer Q, the number of queries.

The next Q lines each contain two space-separated integers li and ri.

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

For each query, a single line containing the answer.

SAMPLE INPUT:

5 13 327
1 2 3 4 5
3
1 2
1 3
2 5

SAMPLE OUTPUT:

2
18
34
For the first query, there are nine ways Bessie can stack papers when reading the interval [1,2]:

Bessie can ignore 1 then ignore 2, getting 0.
Bessie can ignore 1 then add 2 to the top of the stack, getting 2.
Bessie can ignore 1 then add 2 to the bottom of the stack, getting 2.
Bessie can add 1 to the top of the stack then ignore 2, getting 1.
Bessie can add 1 to the top of the stack then add 2 to the top of the stack, getting 21.
Bessie can add 1 to the top of the stack then add 2 to the bottom of the stack, getting 12.
Bessie can add 1 to the bottom of the stack then ignore 2, getting 1.
Bessie can add 1 to the bottom of the stack then add 2 to the top of the stack, getting 21.
Bessie can add 1 to the bottom of the stack then add 2 to the bottom of the stack, getting 12.
Only the 2 ways that give 21 yield a number between 13 and 327, so the answer is 2.

SCORING:

Inputs 2-3: B<100
Inputs 4-5: A=B
Inputs 6-13: No additional constraints.
Problem credits: Jesse Choe

There are N pastures (2≤N≤2⋅105), connected by N−1 roads, such that they form a tree. Every road takes 1 second to cross. Each pasture starts out with 0 grass, and the ith pasture's grass grows at a rate of ai (1≤ai≤108) units per second. Farmer John is in pasture 1 at the start, and needs to drive around and fertilize the grass in every pasture. If he visits a pasture with x units of grass, it will need x amount of fertilizer. A pasture only needs to be fertilized the first time it is visited, and fertilizing a pasture takes 0 time.

The input contains an additional parameter T∈{0,1}.

If T=0, Farmer John must end at pasture 1.
If T=1, Farmer John may end at any pasture.
Compute the minimum amount of time it will take to fertilize every pasture and the minimum amount of fertilizer needed to finish in that amount of time.

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

The first line contains N and T.
Then for each i from 2 to N, there is a line containing pi and ai, meaning that there is a road connecting pastures pi and i. It is guaranteed that 1≤pi<i.

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

The minimum amount of time and the minimum amount of fertilizer, separated by spaces.

SAMPLE INPUT:

5 0
1 1
1 2
3 1
3 4

SAMPLE OUTPUT:

8 21
The optimal route for Farmer John is as follows:

At time 1, move to node 3, which now has 1⋅2=2 grass and so needs 2 fertilizer.
At time 2, move to node 5, which now has 2⋅4=8 grass and so needs 8 fertilizer.
At time 3, move back to node 3, which we already fertilized and so don't need to fertilize again.
At time 4, move to node 4, which now has 4⋅1=4 grass and so needs 4 fertilizer.
At time 5, move back to node 3, which we already fertilized.
At time 6, move back to node 1.
At time 7, move to node 2, which now has 7⋅1=7 grass and so needs 7 fertilizer.
At time 8, return to node 1.
This route takes 8 time and uses 2+8+4+7=21 fertilizer. It can be shown that 8 is the least possible amount of time for any route that returns to node 1 at the end and 21 is the least possible fertilizer used for any route that returns to node 1 and takes 8 time.

SAMPLE INPUT:

5 1
1 1
1 2
3 1
3 4

SAMPLE OUTPUT:

6 29
The optimal route for Farmer John is as follows:

At time 1, move to node 2, which now has 1⋅1=1 grass and so needs 1 fertilizer.
At time 2, move back to node 1.
At time 3, move to node 3, which now has 3⋅2=6 grass and so needs 6 fertilizer.
At time 4, move to node 5, which now has 4⋅4=16 grass and so needs 16 fertilizer.
At time 5, move back to node 3, which we already fertilized and so don't need to fertilize again.
At time 6, move to node 4, which now has 6⋅1=6 grass and so needs 6 fertilizer.
This route takes 6 time and uses 1+6+16+6=29 fertilizer. It can be shown that 6 is the least possible amount of time for any route and 29 is the least possible fertilizer used for any route that takes 6 time.

SCORING:

Inputs 3-10: T=0
Inputs 11-22: T=1
Inputs 3-6 and 11-14: No pasture is adjacent to more than three roads.
Problem credits: Rohin Garg

Note: The time limit for this problem is 3s, 1.5x the default.

FJ gave Bessie an array a of length N (2≤N≤500,−1015≤ai≤1015) with all N(N+1)2 contiguous subarray sums distinct. For each index i∈[1,N], help Bessie compute the minimum amount it suffices to change ai by so that there are two different contiguous subarrays of a with equal sum.

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

The first line contains N.
The next line contains a1,…,aN (the elements of a, in order).

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

One line for each index i∈[1,N].

SAMPLE INPUT:

2
2 -3

SAMPLE OUTPUT:

2
3
Decreasing a1 by 2 would result in a1+a2=a2. Similarly, increasing a2 by 3 would result in a1+a2=a1.

SAMPLE INPUT:

3
3 -10 4

SAMPLE OUTPUT:

1
6
1
Increasing a1 or decreasing a3 by 1 would result in a1=a3. Increasing a2 by 6 would result in a1=a1+a2+a3.

SCORING:

Input 3: N≤40
Input 4: N≤80
Inputs 5-7: N≤200
Inputs 8-16: No additional constraints.
Problem credits: Benjamin Qi

Note: The time limit for this problem is 3s, 1.5x the default.

Bessie likes to watch shows on Cowflix, and she watches them in different places. Farmer John's farm can be represented as a tree with N (2≤N≤2⋅105) nodes, and for each node, either Bessie watches Cowflix there or she doesn't. It is guaranteed that Bessie watches Cowflix in at least one node.

Unfortunately, Cowflix is introducing a new subscription model to combat password sharing. In their new model, you can choose a connected component of size d in the farm, and then you need to pay d+k moonies for an account that you can use in that connected component. Formally, you need to choose a set of disjoint connected components c1,c2,…,cC so that every node where Bessie watches Cowflix must be contained within some ci. The cost of the set of components is ∑Ci=1(|ci|+k), where |ci| is the number of nodes in component ci. Nodes where Bessie does not watch Cowflix do not have to be in any ci.

Bessie is worried that the new subscription model may be too expensive for her given all the places she visits and is thinking of switching to Mooloo. To aid her decision-making, calculate the minimum amount she would need to pay to Cowflix to maintain her viewing habits. Because Cowflix has not announced the value of k, calculate it for all integer values of k from 1 to N.

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

The first line contains N.
The second line contains a bit string s1s2s3…sN where si=1 if Bessie watches Cowflix at node i.

Then N−1 lines follow, each containing two integers a and b (1≤a,b≤N), which denotes an edge between a and b in the tree.

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

The answers for each k from 1 to N on separate lines.

SAMPLE INPUT:

5
10001
1 2
2 3
3 4
4 5

SAMPLE OUTPUT:

4
6
8
9
10
For k≤3, it's optimal to have two accounts: c1={1},c2={5}. For k≥3, it's optimal to have one account: c1={1,2,3,4,5}.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
6
8
9
10
11
12

SCORING:

Inputs 3-5: N≤5000
Inputs 6-8: i is connected to i+1 for all i∈[1,N).
Inputs 9-19: N≤105
Inputs 20-24: No additional constraints.
Problem credits: Danny Mittal

Note: The memory limit for this problem is 512MB, twice the default.

Farmer John created N (1≤N≤105) problems. He then recruited M (1≤M≤20) test-solvers, each of which rated every problem as "easy" or "hard."

His goal is now to create a problemset arranged in increasing order of difficulty, consisting of some subset of his N problems arranged in some order. There must exist no pair of problems such that some test-solver thinks the problem later in the order is easy but the problem earlier in the order is hard.

Count the number of distinct nonempty problemsets he can form, modulo 109+7.

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

The first line contains N and M.
The next M lines each contain a string of length N. The ith character of this string is E if the test-solver thinks the ith problem is easy, or H otherwise.

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

The number of distinct problemsets FJ can form, modulo 109+7.

SAMPLE INPUT:
3 1
EHE

SAMPLE OUTPUT:
9
The nine possible problemsets are as follows:

[1]
[1,2]
[1,3]
[1,3,2]
[2]
[3]
[3,1]
[3,2]
[3,1,2]
Note that the order of the problems within the problemset matters.

SAMPLE INPUT:

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

SAMPLE OUTPUT:
33
SCORING:
Inputs 3-4: M=1
Inputs 5-14: M≤16
Inputs 15-22: No additional constraints.
Problem credits: Benjamin Qi

Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day di, Farmer John sends a delivery of bi haybales (1≤di≤1014, 0≤bi≤109).

Process U (1≤U≤105) updates as follows: Given a pair (d,b), update the number of haybales arriving on day d to b. After each update, output the sum of all days on which Bessie eats haybales modulo 109+7.

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

U, followed by U lines containing the updates.

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

The sum after each update modulo 109+7.

SAMPLE INPUT:

3
4 3
1 5
1 2

SAMPLE OUTPUT:

15
36
18
Answers after each update:

4+5+6=15
1+2+3+4+5+6+7+8=36
1+2+4+5+6=18

SAMPLE INPUT:

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

SAMPLE OUTPUT:

4005
4656
7607
3482
3507
3753
4058
1107
24531

SCORING:

Input 3: U≤5000
Inputs 4-10: Updates only increase the number of haybales arriving on day d.
Inputs 11-22: No additional constraints.
Problem credits: Brandon Wang and Benjamin Qi