Problem Statement

You, the game master, and N players play a Hat Guessing Game. The players line up behind one another, numbered 1 to N from front to back.

Each player wears a red or blue hat. The colors of the hats are represented by a string S: player i wears a red hat if the i-th character of S is R, and a blue hat if it is B. You know the string S, but the players do not. Each player can only see the colors of hats of the players in front of them (namely, the players with smaller player numbers). Particularly, they cannot see the color of their own hat.

The game goes as follows.

First, you count the numbers of players with red hats and those with blue hats, and tell them to all players. Then, you repeat the following sequence of events (called a round) 10^{100} times.

• You ask each player, "Have you found out the color of your own hat?" Each player will honestly answer Yes or No without being heard by other players.
• After asking all players, you announce all players who have answered Yes. All players can hear this announcement. Note that you just announce the player numbers and not the colors of their hats.

All players are extremely clever and know that the other players are also clever. They start answering Yes in the first round when the color of their hat is determined. Additionally, they know that the other players also take this strategy, and use this knowledge to infer the color of their hat.

For each player, find whether they will have found out the color of their own hat after all rounds.

Process T test cases for each input file.

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100
• S is a string of length N consisting of R and B.
• All input values are integers.

Sample Input 1

7
3
RBR
4
BRBR
5
BBBBB
5
BBBRR
20
BRBBRRRRBRRBRBBBRRBR
50
RRBRRRBBBRRRBBBRRBRRBBRBRRBBRRRRRBBBBBRRRBRBRRBRRR
100
BRBRBRBBRRRBBRRBRBBRBBBRBBRBBRRRRBBRRBBBBBBBBBBBBRRBBRBBRBBBBRRRRRRRRRBRBBRBBBBRBBBRBRRBRRBBRBBBBBBB

Sample Output 1

101
0101
11111
10111
10111111010101011101
11111010111010111010101010101011111111111011111111
1111111001111001111111010001111101011111111011011011111111111111111101111111111111010101011111111111

In the first case, the game goes as follows.

• First, you announce to all players, "Two players wear red hats, and one wears a blue hat."
• Round 1:
  • Player 1: answers No to your question.
  • Player 2: answers No to your question.
  • Player 3: Because the hats of the players in front of him are red and blue, he realizes his hat is red. He answers Yes to your question.
  • You announce, "Player 3 answered Yes."
• Round 2:
  • Player 1: Assume his hat is blue. Then, player 2 should have noticed in round 1 that his hat is red. However, player 2 actually answered No. Thus, he realizes his hat is red, and answers Yes to your question.
  • Player 2: answers No to your question.
  • Player 3: answers Yes to your question.
  • You announce, "Players 1 and 3 answered Yes."
• Round 3:
  • Player 1: answers Yes to your question.
  • Player 2: answers No to your question.
  • Player 3: answers Yes to your question.
  • You announce, "Players 1 and 3 answered Yes."
• \vdots

After all rounds, players 1 and 3 know the colors of their hats. However, player 2 does not. More specifically, player 2 can deny neither the possibility that S=RRB nor the possibility that S=RBR with just the information he has, so he cannot determine the color of his hat. Thus, the string 101 should be printed as the answer.

Problem Statement

You are given integers N and K, and a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).

You can perform the following operation any number of times, possibly zero.

• Choose an integer i (1 \leq i \leq N-K+1). Swap the values of the two greatest elements among P_i,P_{i+1},\cdots,P_{i+K-1}.

Find the number, modulo 998244353, of permutations that P can be after your operations.

Constraints

