Problem Statement

Takahashi lives in another world. There are slimes (creatures) of 10000 colors in this world. Let us call these colors Color 1, 2, ..., 10000.

Takahashi has N slimes, and they are standing in a row from left to right. The color of the i-th slime from the left is a_i. If two slimes of the same color are adjacent, they will start to combine themselves. Because Takahashi likes smaller slimes, he has decided to change the colors of some of the slimes with his magic.

Takahashi can change the color of one slime to any of the 10000 colors by one spell. How many spells are required so that no slimes will start to combine themselves?

Constraints

• 2 \leq N \leq 100
• 1 \leq a_i \leq N
• All values in input are integers.

Sample Input 1

5
1 1 2 2 2

Sample Output 1

2

For example, if we change the color of the second slime from the left to 4, and the color of the fourth slime to 5, the colors of the slimes will be 1, 4, 2, 5, 2, which satisfy the condition.

Sample Input 2

3
1 2 1

Sample Output 2

0

Although the colors of the first and third slimes are the same, they are not adjacent, so no spell is required.

Sample Input 3

5
1 1 1 1 1

Sample Output 3

2

For example, if we change the colors of the second and fourth slimes from the left to 2, the colors of the slimes will be 1, 2, 1, 2, 1, which satisfy the condition.

Sample Input 4

14
1 2 2 3 3 3 4 4 4 4 1 2 3 4

Sample Output 4

4

Problem Statement

Ringo Mart, a convenience store, sells apple juice.

On the opening day of Ringo Mart, there were A cans of juice in stock in the morning. Snuke buys B cans of juice here every day in the daytime. Then, the manager checks the number of cans of juice remaining in stock every night. If there are C or less cans, D new cans will be added to the stock by the next morning.

Determine if Snuke can buy juice indefinitely, that is, there is always B or more cans of juice in stock when he attempts to buy them. Nobody besides Snuke buy juice at this store.

Note that each test case in this problem consists of T queries.

Constraints

• 1 \leq T \leq 300
• 1 \leq A, B, C, D \leq 10^{18}
• All values in input are integers.

Sample Input 1

14
9 7 5 9
9 7 6 9
14 10 7 12
14 10 8 12
14 10 9 12
14 10 7 11
14 10 8 11
14 10 9 11
9 10 5 10
10 10 5 10
11 10 5 10
16 10 5 10
1000000000000000000 17 14 999999999999999985
1000000000000000000 17 15 999999999999999985

Sample Output 1

No
Yes
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
Yes

In the first query, the number of cans of juice in stock changes as follows: (D represents daytime and N represents night.)

9 →D 2 →N 11 →D 4 →N 13 →D 6 →N 6 →D x

In the second query, the number of cans of juice in stock changes as follows:

9 →D 2 →N 11 →D 4 →N 13 →D 6 →N 15 →D 8 →N 8 →D 1 →N 10 →D 3 →N 12 →D 5 →N 14 →D 7 →N 7 →D 0 →N 9 →D 2 →N 11 →D …

and so on, thus Snuke can buy juice indefinitely.

Sample Input 2

24
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Sample Output 2

No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No

Problem Statement

You are given a string S of length 2N consisting of lowercase English letters.

There are 2^{2N} ways to color each character in S red or blue. Among these ways, how many satisfy the following condition?

• The string obtained by reading the characters painted red from left to right is equal to the string obtained by reading the characters painted blue from right to left.

Constraints

• 1 \leq N \leq 18
• The length of S is 2N.
• S consists of lowercase English letters.

Sample Input 1

4
cabaacba

Sample Output 1

4

There are four ways to paint the string, as follows:

• cabaacba
• cabaacba
• cabaacba
• cabaacba

Sample Input 2

11
mippiisssisssiipsspiim

Sample Output 2

504

Sample Input 3

4
abcdefgh

Sample Output 3

0

Sample Input 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 4

9075135300

The answer may not be representable as a 32-bit integer.

Problem Statement

