Problem Statement

Given is a string S consisting of lowercase English letters. Snuke can do the operation of swapping two adjacent characters in S. For example, if S=agc, one operation can change it to gac (by swapping a and g) or acg (by swapping g and c).

Snuke wants to do this operation zero or more times so that atcoder <S holds lexicographically.

Determine whether the objective is achievable. If it is achievable, find the minimum number of operations needed.

Solve T test cases in an input file.

Constraints

• 1 \leq T \leq 100
• 1 \leq |S| \leq 1000
• S is a string consisting of lowercase English letters.

Sample Input 1

3
atcodeer
codeforces
aaa

Sample Output 1

1
0
-1

• The first test case: for example, swapping the last two characters makes S=atcodere > atcoder hold.
• The second test case: before doing any operation, we already have S=codeforces > atcoder.
• The third test case: no sequence of operations makes S> atcoder hold.

Problem Statement

In this problem, we consider strings consisting of (, ), [, and ].

A string x is said to be a good parentheses sequence if and only if one of the following conditions is satisfied:

• x is an empty sequence.
• There is a good parentheses sequence s such that concatenating (, s, and ) in this order results in x.
• There is a good parentheses sequence s such that concatenating [, s, and ] in this order results in x.
• There are non-empty good parentheses sequences s and t such that concatenating s and t in this order results in x.

For example, [], ([()]), and ()[()] are good parentheses sequences, but neither ()) nor ([)] is a good parentheses sequence.

Given are an even number N and integer sequences A and B of length N each. Here, we define a score for a good parentheses sequence of length N, s=s_1s_2\cdots s_N, as follows:

• The score for s is the sum of the scores of its characters.
• The score for the i-th character (1 \leq i \leq N) is A_i if s_i is ( or ), and B_i if s_i is [ or ].

Find the maximum possible score for a good parentheses sequence of length N.

Constraints

• 2 \leq N \leq 10^5
• N is an even number.
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All numbers in input are integers.

Sample Input 1

4
4 2 3 1
2 3 2 4

Sample Output 1

12

For s=()[], the score is A_1+A_2+B_3+B_4=12, which is the maximum possible value.

Sample Input 2

10
866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072
178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937

Sample Output 2

6629738472

Problem Statement

There are L squares lining up horizontally in a row, numbered 1, 2, \ldots, L from left to right.

On those squares are N penguins, numbered 1, 2, \ldots, N from left to right. Initially, Penguin i is on Square A_i. Here, 1 \leq A_1 < A_2 < \ldots < A_N \leq L holds.

You can do the following operations any number of times:

• Choose one penguin and slide it to the left or the right. The penguin will keep sliding as long as there is an empty square ahead. It will stop when it reaches a square just before a square occupied by another penguin, or there is no square ahead.

For example, assume that N=3, L=10, and the penguins are on the squares (2,3,7). Here, if we slide Penguin 2 to the right, it will move to Square 6; if we slide Penguin 3 to the right, it will move to Square 10.

Your objective is to put Penguin i on Square B_i for every i. Here, 1 \leq B_1 < B_2 < \ldots < B_N \leq L holds. Determine whether the objective is achievable. If it is achievable, find the minimum number of operations needed.

Constraints

• 1 \leq N \leq 10^5
• N \leq L \leq 10^9
• 1 \leq A_1 < A_2 < \ldots < A_N \leq L
• 1 \leq B_1 < B_2 < \ldots < B_N \leq L
• All numbers in input are integers.

Sample Input 1

4 11
3 4 6 10
1 5 6 11

Sample Output 1

3

The following sequence of operations achieves the objective:

• Slide Penguin 1 to the left. The penguins are now on the squares (1,4,6,10).
• Slide Penguin 2 to the right. The penguins are now on the squares (1,5,6,10).
• Slide Penguin 4 to the right. The penguins are now on the squares (1,5,6,11).

Sample Input 2

1 3
1
2

Sample Output 2

-1

Sample Input 3

10 1000000000
65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792
1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000

Sample Output 3

13

Problem Statement

There are N piles of stones lying in a row. The i-th pile from the left contains A_i stones.

Two players, FirstLeft and SecondRight, play a game. They alternately play a turn, with FirstLeft going first. In each turn, the player does the following operation:

• In FirstLeft's turn: he removes one or more stones from the leftmost pile with one or more stones.
• In SecondRight's turn: he removes one or more stones from the rightmost pile with one or more stones.

The player who becomes unable to play his turn loses. Determine the winner of the game when the players act optimally.

Solve T test cases in an input file.

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^9

Sample Input 1

3
1
10
2
3 2
3
2 1 2

Sample Output 1

First
First
Second

For example, in the third game, one possible scenario is as follows:

