作者： chenchen

On National Milk Day, Farmer John is offering exclusive prices on buckets of milk! He has N (1≤N≤10⁵) deals numbered from 1 to N. For the i'th deal, he is offering 2i−1 buckets of milk for a_i (1≤a_i≤10⁹,a_i<a_i+1) moonies. The same deal may be taken any non-negative integer number of times.

You are thinking about Q (1≤Q≤10⁴ ) independent queries. For each query, you have an integer x (1≤x≤10⁹) in mind and wonder what is the minimum cost to purchase at least x buckets of milk.

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

The first line contains two integers N and Q.

The following line contains a₁,a₂,…,a_N.

Each of the following Q lines contains an integer x, representing a query.

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

For each query, output the minimum cost on a new line.

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 long" in C/C++).

SAMPLE INPUT:

2 4
10 15
1
2
6
7

SAMPLE OUTPUT:

10
15
45
55

In the example above, Farmer John is offering 2 deals: 1 bucket of milk for 10 moonies and 2 buckets of milk for 15 moonies.

The cheapest cost to buy 1 bucket is just the cost of the 1 bucket deal and the cheapest cost to buy 2 buckets is just the cost of the 2 bucket deal.

To get 6 buckets, the cheapest way is to purchase 3 of the 2 bucket deal for a total of 45 moonies.

To get 7 buckets, the cheapest way is to purchase 3 of the 2 bucket deal and 1 of the 1 bucket deal for a total of 55 moonies.

SAMPLE INPUT:

4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
101

SAMPLE OUTPUT:

10
20
30
30
40
50
60
60
120
760

In this example, Farmer John is offering a total of 4 deals for 1, 2, 4, and 8 buckets. For each of the 10 queries, the corresponding output indicates the minimum cost to purchase at least that amount of milk. Sometimes, it is cheaper to purchase more than the specified amount.

SCORING:

Inputs 3-4: N≤2
Inputs 5-8: N≤10
Inputs 9-16: No additional constraints.

Problem credits: Chongtian Ma

Bessie is playing the popular game "Moo Hunt". In this game, there are N (3≤N≤20) cells in a line, numbered from 1 to N. All cells either have the character M or O with the i-th cell having character s_i.

Bessie plans to perform K (1≤K≤2⋅10⁵) mooves. On her i-th moove, Bessie will tap 3 different cells (x_i,y_i,z_i) (1≤x_i,y_i,z_i≤N). Bessie will earn a point if  s_xi=M
and s_yi=s_zi=O. In other words, Bessie will earn a point if she forms the string MOO by tapping cells x_i,y_i,z_i in that order.

Farmer John wants to help Bessie get a new high score. He wants you to find the maximum possible score Bessie could get across all possible boards if she performs the K mooves as well as the number of different boards that will allow Bessie to achieve this maximum possible score. Two boards are different if there exists a cell such that the corresponding characters at the cell are different.

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

The first line contains N and K, the number of cells and the number of mooves Bessie will perform.

Each of the next K lines contains x_i,y_i,z_i describing Bessie's i-th move (x_i,y_i,z_i are pairwise distinct).

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

Output the maximum possible score Bessie could achieve, followed by the count of different boards that will allow Bessie to achieve this maximum score.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4 2

The boards MOOOM and MOOMM allow Bessie to achieve a maximum score of 4. In both boards, Bessie will earn points on mooves 1,2,5,6. It can be shown that this is the maximum score Bessie can achieve, and those two boards are the only possible boards allowing Bessie to achieve a score of 4.

SAMPLE INPUT:

6 12
2 4 3
2 3 4
3 5 2
3 5 1
3 1 5
3 1 2
6 1 5
1 6 4
2 3 6
3 6 2
4 1 6
3 4 2

SAMPLE OUTPUT:

6 3

The boards that allow Bessie to achieve a maximum possible score of 6 are OOMOOO, OOMMOO, and OOMOOM.

SCORING:

Inputs 3-5: N≤8,K≤10⁴

Inputs 6-12: There will be one test for each N∈{14,15,16,17,18,19,20} with no  additional constraints on K.

Problem credits: Alex Liang

Bessie has a computer with a keyboard that only has two letters, M and O.

Bessie wants to type her favorite moo S consisting of N letters, each of which is either an M or an O. However, her computer has been hit with a virus. Every time she tries to type the letter O, every letter that she has typed so far flips, either from M to O or from O to M, before the O appears.

