Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

Takahashi keeps a sleep log. The log is represented as an odd-length sequence A=(A _ 1(=0), A _ 2,\ldots,A _ N), where odd-numbered elements represent times he got up, and even-numbered elements represent times he went to bed. More formally, he had the following sleep sessions after starting the sleep log.

• For every integer i such that 1\leq i\leq\dfrac{N-1}2, he fell asleep exactly A _ {2i} minutes after starting the sleep log and woke up exactly A _ {2i+1} minutes after starting the sleep log.
• He did not fall asleep or wake up at any other time.

Answer the following Q questions. For the i-th question, you are given a pair of integers (l _ i,r _ i) such that 0\leq l _ i\leq r _ i\leq A _ N.

• What is the total number of minutes for which Takahashi was asleep during the r _ i-l _ i minutes from exactly l _ i minutes to r _ i minutes after starting the sleep log?

Constraints

• 3\leq N\lt2\times10^5
• N is odd.
• 0=A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^9
• 1\leq Q\leq2\times10^5
• 0\leq l _ i\leq r _ i\leq A _ N\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

Sample Output 1

480
0
960

Takahashi slept as shown in the following figure.

The answers to each question are as follows.

• Between 480 minutes and 1920 minutes after starting the sleep log, Takahashi slept from 480 minutes to 720 minutes, from 1320 minutes to 1440 minutes, and from 1800 minutes to 1920 minutes in 3 sleep sessions. The total sleep time is 240+120+120=480 minutes.
• Between 720 minutes and 1200 minutes after starting the sleep log, Takahashi did not sleep. The total sleep time is 0 minutes.
• Between 0 minutes and 2160 minutes after starting the sleep log, Takahashi slept from 240 minutes to 720 minutes, from 1320 minutes to 1440 minutes, and from 1800 minutes to 2160 minutes in 3 sleep sessions. The total sleep time is 480+120+360=960 minutes.

Therefore, the three lines of the output should contain 480, 0, and 960.

Sample Input 2

21
0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000
10
77 721
255 541
478 970
369 466
343 541
42 165
16 618
222 592
730 983
338 747

Sample Output 2

296
150
150
49
89
20
279
183
61
177

Problem Statement

You are given integers N,M, a sequence of N integers X=(X_1,X_2,\ldots,X_N), and a sequence of M integers Y=(Y_1,Y_2,\ldots,Y_M).

Determine whether there exists an N row by M column integer matrix A=(A_{i,j}) (1\le i\le N,\ 1\le j\le M) that satisfies all of the following conditions, and if so, find one such matrix.

• 1\le A_{i,j} \le N\times M
• All N\times M elements of A_{i,j} are distinct.
• \displaystyle \max_{1\le j\le M} A_{i,j} = X_i for i=1,2,\ldots,N.
• \displaystyle \max_{1\le i\le N} A_{i,j} = Y_j for j=1,2,\ldots,M.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 10^5
• 1\le N,M
• The sum of N\times M over all test cases is at most 2\times 10^5.
• 1\le X_i,Y_j\le N\times M
• All input values are integers.

Sample Input 1

3
2 3
5 6
5 3 6
3 3
5 4 6
6 2 4
5 4
18 20 19 14 17
18 20 14 15

Sample Output 1

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

Consider the first test case.

In the sample output, all elements of A are between 1 and 6 and are distinct, and furthermore,

• \displaystyle \max_{1\le j\le 3} A_{1,j} =\max \lbrace 5,1,4\rbrace = 5 = X_1
• \displaystyle\max_{1\le j\le 3} A_{2,j} =\max \lbrace 2,3,6\rbrace = 6 = X_2
• \displaystyle\max_{1\le i\le 2} A_{i,1} =\max \lbrace 5,2\rbrace = 5 = Y_1
• \displaystyle\max_{1\le i\le 2} A_{i,2} =\max \lbrace 1,3\rbrace = 3 = Y_2
• \displaystyle\max_{1\le i\le 2} A_{i,3} =\max \lbrace 4,6\rbrace = 6 = Y_3

so all conditions are satisfied.

Other outputs, such as the following, are also accepted.

Yes
5 3 1
4 2 6

Problem Statement

There are N people standing in a line, with person i standing at the i-th position from the front.

Repeat the following operation until there is only one person left in the line:

• Remove the person at the front of the line with a probability of \frac{1}{2}, otherwise move them to the end of the line.

For each person i=1,2,\ldots,N, find the probability that person i is the last person remaining in the line, modulo 998244353. (All choices to remove or not are random and independent.)

Constraints

• 2\leq N\leq 3000
• All input values are integers.

Sample Input 1

2

Sample Output 1

332748118 665496236

Person 1 will be the last person remaining in the line with probability \frac{1}{3}.

Person 2 will be the last person remaining in the line with probability \frac{2}{3}.

Sample Input 2

5

Sample Output 2

235530465 792768557 258531487 238597268 471060930