• 2 \leq K \leq N \leq 250000
• (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
• All input values are integers.

Sample Input 1

3 3
2 3 1

Sample Output 1

2

In this case, the operation can only be performed with i=1.

After one operation, the two greatest elements among P_1,P_2,P_3, which are P_2=3 and P_1=2, have their values swapped, and you have P=(3,2,1). After one more operation, you have P=(2,3,1).

Thus, there are two permutations, P=(2,3,1),(3,2,1), that P can be after your operations.

Sample Input 2

3 2
1 3 2

Sample Output 2

6

Sample Input 3

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

Sample Output 3

144

Sample Input 4

20 5
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

Sample Output 4

1451520

Problem Statement

There are N gems numbered 1 to N. Gem i has a color C_i and a value V_i. Here, colors are represented as integers from 1 through N.

A pair of two gems (i,j) is said to be a good pair if (and only if) they satisfy the following conditions:

• C_i \neq C_j,
• V_i + V_j \leq L.

You will make some number of good pairs from the N gems. A gem must not belong to multiple pairs, but it is fine if some gems belong to no pairs.

Find the maximum possible total value of all gems in your pairs.

Constraints

• 1 \leq N \leq 250000
• 1 \leq L \leq 10^9
• 1 \leq C_i \leq N
• 0 \leq V_i \leq L
• All input values are integers.

Sample Input 1

4 5
1 2
1 3
2 1
2 4

Sample Output 1

4

The pair (1,2) is not good because the first condition is not satisfied.

The pair (1,4) is not good because the second condition is not satisfied.

In this case, it is optimal to make the pair (2,3).

Sample Input 2

5 10
3 8
4 2
1 5
1 3
1 2

Sample Output 2

17

In this case, it is optimal to make the pairs (1,5) and (2,3).

Sample Input 3

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

Sample Output 3

34

Sample Input 4

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

Sample Output 4

4704511147

Problem Statement

You are given a sequence of positive integers A_1,A_2,\cdots,A_N. Let S=N+\sum_{1 \leq i \leq N}A_i.

Cat Snuke has S cards. Each card has an integer written on it. The integers on the cards are A_1,A_2,\cdots,A_N,-1,\cdots,-1. Particularly, there are \sum_{1 \leq i \leq N}A_i cards with -1.

Snuke is now standing at the coordinate 0 on a number line. He will perform the following operation S times.

• Let x be the current coordinate of Snuke. Choose and discard one of the cards he has. Let v be the number on the discarded card, and jump to the coordinate x+v. If he has jumped to the coordinate 0, earn one coin.

For each k=1,2,\cdots,N, find the number, modulo 998244353, of sequences of moves for Snuke such that he earns exactly k coins.

Note that you should count sequences of moves. Namely, if two cards have the same number, discarding one of them is not distinguished from discarding the other.

Constraints

• 1 \leq N \leq 5000
• 1 \leq A_i \leq 5000
• All input values are integers.

Sample Input 1

2
1 1

Sample Output 1

2
4

One possible sequence of moves is (-1,+1,+1,-1). Here, Snuke changes his coordinate as 0 \to -1 \to 0 \to 1 \to 0 and earns two coins.

Here are all possible sequences of moves and the number of coins that will be earned.

• (-1,-1,+1,+1): one coin
• (-1,+1,-1,+1): two coins
• (-1,+1,+1,-1): two coins
• (+1,-1,-1,+1): two coins
• (+1,-1,+1,-1): two coins
• (+1,+1,-1,-1): one coin

Sample Input 2

3
1 2 3

Sample Output 2

140
220
144

Sample Input 3

20
16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5

Sample Output 3

507808441
401798892
110460932
680359166
737048635
442374434
737773176
980506765
473506608
693729211
532774651
621434128
4273369
839437048
585784927
590354055
969740008
825216624
442091194
660636013

Problem Statement

You are given N non-negative integers A_1,A_2,\cdots,A_N. For each k=1,2,\cdots,N, solve the following problem.

Alice and Bob play the following game.

• Alice chooses k numbers from A_1,A_2,\cdots,A_N. Let x_1,x_2,\cdots,x_k be the chosen numbers (in arbitrary order).

• Bob makes a sequence of 2k non-negative integers y=(y_1,y_2,\cdots,y_{2k}), which must satisfy the following conditions.

  • 0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}.
  • Let z_i=y_{2i-1} \oplus y_{2i}. Then, \{z_1,z_2,\cdots,z_k\} coincides with \{x_1,x_2,\cdots,x_k\} as a multiset.

Here, \oplus denotes bitwise \mathrm{XOR}.

Let the score of the game be the value of y_{2k}. Bob plays to minimize the score. With this in mind, Alice plays to maximize the score. What will the score be?

Constraints

• 1 \leq N \leq 250000
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3
1 2 3

Sample Output 1

2
6
6

Consider the case k=1.

• If Alice chooses x_1=1: Bob makes y=(0,1), for the score of 1.
• If Alice chooses x_1=2: Bob makes y=(0,2), for the score of 2.
• If Alice chooses x_1=3: Bob makes y=(1,2), for the score of 2.

Thus, Alice will choose x_1=2 or x_1=3, for the score of 2.

Consider the case k=2. If Alice chooses (x_1,x_2)=(2,3) and Bob makes y=(1,2,4,6), the score will be 6. This is an example of optimal play for both players, and the answer is 6.

Consider the case k=3. If Alice chooses (x_1,x_2,x_3)=(1,2,3) and Bob makes y=(0,1,1,2,4,6), the score will be 6. This is an example of optimal play for both players, and the answer is 6.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

1
3
5
7
9

Sample Input 3

5
1 2 4 8 16

Sample Output 3

16
24
28
30
31

Sample Input 4

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

Sample Output 4

536870912
1610612736
2684354560
3758096384
4831838208
4831838208
4831838208
4831838208
4831838208
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664