Is it possible for Bessie to type out her favorite moo?

Additionally, Bessie is given a parameter k which is either 0 or 1.

If k=0, then Bessie only needs to determine whether it is possible to type out her favorite moo.

If k=1, then Bessie also needs to give an example of a sequence of keystrokes to type so she can type out her favorite moo.

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

The first line contains T, the number of independent test cases (1≤T≤10⁴) and k
(0≤k≤1).

The first line of each test case has N (1≤N≤2⋅10⁵).

The second line of each test case has S. It is guaranteed that no characters will  appear in S besides M and O.

The sum of N across all test cases will not exceed 4⋅10⁵.

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

For each test case, output either one or two lines using the following procedure.

If it is impossible for Bessie to type out S, print NO on a single line.

Otherwise, on the first line print YES. Furthermore, if k=1, on the second line,print a string of length N, the characters in order that Bessie needs to type in order to type out her favorite moo. If there are multiple such strings, any will be accepted.

SAMPLE INPUT:

2 0
3
MOO
5
OOMOO

SAMPLE OUTPUT:

YES
YES

SAMPLE INPUT:

2 1
3
MOO
5
OOMOO

SAMPLE OUTPUT:

YES
OMO
YES
MOOMO

As Bessie types out MOOMO, this is how the letters change:

1.Before typing the first M, Bessie has an empty string. Afterwards, she has the string M.

2.After typing the first O, the M flips to O, and then the O is appended to form OO.

3.After typing the second O, the OO flips to MM, and then the O is appended to form MMO.

4.After typing the second M, Bessie has the string MMOM.

5.After typing the last O, the string MMOM flips to OOMO, and then the O is  appended to form OOMOO, as desired.

SCORING:

Inputs 3-4: k=0.
Inputs 5-6: k=1,T≤10³,N≤10.
Inputs 7-9: k=1,T≤10,N≤1000.
Inputs 10-16: k=1.

Problem credits: Nick Wu

Farmer John has an array A containing N integers (1≤N≤5⋅10⁵,1≤A_i≤N). He picks his favorite index j and take out a sheet of paper with only  A_j written on it. He can then perform the following operation some number of times:

Cyclically shift all elements in A one spot to the left or one spot to the right. Then, write down A_j on a piece of paper.

Let S denote the set of distinct integers that occur in A. Farmer John wonders what the minimum number of operations he must perform is so that the paper contains all integers that appear in S.

Since it is unclear what FJ's favorite index is, output the answer for all possible favorite indices 1≤j≤N. Note for each index, A is reset to its original form before performing any operations.

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

The first line contains N.

The following line contains A₁,A₂,…,A_N.

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

Output N space-separated integers, where the i'th integer is the answer for his favorite index j=i.

SAMPLE INPUT:

6
1 2 3 1 3 4

SAMPLE OUTPUT:

4 3 3 4 3 3

The distinct numbers are S={1,2,3,4}. Suppose Farmer John’s favorite index is j=1. He starts off with A₁=1 written on a piece of paper. We can track the array A after each cyclic shift Farmer John makes.

Cyclic shift right: FJ writes down A₁=4.

4 1 2 3 1 3

Cyclic shift left: FJ writes down A₁=1 again.

1 2 3 1 3 4

Cyclic shift left: FJ writes down A₁=2.

2 3 1 3 4 1

Cyclic shift left: FJ writes down A₁=3.

3 1 3 4 1 2

At this point, Farmer John has written down every number in S using 4 operations.

SAMPLE INPUT:

12
1 1 2 1 1 3 1 1 4 1 1 1

SAMPLE OUTPUT:

8 7 6 7 8 9 8 7 6 7 8 9

SCORING:

Inputs 3-5: N≤500
Inputs 6-8: N≤10⁴
Inputs 9-17: No additional constraints.

Problem credits: Chongtian Ma

N contestants participated in a contest, each placing a distinct rank from 1
to N. There are C criteria used to invite contestants to participate in the final round, and the ith-ranked contestant satisfies a specified n_i of them (1≤n_i ≤C).

The invitation process runs as follows. First, the top f₁ students who satisfy the 1
st criteria will be invited. Then, out of all students who haven't yet been invited, the top f₂ (or all remaining if there are fewer than f₂ remaining) students who satisfy the 2nd criterion will be invited. This process repeats, for each i
from 1 to C (1≤f_i≤N).

