Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

1. If the sequence has one or fewer balls, end the operation.
2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^2.
• After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
• After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
  • When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
  • The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
  • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
• After the fourth operation, the sequence has one ball, of size 2^4.
• After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
• After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
• After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^0.
• After the second operation, the sequence has one ball, of size 2^1.
• After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
• After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
• After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9
• 0 \leq Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All X_i and Y_i are integers.
• S is a string of length N consisting of L and R.

Sample Input 1

3
2 3
1 1
4 1
RRL

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

2
1 1
2 1
RR

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Sample Output 3

Yes

Problem Statement

You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.

When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.

• The endpoints of the chosen edges are pairwise distinct.

Constraints

• 2\leq N\leq 16
• 1\leq D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

4
1 5 4
7 8
6

Sample Output 1

13

If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.

It can be shown that this is the maximum achievable value.

Sample Input 2

3
1 2
3

Sample Output 2

3

N can be odd.

Sample Input 3

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

Sample Output 3

75

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects vertices A_i and B_i.

You are also given a sequence of positive integers C = (C_1, C_2, \ldots ,C_N) of length N. Let d(a, b) be the number of edges between vertices a and b, and for x = 1, 2, \ldots, N, let \displaystyle f(x) = \sum_{i=1}^{N} (C_i \times d(x, i)). Find \displaystyle \min_{1 \leq v \leq N} f(v).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is a tree.
• 1 \leq C_i \leq 10^9

Sample Input 1

4
1 2
1 3
2 4
1 1 1 2

Sample Output 1

5

For example, consider calculating f(1). We have d(1, 1) = 0, d(1, 2) = 1, d(1, 3) = 1, d(1, 4) = 2.
Thus, f(1) = 0 \times 1 + 1 \times 1 + 1 \times 1 + 2 \times 2 = 6.

Similarly, f(2) = 5, f(3) = 9, f(4) = 6. Since f(2) is the minimum, print 5.

Sample Input 2

2
2 1
1 1000000000

Sample Output 2

1

f(2) = 1, which is the minimum.

Sample Input 3

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

Sample Output 3

56

Problem Statement

For a permutation P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N), let us define the score S(P) of P as follows.

• There are N people, numbered 1,2,\dots,N. Additionally, Snuke is there. Initially, Person i (1 \leq i \leq N) has Ball i.
  Each time Snuke screams, every Person i such that i \neq p_i gives their ball to Person p_i simultaneously.
  If, after screaming at least once, every Person i has Ball i, Snuke stops screaming.
  The score is the number of times Snuke screams until he stops. Here, it is guaranteed that the score will be a finite value.

There are N! permutations P of (1,2, \dots, N). Find the sum, modulo 998244353, of the scores of those permutations, each raised to the K-th power.

• Formally, let S_N be the set of the permutations of (1,2, \dots, N). Compute the following: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.

Constraints

• 2 \leq N \leq 50
• 1 \leq K \leq 10^4
• All values in input are integers.

Sample Input 1

2 2

Sample Output 1

5

When N = 2, there are two possible permutations P: (1,2),(2,1).

The score of the permutation (1,2) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 1.

The score of the permutation (2,1) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 2, and Person 2 has Ball 1.
  After Snuke's second scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 2.

Therefore, the answer in this case is 1^2 + 2^2 = 5.

Sample Input 2

3 3

Sample Output 2

79

All permutations and their scores are listed below.

• (1,2,3): The score is 1.
• (1,3,2): The score is 2.
• (2,1,3): The score is 2.
• (2,3,1): The score is 3.
• (3,1,2): The score is 3.
• (3,2,1): The score is 2.

Thus, we should print 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.

Sample Input 3

50 10000

Sample Output 3

77436607