• FirstLeft takes 2 stones from the leftmost pile. The piles now contain 0,1,2 stone(s).
• SecondRight takes 1 stone from the rightmost pile. The piles now contain 0,1,1 stone(s).
• FirstLeft takes 1 stone from the middle pile. The piles now contain 0,0,1 stone(s).
• SecondRight takes 1 stone from the rightmost pile. The piles now contain 0,0,0 stones.
• FirstLeft is unable to do his operation and loses.

Problem Statement

For an integer sequence of length N, A=(A_1,A_2,\cdots,A_N), and an integer T, let f(A,T) defined as follows:

• f(A, T) is the lexicographically greatest integer sequence x that satisfies all of the conditions below. Here, under the constraints in this problem, it can be proved that there always are sequences that satisfy the conditions and that the number of those sequences is finite. Thus, f(A, T) can always be defined.

  • x is a sequence of length N consisting of non-negative integers.
  • For each i (1 \leq i \leq N), let y_i be the number of indices j such that j<i and A_j+T \times x_j < A_i+T \times x_i. Then, y_i=x_i holds.

For example, assume that A=(6,5,1) and T=3. Then, the sequences x that satisfy the conditions are: (0,0,0), (0,0,2), and (0,1,0). Thus, the value of f(A, T) is the lexicographically maximum among them: (0,1,0).

Now, Snuke has N integer sequences B_1,B_2,\cdots,B_N and an integer T. Each of the sequences B_i (1 \leq i \leq N) is an integer sequence of length K.

He will create an integer sequence A of length N and compute f(A, T). The value of A_i will be chosen from B_{i,1},B_{i,2},\cdots,B_{i,K}. Here, if B_i contains the same value multiple times, we will distinguish those occurrences; that is, there are K^N ways to create A.

For every i (1 \leq i \leq N), solve the following problem:

• For all K^N choices of A, we will compute f(A,T) and record the value of its i-th element. Find the sum of these values, modulo (10^9+7).

Constraints

• 1 \leq N \leq 50
• 1 \leq K \leq 50
• 1 \leq T \leq 10^7
• 1 \leq B_{i,j} \leq 10^9

Sample Input 1

2 2 1
1 2
1 2

Sample Output 1

0
3

• For A=(1,1): f(A,T)=(0,1)
• For A=(1,2): f(A,T)=(0,1)
• For A=(2,1): f(A,T)=(0,0)
• For A=(2,2): f(A,T)=(0,1)

Thus, the answer is 0+0+0+0=0 for i=1 and 1+1+0+1=3 for i=2.

Sample Input 2

3 2 3
6 2
5 3
1 4

Sample Output 2

0
6
13

Sample Input 3

10 15 45
129 82 26 185 217 258 22 192 24 117 167 255 91 180 203
171 73 168 26 208 169 115 164 121 214 154 196 172 66 230
185 178 241 220 243 143 111 124 10 62 56 117 254 43 81
201 74 213 163 204 35 44 203 207 73 218 60 243 51 250
229 117 212 245 112 152 206 96 266 165 105 94 231 41 27
261 201 258 111 100 72 239 31 199 203 226 151 72 268 44
94 19 47 243 133 174 141 82 190 62 175 256 126 123 210
186 64 73 82 68 183 261 120 265 212 18 24 36 152 92
205 101 186 91 172 153 91 242 141 97 247 193 45 245 66
225 97 162 213 61 219 184 195 80 203 79 72 269 258 199

Sample Output 3

0
248044096
333666695
536381826
8787512
11659012
661959013
166067001
529828166
526544756

Problem Statement

Snuke received a big blackboard. Being pleased with this present, he first wrote some positive integers. Then, he repeated the following operation until there was no integer written on the blackboard:

• Choose one integer written on the blackboard and erase it. Let x be the erased integer. Then, record the remainder of x divided by 2 on his notebook. Finally, if x \geq 2, write a new integer x-1 on the blackboard.

Snuke's record is represented by a string S consisting of 0 and 1, where S_i is the remainder of the chosen integer divided by 2 in the i-th operation.

Snuke forgot the combination of positive integers he first wrote on the blackboard. From the information given as the string S, find the number of possible combinations of positive integers he first wrote on the blackboard. Here, we consider combinations a and b of positive integers different when there is an integer v such that the numbers of times v occurs in a and v occurs in b differ. Since the count can be enormous, compute it modulo (10^9+7). Also, it is possible that Snuke's record is incorrect and that no combination of positive integers satisfies the condition. In such a case, just answer 0.

Constraints

• 1 \leq |S| \leq 300
• S is a string consisting of 0 and 1.

Sample Input 1

101

Sample Output 1

2

There are two possible combinations of integers written on the blackboard: \{1,2\} and \{3\}.

Sample Input 2

100

Sample Output 2

0

There is no possible combination of integers written on the blackboard.

Sample Input 3

010101

Sample Output 3

3

There are three possible combinations of integers written on the blackboard: \{2,2,2\}, \{2,4\}, and \{6\}.

Sample Input 4

11101000111110111101001011110010111110101111110111

Sample Output 4

3904