However, some contestants will decline to participate in the final round, in which case they will be ignored when determining who to invite.

You are given a permutation p₁,p₂,…,p_N of 1…N. For each i from 0 to N−1, determine the sum of the ranks of the contestants who will be invited if the participants with ranks given by the first i elements of p decline to attend.

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

The first line contains N and C (1≤N,C≤10⁵).

The next line contains f₁,f₂,…,f_C.

The next line contains p₁…,p_N.

The next N lines each contain ni (1≤n_i≤C), followed by n_i distinct integers in [1,C], representing the criteria that the i th-ranked contestant satisfies. It is guaranteed that ∑n_i≤10⁶.

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

Output N lines, the sum of ranks of invitees before each declination.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

6
6
9
6
4

There is only one criterion. The top three remaining contestants who have not declined will be invited.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

10
14
12
9
5

Initially, the ith contestant gets invited under criterion i for all 1≤i≤4.

After the first declination, the i+1th contestant gets invited under criterion i for all 1≤i≤4.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

21
20
16
10
5
3

SCORING:

Inputs 4-6: N,C≤103,∑ni≤104
Inputs 7-8: C=1
Inputs 9-10: C=2
Inputs 11-16: No additional constraints.

Problem credits: Benjamin Qi

Farmer John and Farmer Nhoj have taken their respective cows to sit around a campfire in hopes of settling their personal differences. In total, there are N
(2≤N≤10⁵) cows sitting in a circular formation. When the farmers are ready to take their cows back to their farms, they realize one crucial mistake: since all the cows look the same and are mixed up, they are unable to identify which cows belong to which farmer!

Then the N cows are organized into one straight line to be interrogated by the two farmers. Because of the confusion, the order of the cows in the line, from 1
to N, might not correspond to their circular order around the campfire.

But the cows want to play a game. Instead of answering directly which farmer they belong to, they say which farmer the cows adjacent to them in the original circle belong to. Additionally, it is known that Farmer Nhoj's cows always lie but Farmer John raised his cows well and they will always tell the truth.

Given the statements of the cows, is it possible to assign each cow to either Farmer John or Farmer Nhoj such that the statements of the cows assigned to Farmer John are all true, and the statements of the cows assigned to Farmer Nhoj are all false?

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

The first line contains T (1≤T≤1000), the number of independent test cases, and an integer C∈{0,1} (whether to output a construction or not).

The first line of each test case contains N.

The following line contains a string of length N containing characters J or N. The i'th character is J if cow i claims the cow to their left in the circle belongs to Farmer John, or Farmer Nhoj otherwise.

The following line contains a string of length N containing characters J or N. The i'th character is J if cow i claims the cow to their right in the circle belongs to Farmer John, or Farmer Nhoj otherwise.

It is guaranteed that the sum of N over all tests does not exceed 5⋅10⁵.

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

For each test case, output YES or NO.

Additionally, if C=1 and the answer is YES, output two more lines describing your construction:

The first line should contain a permutation p₁,p₂,…,p_N of 1…N, representing the circular order of the cows around the campfire, where cow p_i is to the left of cow p_i+1 for i in 1…N−1, and cow p_N is to the left of cow p₁.

The second line should contain a string b₁b₂…b_N consisting only of Js and Ns, meaning that cow p_i belongs to Farmer John if b_i is J, or Farmer Nhoj otherwise.

Any valid construction will be accepted.

SAMPLE INPUT:

6 0
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

SAMPLE OUTPUT:

YES
NO
NO
YES
NO
YES
SAMPLE INPUT:
6 1
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

SAMPLE OUTPUT:

YES
1 2 3
JJJ
NO
NO
YES
1 2 3 4
NJNJ
NO
YES
4 5 2 1 3
JJJJN

Consider the output for the sixth test case. Cows 1, 2, 4, 5 belong to Farmer John, and Cow 3 belongs to Farmer Nhoj.

The cows will then behave as follows:

Cow 1's left and right neighbours are Cow 2 and Cow 3, respectively. Cow 1 says that Cow 2 belongs to Farmer John, and Cow 3 belongs to Farmer Nhoj.

Cow 2's left and right neighbours are Cow 5 and Cow 1, respectively. Cow 2 says that both cows belong to Farmer John.