Let us consider a grid of squares with 10^9 rows and N columns. Let (i, j) be the square at the i-th column (1 \leq i \leq N) from the left and j-th row (1 \leq j \leq 10^9) from the bottom.

Snuke has cut out some part of the grid so that, for each i = 1, 2, ..., N, the bottom-most h_i squares are remaining in the i-th column from the left. Now, he will paint the remaining squares in red and blue. Find the number of the ways to paint the squares so that the following condition is satisfied:

• Every remaining square is painted either red or blue.
• For all 1 \leq i \leq N-1 and 1 \leq j \leq min(h_i, h_{i+1})-1, there are exactly two squares painted red and two squares painted blue among the following four squares: (i, j), (i, j+1), (i+1, j) and (i+1, j+1).

Since the number of ways can be extremely large, print the count modulo 10^9+7.

Constraints

• 1 \leq N \leq 100
• 1 \leq h_i \leq 10^9

Sample Input 1

9
2 3 5 4 1 2 4 2 1

Sample Output 1

12800

One of the ways to paint the squares is shown below:

  #
  ##  #
 ###  #
#### ###
#########

Sample Input 2

2
2 2

Sample Output 2

6

There are six ways to paint the squares, as follows:

## ## ## ## ## ##
## ## ## ## ## ##

Sample Input 3

5
2 1 2 1 2

Sample Output 3

256

Every way to paint the squares satisfies the condition.

Sample Input 4

9
27 18 28 18 28 45 90 45 23

Sample Output 4

844733013

Remember to print the number of ways modulo 10^9 + 7.

Problem Statement

You are given a string S of length 2N, containing N occurrences of a and N occurrences of b.

You will choose some of the characters in S. Here, for each i = 1,2,...,N, it is not allowed to choose exactly one of the following two: the i-th occurrence of a and the i-th occurrence of b. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).

Find the lexicographically largest string that can be obtained in this way.

Constraints

• 1 \leq N \leq 3000
• S is a string of length 2N containing N occurrences of a and N occurrences of b.

Sample Input 1

3
aababb

Sample Output 1

abab

A subsequence of T obtained from taking the first, third, fourth and sixth characters in S, satisfies the condition.

Sample Input 2

3
bbabaa

Sample Output 2

bbabaa

You can choose all the characters.

Sample Input 3

6
bbbaabbabaaa

Sample Output 3

bbbabaaa

Sample Input 4

9
abbbaababaababbaba

Sample Output 4

bbaababababa

Problem Statement

There are N boxes arranged in a row from left to right. The i-th box from the left contains a_i manju (buns stuffed with bean paste). Sugim and Sigma play a game using these boxes. They alternately perform the following operation. Sugim goes first, and the game ends when a total of N operations are performed.

• Choose a box that still does not contain a piece and is adjacent to the box chosen in the other player's last operation, then put a piece in that box. If there are multiple such boxes, any of them can be chosen.
• If there is no box that satisfies the condition above, or this is Sugim's first operation, choose any one box that still does not contain a piece, then put a piece in that box.

At the end of the game, each player can have the manju in the boxes in which he put his pieces. They love manju, and each of them is wise enough to perform the optimal moves in order to have the maximum number of manju at the end of the game.

Find the number of manju that each player will have at the end of the game.

Constraints

• 2 \leq N \leq 300 000
• 1 \leq a_i \leq 1000
• All values in input are integers.

Sample Input 1

5
20 100 10 1 10

Sample Output 1

120 21

If the two performs the optimal moves, the game proceeds as follows:

• First, Sugim has to put his piece in the second box from the left.
• Then, Sigma has to put his piece in the leftmost box.
• Then, Sugim puts his piece in the third or fifth box.
• Then, Sigma puts his piece in the fourth box.
• Finally, Sugim puts his piece in the remaining box.

Sample Input 2

6
4 5 1 1 4 5

Sample Output 2

11 9

Sample Input 3

5
1 10 100 10 1

Sample Output 3

102 20