Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

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 sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).

Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:

• a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).

Find the number, modulo 998244353, of sequences that can be C.

Constraints

• 1 \leq N \leq 3000
• 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
• The sequences A and B are non-decreasing.
• All values in input are integers.

Sample Input 1

2
1 1
2 3

Sample Output 1

5

There are five sequences that can be C, as follows.

• (1, 1)
• (1, 2)
• (1, 3)
• (2, 2)
• (2, 3)

Note that (2, 1) does not satisfy the condition since it is not non-decreasing.

Sample Input 2

3
2 2 2
2 2 2

Sample Output 2

1

There is one sequence that can be C, as follows.

• (2, 2, 2)

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

Sample Output 3

978222082

Be sure to find the count modulo 998244353.

Problem Statement

You are given a rooted tree with N vertices. The root is Vertex 1.
For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i.

For each i = 1, 2, \ldots, N, let S_i denote the set of all vertices in the subtree rooted at Vertex i. (Each vertex is in the subtree rooted at itself, that is, i \in S_i.)

Additionally, for integers l and r, let [l, r] denote the set of all integers between l and r, that is, [l, r] = \lbrace l, l+1, l+2, \ldots, r \rbrace.

Consider a sequence of N pairs of integers \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big) that satisfies the conditions below.

• 1 \leq L_i \leq R_i for every integer i such that 1 \leq i \leq N.
• The following holds for every pair of integers (i, j) such that 1 \leq i, j \leq N.
  • [L_i, R_i] \subseteq [L_j, R_j] if S_i \subseteq S_j
  • [L_i, R_i] \cap [L_j, R_j] = \emptyset if S_i \cap S_j = \emptyset

It can be shown that there is at least one sequence \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big). Among those sequences, print one that minimizes \max \lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace, the maximum integer used. (If there are multiple such sequences, you may print any of them.)

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• All values in input are integers.
• The given graph is a tree.

Sample Input 1

3
2 1
3 1

Sample Output 1

1 2
2 2
1 1

(L_1, R_1) = (1, 2), (L_2, R_2) = (2, 2), (L_3, R_3) = (1, 1) satisfies the conditions.
Indeed, we have [L_2, R_2] \subseteq [L_1, R_1], [L_3, R_3] \subseteq [L_1, R_1], [L_2, R_2] \cap [L_3, R_3] = \emptyset.
Additionally, \max \lbrace L_1, L_2, L_3, R_1, R_2, R_3 \rbrace = 2 is the minimum possible value.

Sample Input 2

5
3 4
5 4
1 2
1 4

Sample Output 2

1 3
3 3
2 2
1 2
1 1

Sample Input 3

5
4 5
3 2
5 2
3 1

Sample Output 3

1 1
1 1
1 1
1 1
1 1

Problem Statement

You are given two sequences of N numbers: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

Takahashi can repeat the following operation any number of times (possibly zero).

Choose three pairwise distinct integers i, j, and k between 1 and N.
Swap the i-th and j-th elements of A, and swap the i-th and k-th elements of B.

If there is a way for Takahashi to repeat the operation to make A and B equal, print Yes; otherwise, print No.
Here, A and B are said to be equal when, for every 1\leq i\leq N, the i-th element of A and that of B are equal.

Constraints

• 3 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• All values in the input are integers.

Sample Input 1

3
1 2 1
1 1 2

Sample Output 1

Yes

Performing the operation once with (i,j,k)=(1,2,3) swaps A_1 and A_2, and swaps B_1 and B_3,
making both A and B equal to (2,1,1). Thus, you should print Yes.

Sample Input 2

3
1 2 2
1 1 2

Sample Output 2

No

There is no way to perform the operation to make A and B equal, so you should print No.

Sample Input 3

5
1 2 3 2 1
3 2 2 1 1

Sample Output 3

Yes

Sample Input 4

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

Sample Output 4

No