作者： chenchen

Farmer John's cows each want to find their soulmate -- another cow with similar characteristics with whom they are maximally compatible. Each cow's personality is described by an integer pi (1≤pi≤10^18). Two cows with the same personality are soulmates. A cow can change her personality via a "change operation" by multiplying by 2, dividing by 2 (if pi is even), or adding 1.
Farmer John initially pairs his cows up in an arbitrary way. He is curious how many change operations would be needed to make each pair of cows into soulmates. For each pairing, decide the minimum number of change operations the first cow in the pair must make to become soulmates with the second cow.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N (1≤N≤10), the number of pairs of cows. Each of the remaining N lines describes a pair of cows in terms of two integers giving their personalities. The first number indicates the personality of the cow that must be changed to match the second.
OUTPUT FORMAT (print output to the terminal / stdout):
Please write N lines of output. For each pair, print the minimum number of operations required for the first cow to make her personality match that of the second.
SAMPLE INPUT:
6
31 13
12 8
25 6
10 24
1 1
997 120
SAMPLE OUTPUT:
8
3
8
3
0
20
For the first test case, an optimal sequence of changes is 31⟹32⟹16⟹8⟹9⟹10⟹11⟹12⟹13.
For the second test case, an optimal sequence of changes is 12⟹6⟹7⟹8.
SCORING:
Test cases 1-4 satisfy pi≤10^5.
Test cases 5-12 satisfy no additional constraints.

Farmer John's cows have decided to offer a programming contest for the cows on Farmer Nhoj's farm. In order to make the problems as fun as possible, they have spent considerable time coming up with challenging input cases. For one problem in particular, "Haybales", the cows need your help devising challenging inputs. This involve solving the following somewhat intriguing problem:
There is an array of sorted integers x1≤x2≤?≤xN (1≤N≤10^5), and an integer K. You don't know the array or K, but you do know for each index i, the largest index ji such that xji≤xi+K. It is guaranteed that i≤ji and j1≤j2≤?≤jN≤N.
Given this information, Farmer John's cows need to construct any array along with some integer K that matches that information. The construction needs to satisfy 0≤xi≤10^18 for all i and 1≤K≤10^18.
It can be proven that this is always possible. Help Farmer John's cows solve this problem!
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N. The next line contains j1,j2,…,jN.
OUTPUT FORMAT (print output to the terminal / stdout):
Print K, then x1,…,xN on separate lines. Any valid output will be accepted.
SAMPLE INPUT:
6
2 2 4 5 6 6
SAMPLE OUTPUT:
6
1
6
17
22
27
32
The sample output is the array a=[1,6,17,22,27,32] with K=6. j1=2 is satisfied because a2=6≤1+6=a1+K but a3=17>1+6=a1+K, so a2 is the largest element that is at most a1. Similarly,
j2=2 is satisfied because a2=6≤6+6 but a3=17>6+6
j3=4 is satisfied because a4=22≤17+6 but a5=27>17+6
j4=5 is satisfied because a5=27≤22+6 but a5=32>22+6
j5=6 is satisfied because a6=32≤27+6 and a6 is the last element of the array
j6=6 is satisfied because a6=32≤32+6 and a6 is the last element of the array
This is not the only possible correct output for the sample input. For example, you could instead output the array [1,2,4,5,6,7] with K=1.
SCORING:
For 50% of all inputs, N≤5000
For the remaining inputs, there are no additional constraints.

Farmer John operates a collection of N farms (1≤N≤2·10^5), conveniently numbered 1…N. Initially, there are no roads connecting these farms to each-other, and each farm is actively producing milk.
Due to the dynamic nature of the economy, Farmer John needs to make changes to his farms according to a series of Q update operations (0≤Q≤2⋅10^5). Update operations come in three possible forms:
(D x) Deactivate an active farm x, so it no longer produces milk.
(A x y) Add a road between two active farms x and y.
(R e) Remove the eth road that was previously added (e=1 is the first road that was added).
A farm x that is actively producing milk, or that can reach another active farm via a series of roads, is called a "relevant" farm. For each farm x, please calculate the maximum i (0≤i≤Q) such that x is relevant after the i-th update.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N and Q. The next Q lines each contain an update of one of the following forms:
D x
A x y
R e
It is guaranteed that for updates of type R, e is at most the number of roads that have been added so far, and no two updates of type R have the same value of e.
OUTPUT FORMAT (print output to the terminal / stdout):
Please output N lines, each containing an integer in the range 0…Q.
SAMPLE INPUT:
5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3
SAMPLE OUTPUT:
7
8
6
9
9
In this example, roads are removed in the order (2,3),(1,2),(2,4).
Farm 1 is relevant just before (1,2) is removed.
Farm 2 is relevant just before (2,4) is removed.
Farm 3 is relevant just before (2,3) is removed.
Farms 4 and 5 are still active after all queries. Therefore they both stay relevant, and the output for both should be Q.
SCORING:
Tests 2 through 5 satisfy N≤103, Q≤2⋅103
Test cases 6 through 20 satisfy no additional constraints.