Cow 3's left and right neighbours are Cow 1 and Cow 4, respectively. Cow 3 (dishonestly) says that both cows belong to Farmer Nhoj.

Cow 4's left and right neighbours are Cow 3 and Cow 5, respectively. Cow 4 says that Cow 3 belongs to Farmer Nhoj, and Cow 5 belongs to Farmer John.

Cow 5's left and right neighbours are Cow 4 and Cow 2, respectively. Cow 5 says that both cows belong to Farmer John.

All these claims are consistent with the input.

SCORING:

Input 3: C=0 and N≤10
Input 4: C=1 and N≤10
Inputs 5-8: C=0
Inputs 9-12: C=1

Problem credits: Chongtian Ma

Bessie is trying to evade the farmers. The farmers own N (2≤N≤5⋅10⁵) farms with a one way road between the i-th farm and the ai-th farm (1≤i≤N,  a_i≠i). There are F (1≤F≤N) farmers and the i-th farmer is initially stationed at farm

s_i(1≤s_i≤N, all si unique). At each time step, every farmer takes the road at their current farm and moves to the next. Bessie gets caught if she is ever located at the same farm as any farmer.

Suppose Bessie starts at some farm b. At each time step, she has two options: she can either choose to rest (stay at her current farm) or take the road and move to the next farm. If she chooses to move, she moves simultaneously with the farmers. Bessie moves so that she is never caught by any farmer in a finite number of timesteps.

For each starting farm b (1≤b≤N), find the maximum number of times Bessie can choose the rest option if she starts at farm b.

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

The first line contains N and F, the number of farms and the number of farmers.

The second line contains a₁…a_N, the one-way roads going out of each farm.

The third line contains s₁…s_F, the starting locations of each farmer.

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

Output N lines, the b-th of which must consist of a single integer denoting the maximum number of times Bessie can choose the rest option if she starts at farm b. If there is no way for Bessie to ensure she is never caught after a finite number of timesteps, then output −1. If Bessie can rest an infinite number of times, then output −2.

SAMPLE INPUT:

4 1
2 1 4 3
1

SAMPLE OUTPUT:

-1
0
-2
-2

Farm 1: If Bessie starts at a farm with a farmer, then she is caught immediately, and you should output −1.

Farm 2: Bessie must choose to move at every timestep to avoid being caught by the farmer who starts at farm 1.

Farms 3-4: Bessie can rest an infinite number of times without being caught.

SCORING:

Input 2: N≤50
Inputs 3-10: N≤2000
Inputs 11-20: No additional constraints.

Problem credits: Alex Liang

Bessie is given an undirected graph with N (1≤N≤2⋅10⁵) vertices labeled 1…N and M edges (N−1≤M≤2⋅10⁵). Each edge is described by two integers u,v(1≤u,v≤N) describing an undirected edge between nodes u and v and a lowercase Latin letter c in the range a..z that is the value on the edge. The graph given is guaranteed to be connected. There may be multiple edges or self-loops.

Define f(a,b) as the lexicographically smallest concatenation of edge values over all paths starting from node a and ending at node b. A path may contain the same edge more than once (i.e., cycles are allowed).

For each i (1≤i≤N), help Bessie determine the length of f (1,i). Output this length if it is finite, otherwise output −1.

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

The first line contains T (1≤T≤10), the number of independent tests. Each test is specified in the following format:

The first line contains N and M.

The next M lines each contain two integers followed by a lowercase Latin character.

It is guaranteed that neither the sum of N nor the sum of M over all tests exceeds 4⋅10⁵.

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

For each test, output N space-separated integers on a new line.

SAMPLE INPUT:

2
1 0
2 2
1 1 a
2 1 b

SAMPLE OUTPUT:

0
0 -1

For the first test case, node 1 can be reached with an empty path, so the answer is 0. In the second test case, node 2 cannot have a lexicographically smallest path, since FJ can repeat the 'a' self-loop any number of times before moving to node 2, producing arbitrarily long strings that are still lexicographically minimal. Therefore, the answer for node 2 is -1.

SAMPLE INPUT:

2
7 7
1 2 a
1 3 a
2 4 b
3 5 a
5 6 a
6 7 a
7 4 a
4 3
1 2 z
2 3 x
3 4 y

SAMPLE OUTPUT:

0 1 1 5 2 3 4
0 1 2 -1

