作者： chenchen

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

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

Farmer John has N(1≤N≤5000) cows standing around a circular track divided into M(1≤M≤10⁶) equally spaced positions, numbered 0 to M−1 clockwise. Cow i is initially at position x_i , where 0=x₁<x₂<⋯<x_N<M.

For each 1≤i≤N, cow i will independently and randomly choose either to face clockwise or counterclockwise with some probability specific to that cow. Once a cow has chosen her initial direction, she begins moving continuously in that direction at a constant speed of one position per minute. Whenever two cows meet (i.e., they occupy the same space), they bounce off of each other: immediately reversing their directions and continuing to move at the same speed in that direction.

Farmer John is wondering where cow 1 will end up. For each 0≤i<M, find the probability that cow 1 is at position i after K (1≤K≤10¹⁸) minutes.

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

The first line contains T (1≤T≤100), the number of independent test cases. Each test case is specified as follows:

The first line of each test case contains N(1≤N≤5000), M(1≤M≤10⁶), and K(1≤K≤10¹⁸ ).

The second line contains N integers p₁,…,p_N (0≤p_i<10⁹+7) where if a_i/b_i is the probability cow i goes clockwise, then p_i⋅b_i≡a_i(mod10⁹+7).

The third and final line contains N integers x₁,x₂,…,x_N.

It is guaranteed that the sum of N² over all test cases is ≤5000² and the sum of M over all testcases is ≤10⁶.

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

Output a new line for each test case. The line for each test case should be formatted as follows:

For every 0≤i<M, let p_i/q_i be the probability cow 1 is in position i at the end of K
minutes. Output M space-separated integers p_iq_i^-1 (mod 10⁹+7)

(where p_iq_i^-1≡pi(mod 10⁹+7)).

SAMPLE INPUT:

3
2 2 1
500000004 500000004
0 1
3 3 1
500000004 500000004 500000004
0 1 2
5 10 13
500000004 1 500000004 0 500000004
0 3 4 7 9

SAMPLE OUTPUT:

500000004 500000004
500000004 250000002 250000002
0 0 0 125000001 375000003 0 125000001 375000003 0 0

For the first test case, both cows have a 1/2 chance of going in either direction. If both pick the same direction, they will end up swapping positions (so cow 1 ends up at 1). Otherwise, they will bounce off in the middle and return to their original positions. Therefore, there is a 12 chance for cow 1 to end up at 0 and a 12 chance for cow 1 to end up at 1.

For the second test case, all cows again have a 12 chance of going in either direction. For each combination of directions, here is where cow 1 ends up at.

CW, CW, CW: 1
CW, CW, CCW: 1
CCW, CCW, CCW: 2
CCW, CW, CCW: 2
CW, CCW, CW: 0
CW, CCW, CCW: 0
CCW, CW, CW: 0
CCW, CCW, CW: 0

SCORING:

Input 2: K≤100,N≤10.
Input 3: N≤10.
Inputs 4-7: ∑N³≤500³.
Inputs 8-11: K<M/2.
Inputs 12-15: No additional constraints.

Problem credits: Sujay Konda

Farmer John has N (2≤N≤1000) cows at distinct locations l₁,…,l_N along a circle of circumference C (0≤l₁<l₂<⋯<l_N<C,N≤C≤10⁹).

FJ will select k pairs of cows, where 1≤k≤⌊N/2⌋, and no cow is selected more than once. He wants to select the pairs such that the minimum distance between any two cows in the same pair along the circumference of the circle is maximized.

For each value of k, help FJ determine the maximum possible minimum distance.

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

The first line contains N and C.

The second line contains l₁…l_N .

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

Output a single line with ⌊N/2⌋space-separated integers, with the answers for k=1…⌊N/2⌋in that order.

SAMPLE INPUT:

4 100
0 25 50 75

SAMPLE OUTPUT:

50 50

For k=1, cow 1 can be paired to cow 3, which is distance 50 away along the circumference of the circle, making the answer 50.

For k=2, cow 1 can be paired to cow 3, and cow 2 can be paired to cow 4, which is distance 50 away from it along the circumference of the circle, making the answer still 50.

SAMPLE INPUT:

4 100
0 1 2 99

SAMPLE OUTPUT:

3 2

For k=1, cow 3 can be paired to cow 4, which is distance 2+100−99=3 away from it along the circumference of the circle, making the answer 3.

For k=2, cow 1 can be paired to cow 3 and cow 2 can be paired to cow 4. Each of these pairs contains two cows at a distance of 2 from each other along the circumference of the circle, making the answer 2.

SCORING:

Inputs 3-4: 2l_N≤C
Inputs 5-6: N≤20
Inputs 7-14: N≤100
Inputs 15-22: No additional constraints.

Problem credits: Benjamin Qi