The grass has dried up in Farmer John's pasture due to a drought. After hours of despair and contemplation, FJ comes up with the brilliant idea of purchasing corn to feed his precious cows.
FJ’s N (1≤N≤100) cows are arranged in a line such that the ith cow in line has a non-negative integer hunger level of hi. As FJ’s cows are social animals and insist on eating together, the only way FJ can decrease the hunger levels of his cows is to select two adjacent cows i and i+1 and feed each of them a bag of corn, causing each of their hunger levels to decrease by one.
FJ wants to feed his cows until all of them have the same non-negative hunger level. Although he doesn't know his cows' exact hunger levels, he does know an upper bound on the hunger level of each cow; specifically, the hunger level hi of the i-th cow is at most Hi (0≤Hi≤1000).
Your job is to count the number of N-tuples of hunger levels [h1,h2,…,hN] that are consistent with these upper bounds such that it is possible for FJ to achieve his goal, modulo 10^9+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The second line contains H1,H2,…,HN.
OUTPUT FORMAT (print output to the terminal / stdout):
The number of N-tuples of hunger levels modulo 10^9+7.
SAMPLE INPUT:
3
9 11 7
SAMPLE OUTPUT:
241
There are (9+1)⋅ (11+1)⋅ (7+1) 3-tuples h that are consistent with H.
One of these tuples is h=[8,10,5]. In this case, it is possible to make all cows have equal hunger values: give two bags of corn to both cows 2 and 3, then give five bags of corn to both cows 1 and 2, resulting in each cow having a hunger level of 3.
Another one of these tuples is h=[0,1,0]. In this case, it is impossible to make the hunger levels of the cows equal.
SAMPLE INPUT:
4
6 8 5 9
SAMPLE OUTPUT:
137
SCORING:
N is even in even-numbered tests and odd in odd-numbered tests.
Tests 3 and 4 satisfy N≤6 and Hi≤10.
Tests 5 through 10 satisfy N≤50 and Hi≤100.
Tests 11 through 20 satisfy no further constraints.

The cows are taking a multiple choice test. But instead of a standard test where your selected choices are scored for each question individually and then summed, in this test your selected choices are summed before being scored.
Specifically, you are given N (2≤N≤10*5) groups of integer vectors on the 2D plane, where each vector is denoted by an ordered pair (x,y). Choose one vector from each group such that the sum of the vectors is as far away from the origin as possible.
It is guaranteed that the total number of vectors is at most 2?105. Each group has size at least 2, and within a group, all vectors are distinct. It is also guaranteed that every x and y coordinate has absolute value at most 109N.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N, the number of groups.
Each group starts with G, the number of vectors in the group, followed by G lines containing the vectors in that group. Consecutive groups are separated by newlines.
OUTPUT FORMAT (print output to the terminal / stdout):
The maximum possible squared Euclidean distance.
SAMPLE INPUT:
3
2
-2 0
1 0
2
0 -2
0 1
3
-5 -5
5 1
10 10
SAMPLE OUTPUT:
242
It is optimal to select (1,0) from the first group, (0,1) from the second group, and (10,10) from the third group. The sum of these vectors is (11,11), which is squared distance 112+112=242 from the origin.
SCORING:
In test cases 1-5, the total number of vectors is at most 103.
In test cases 6-9, every group has size exactly two.
Test cases 10-17 satisfy no additional constraints.

As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has N (1≤N≤5000) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤10^9) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
If two adjacent stacks' heights differ by exactly one, she can move the top haybale of the taller stack to the shorter stack.
How many configurations are obtainable after performing the above operation finitely many times, modulo 109+7? Two configurations are considered the same if, for all i, the ith stack has the same number of haybales in both.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases, all of which must be solved to solve one input correctly.
Each test case consists of N, and then a sequence of N heights. It is guaranteed that the sum of N over all test cases does not exceed 5000.

OUTPUT FORMAT (print output to the terminal / stdout):
Please output T lines, one for each test case.
SAMPLE INPUT:
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 5
SAMPLE OUTPUT:
4
4
5
15
9
8
19
For the first test case, the four possible configurations are:

(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2).
For the second test case, the four possible configurations are:

(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2).
SCORING:
Inputs 1-3 satisfy N≤10.
Input 4 satisfies 1≤hi≤3 for all i.
Inputs 5-7 satisfy |hi−i|≤1 for all i.
Inputs 8-10 satisfy 1≤hi≤4 for all i and N≤10^0.
Inputs 11-13 satisfy N≤100.
Inputs 14-17 satisfy N≤1000.
Inputs 18-21 satisfy no additional constraints.