For the first test case, node 1 has distance 0. Nodes 2 and 3 are adjacent with node 1, and they have distance 1. For nodes 4, 5, 6, and 7, it can be proven that the lexicographically shortest path does not pass through the edge between node 2 and 4.

For the second test case, node 4 again has no lexicographically smallest path, since the string can be extended indefinitely while remaining lexicographically minimal. Thus, its answer is -1.

SCORING:

Inputs 3-4: Every character is a.
Inputs 5-8: Every character is a or b.
Inputs 9-14: N,M≤5000
Inputs 15-22: No additional constraints.

Problem credits: Daniel Zhu and Yash Belani

Farmer John has N (1≤N≤5⋅10⁴) barns arranged along a road. The i-th barn contains a_i bales of hay and b_i bags of feed (0≤a_i ,b_i ≤10⁹).

Bessie has been complaining about the inequality between barns. She defines the "imbalance" of the farm as the difference between the maximum hay in any barn and the minimum feed in any barn. Formally, the imbalance is max(a)−min(b).

To address Bessie's concerns, Farmer John can perform exactly K (1≤K≤10¹⁸ ) transfers. In each transfer, he selects a barn i, sells one of its haybales, and buys it a new bag of feed for the same barn. Note that there can be negative amounts in his farm (he is not afraid of debt). Formally, K times, you choose an index i∈[1,N], decrement a_i, and increment b_i .

Help Farmer John determine the minimum possible imbalance after performing exactly K transfers.

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

The first line contains T (1≤T≤10³), the number of independent test cases.

The first line of each test case contains Nand K.

The following line contains a₁…a_N.

The following line contains b₁…b_N.

The sum of N over all test cases is at most 5⋅10⁴ .

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

For each test case, output a single integer, the minimum possible value of max(a−min(b) after performing K operations.

SAMPLE INPUT:

4
1 10
5
3
2 6
100 96
0 4
3 3
1 1 2
0 0 1
3 3
1 2 2
0 1 1

SAMPLE OUTPUT:

-18
90
0
0

In the first test case, Farmer John can transfer 10 haybales from barn 1 into bags of feed. This leaves a=[−5] and b=[13]. The imbalance is max(a−min(b)=−5−13=−18.

In the second test case, Farmer john can transfer 5 haybales from barn 1 and 1 haybale from barn 2. This leaves a=[95,95] and b=[5,5]. The imbalance is 95−5=90. This is the minimum imbalance Farmer John can achieve.

SCORING:

Inputs 2-4: K≤500, sum of N over all testcases is ≤500
Inputs 5-8: Sum of N over all testcases is ≤500
Inputs 9-13: No additional constraints.

Problem credits: Rohin Garg

Farmer Nhoj has trapped Bessie on a rooted tree with N (2≤N≤2⋅10⁵) nodes, where node 1 is the root. Scared and alone, Bessie makes the following move each second:

If Bessie's current node has no children, then she will move to a random ancestor of the current node (excluding the node itself).

Otherwise, Bessie will move to a random child of the current node.

Initially, Bessie is at node x, and her only way out is the exit located at node y (1≤x,y≤N). For Q (1≤Q≤2⋅10⁵) independent queries of x and y, compute the expected number of seconds it would take Bessie to reach node y for the first time if she started at node x, modulo 10⁹+7.

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

The first line contains N and Q.

The next line contains N−1 integers p₂,…p_N describing the tree (1≤p_i<i). For each 2≤i≤N, there is an edge between nodes i and p_i.

Each of the next Q lines contains integers x and y representing the nodes for that query.

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

For each query, output the expected number of seconds for Bessie to reach node y for the first time starting at node x, modulo 10⁹+7.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
4
3
3
1

In the 1st query, the expected time to reach node 1 from itself is 0.

In the 3rd query, after 1 second, Bessie will be at node 1 with probability 12 and at node 2 with probability 12. Since the expected time to reach node 1 from node 2 is 4, the expected time for Bessie to reach node 1 starting at node 3 is 1+12⋅0+12⋅4=3.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
3
500000011
500000011
6

In the 3rd query, the expected time to reach node 3 from node 1 is 152.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018

SCORING:

Inputs 4-8: For all queries, y=1.
Inputs 9-13: For all queries, x=1.
Inputs 14-18: For each 2≤i≤N, p_i is uniformly randomly chosen from the range [1,i−1].

Inputs 19-23: No additional constraints.

Problem credits: Avnith Vijayram