Problem Statement

You are given a string S consisting of digits.

Remove all characters from S except for 2, and then concatenate the remaining characters in their original order to form a new string.

Constraints

• S is a string consisting of digits with length between 1 and 100, inclusive.
• S contains at least one 2.

Sample Input 1

20250222

Sample Output 1

22222

By removing 0, 5, and 0 from 20250222 and then concatenating the remaining characters in their original order, the string 22222 is obtained.

Sample Input 2

2

Sample Output 2

2

Sample Input 3

22222000111222222

Sample Output 3

22222222222

Problem Statement

You are given a sequence of N integers: A=(A _ 1,A _ 2,\ldots,A _ N).

Print all even numbers in A without changing the order.

Constraints

• 1\leq N\leq 100
• 1\leq A _ i\leq 100\ (1\leq i\leq N)
• A contains at least one even number.
• All values in the input are integers.

Sample Input 1

5
1 2 3 5 6

Sample Output 1

2 6

We have A=(1,2,3,5,6). Among them are two even numbers, A _ 2=2 and A _ 5=6, so print 2 and 6 in this order, with a space in between.

Sample Input 2

5
2 2 2 3 3

Sample Output 2

2 2 2

A may contain equal elements.

Sample Input 3

10
22 3 17 8 30 15 12 14 11 17

Sample Output 3

22 8 30 12 14

Problem Statement

N horses numbered 1 to N had a race.

All horses started simultaneously, and horse i took T_i seconds from the start to the goal.

Find the numbers of the horses that finished in 1st, 2nd, and 3rd places. It is guaranteed that all T_i are distinct.

Constraints

• 3\leq N \leq 32
• 1\leq T_i \leq 200
• All T_i are distinct.
• All input values are integers.

Sample Input 1

4
100 110 105 95

Sample Output 1

4 1 3

The horses finished in the order 4, 1, 3, 2. Output the numbers for 1st, 2nd, and 3rd places, which are 4, 1, 3, in this order, separated by spaces.

Sample Input 2

8
72 74 69 70 73 75 71 77

Sample Output 2

3 4 7

Problem Statement

You are given an integer B.
If there exists a positive integer A such that A^A = B, print its value; otherwise, output -1.

Constraints

• 1 \leq B \leq 10^{18}
• B is an integer.

Sample Input 1

27

Sample Output 1

3

3^3 = 27, so print 3.

Sample Input 2

100

Sample Output 2

-1

There is no A such that A^A = B.

Sample Input 3

10000000000

Sample Output 3

10

Problem Statement

A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:

• Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
• Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append X to the end to form T.

Given strings S and T, determine if T is an airport code for S.

Constraints

• S is a string of lowercase English letters with a length between 3 and 10^5, inclusive.
• T is a string of uppercase English letters with a length of 3.

Sample Input 1

narita
NRT

Sample Output 1

Yes

The subsequence nrt of narita, when converted to uppercase, forms the string NRT, which is an airport code for narita.

Sample Input 2

losangeles
LAX

Sample Output 2

Yes

The subsequence la of losangeles, when converted to uppercase and appended with X, forms the string LAX, which is an airport code for losangeles.

Sample Input 3

snuke
RNG

Sample Output 3

No

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le W \le 3 \times 10^8
• 1 \le A_i \le 10^9
• 1 \le B_i \le 1000

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

Problem Statement

This problem is a subproblem of Problem G.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
  1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
  2. Define an integer x as follows:
     • If S_i = 0 and S_{i+1} = 0, let x = 1.
     • If S_i = 0 and S_{i+1} = 1, let x = 0.
     • If S_i = 1 and S_{i+1} = 0, let x = 0.
     • If S_i = 1 and S_{i+1} = 1, let x = 1.
  3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
     For example, if S= 10101 and you choose i=2, the string after the operation is 1001.

You are given a string T of length N consisting of 0 and 1.
Find the number of beautiful strings that are substrings of T. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

3
110

Sample Output 1

3

The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1. The beautiful strings that are substrings of T are the following three strings:

• The string 1 obtained by taking the 1st character of T.
• The string 1 obtained by taking the 2nd character of T.
• The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

4

Sample Input 3

30
011011100101110111100010011010

Sample Output 3

225

Problem Statement

You are given a permutation P=(P_0,P_1,\ldots,P_{2^{N}-1}) of (1,2,3,\ldots,2^{N}).

You can perform the following operation any number of times (possibly zero):

• Choose non-negative integers a,b satisfying 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N}, and reverse P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}. Here, reversing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} means simultaneously replacing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} with P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}.

Find the lexicographically smallest permutation P that can be obtained by repeating the operation.

You are given T test cases, so find the answer for each.

Constraints

• 1 \leq T \leq 10^{5}
• 1 \leq N \leq 18
• P is a permutation of (1,2,3,\ldots,2^{N}).
• For each input file, the sum of 2^N over all test cases is at most 3 \times 10^{5}.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

In the first test case, when no operation is performed on P, P=(1,2). This is the lexicographically smallest permutation. Thus, the answer is (1,2).

In the second test case, when we perform the operation with a=1,b=1, P becomes (1,3,2,4). No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,3,2,4). Thus, the answer is (1,3,2,4).

In the third test case, by performing operations in the following order, we can obtain P=(1,4,2,3):

• Perform the operation with a=0,b=1. P becomes (3,2,4,1).
• Perform the operation with a=0,b=2. P becomes (1,4,2,3).

No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,4,2,3). Thus, the answer is (1,4,2,3).

Problem Statement

In Takahashi's chest of drawers, there are socks of N colors, with A_i socks of color i.

Initially, Takahashi has one sock of color C outside the chest of drawers, separate from these socks, and repeats the following operation until the termination condition is met:

• Uniformly randomly choose and draw 1 sock from the chest of drawers. Then, if the two socks he has outside the chest of drawers are the same color, terminate the operation. Otherwise, choose one of the socks and put it back in the chest of drawers. He always chooses the sock to put back so as to minimize the expected number of future sock draws.

Find the expected number, modulo 998244353, of sock draws until the operation terminates.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq C \leq N
• 1 \leq A_i \leq 3000
• All input values are integers.

Sample Input 1

3 2
3 1 2

Sample Output 1

249561092

The expected number of sock draws is \frac{15}{4}.

Sample Input 2

8 4
4 1 6 2 5 1 7 3

Sample Output 2

393623786