As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has N (1≤N≤5000) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤109) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
If two adjacent stacks' heights differ by exactly one, she can move the top haybale of the taller stack to the shorter stack.
How many configurations are obtainable after performing the above operation finitely many times, modulo 10^9+7? Two configurations are considered the same if, for all i, the ith stack has the same number of haybales in both.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases, all of which must be solved to solve one input correctly.
Each test case consists of N, and then a sequence of N heights. It is guaranteed that the sum of N over all test cases does not exceed 5000.

OUTPUT FORMAT (print output to the terminal / stdout):
Please output T lines, one for each test case.
SAMPLE INPUT:
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 5
SAMPLE OUTPUT:
4
4
5
15
9
8
19
For the first test case, the four possible configurations are:

(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2).
For the second test case, the four possible configurations are:

(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2).
SCORING:
Inputs 1-3 satisfy N≤10.
Input 4 satisfies 1≤hi≤3 for all i.
Inputs 5-7 satisfy |hi−i|≤1 for all i.
Inputs 8-10 satisfy 1≤hi≤4 for all i and N≤100.
Inputs 11-13 satisfy N≤100.
Inputs 14-17 satisfy N≤1000.
Inputs 18-21 satisfy no additional constraints.
Problem credits: Daniel Zhang

Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has N (1≤N≤10^5) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤10^9) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
If two adjacent stacks' heights differ by at most K (1≤K≤10^9), she can swap the two stacks.
What is the lexicographically minimum sequence of heights that Bessie can obtain after some sequence of these operations?

**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N and K. The i+1-st line contains the height of the i-th haybale.
OUTPUT FORMAT (print output to the terminal / stdout):
Please print out N lines, the i-th containing the height of the i-th haybale in the solution.
SAMPLE INPUT:
5 3
7
7
3
6
2
SAMPLE OUTPUT:
6
7
7
2
3
One way that Bessie can swap the stacks is as follows:

7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3
SCORING:
In 10% of all input cases, N≤10^0
In another 20% of all input cases, N≤5000
In the remaining 70% of input cases, there are no additional constraints
Problem credits: Daniel Zhang and Benjamin Qi

In an effort to improve her vocabulary, Bessie the cow has obtained a set of four wooden blocks, each one a cube with a letter of the alphabet written on each of its six sides. She is learning how to spell by arranging the blocks in a row so the letters on top of the blocks spell words.
Given the letters on each of Bessie's four blocks, and a list of words she would like to spell, please determine which of words on her list she will be able to spell successfully using the blocks.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N (1≤N≤10), the number of words that Bessie would like to spell. The next four lines each contain a string with six uppercase letters, representing the letters on the six sides of one of Bessie's blocks. The next N lines contain the N words Bessie would like to spell. Each of these is between 1 and 4 uppercase letters long.
OUTPUT FORMAT (print output to the terminal / stdout):
For each word on Bessie's list, output YES if she is able to spell it using the blocks and NO otherwise.
SAMPLE INPUT:
6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM
SAMPLE OUTPUT:
YES
NO
YES
YES
NO
NO
In this example, Bessie can spell COW, ZOO, and MOVE. Sadly, she cannot spell MOO, since the only block with an M cannot also be used for an O. She cannot spell FARM since there is no block with a letter R. She cannot spell CODE since the C, D, and E all belong to the same block.

Problem credits: Brian Dean

In what seems to be a familiar occurrence, Farmer John is lining up his N cows (1≤N≤10^5), conveniently numbered 1…N, for a photograph.
Initially, the cows are lined up in the order a1,a2,…,aN from left to right. Farmer John's goal is to line up the cows in the order b1,…,bN from left to right. To accomplish this, he may perform a series of modifications to the ordering. Each modification consists of choosing a single cow and moving it some number of positions to the left.

Please count the minimum number of modifications required in order for Farmer John to line up his cows in the desired order.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N. The second line contains a1,a2,…,aN. The third line contains b1,b2,…,bN.
OUTPUT FORMAT (print output to the terminal / stdout):
Print the minimum number of modifications required to produce Farmer John's desired ordering.
SAMPLE INPUT:
5
1 2 3 4 5
1 2 3 4 5
SAMPLE OUTPUT:
0
In this example, the cows are already in the desired order, so no modifications are required.

SAMPLE INPUT:
5
5 1 3 2 4
4 5 2 1 3
SAMPLE OUTPUT:
2
In this example, two modifications suffice. Here is one way Farmer John can rearrange his cows:

Choose cow 4 and move it four positions to the left.
Choose cow 2 and move it two positions to the left.
5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3
SCORING:
Test cases 3-6 satisfy N≤100.
Test cases 7-10 satisfy N≤5000.
Test cases 11-14 satisfy no additional constraints.
Problem credits: Benjamin Qi