Problem Statement

Takahashi, Nakahashi and Hikuhashi have integers A, B and C, respectively. After repeating the following operation K times, find the integer Takahashi will get minus the integer Nakahashi will get:

• Each of them simultaneously calculate the sum of the integers that the other two people have, then replace his own integer with the result.

However, if the absolute value of the answer exceeds 10^{18}, print Unfair instead.

Constraints

• 1 \leq A,B,C \leq 10^9
• 0 \leq K \leq 10^{18}
• All values in input are integers.

Sample Input 1

1 2 3 1

Sample Output 1

1

After one operation, Takahashi, Nakahashi and Hikuhashi have 5, 4 and 3, respectively. We should print 5-4=1.

Sample Input 2

2 3 2 0

Sample Output 2

-1

Sample Input 3

1000000000 1000000000 1000000000 1000000000000000000

Sample Output 3

0

Problem Statement

You are given a sequence (P_1,P_2,...,P_N) which is a permutation of the integers from 1 through N. You would like to sort this sequence in ascending order by repeating the following operation:

• Choose an element in the sequence and move it to the beginning or the end of the sequence.

Find the minimum number of operations required. It can be proved that it is actually possible to sort the sequence using this operation.

Constraints

• 1 \leq N \leq 2\times 10^5
• (P_1,P_2,...,P_N) is a permutation of (1,2,...,N).
• All values in input are integers.

Sample Input 1

4
1
3
2
4

Sample Output 1

2

For example, the sequence can be sorted in ascending order as follows:

• Move 2 to the beginning. The sequence is now (2,1,3,4).
• Move 1 to the beginning. The sequence is now (1,2,3,4).

Sample Input 2

6
3
2
5
1
4
6

Sample Output 2

4

Sample Input 3

8
6
3
1
2
7
4
8
5

Sample Output 3

5

Problem Statement

There is a sequence X of length N, where every element is initially 0. Let X_i denote the i-th element of X.

You are given a sequence A of length N. The i-th element of A is A_i. Determine if we can make X equal to A by repeating the operation below. If we can, find the minimum number of operations required.

• Choose an integer i such that 1\leq i\leq N-1. Replace the value of X_{i+1} with the value of X_i plus 1.

Constraints

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

Sample Input 1

4
0
1
1
2

Sample Output 1

3

We can make X equal to A as follows:

• Choose i=2. X becomes (0,0,1,0).
• Choose i=1. X becomes (0,1,1,0).
• Choose i=3. X becomes (0,1,1,2).

Sample Input 2

3
1
2
1

Sample Output 2

-1

Sample Input 3

9
0
1
1
0
1
2
2
1
2

Sample Output 3

8

Problem Statement

Coloring of the vertices of a tree G is called a good coloring when, for every pair of two vertices u and v painted in the same color, picking u as the root and picking v as the root would result in isomorphic rooted trees.

Also, the colorfulness of G is defined as the minimum possible number of different colors used in a good coloring of G.

You are given a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i. We will construct a new tree T by repeating the following operation on this tree some number of times:

• Add a new vertex to the tree by connecting it to one of the vertices in the current tree with an edge.

Find the minimum possible colorfulness of T. Additionally, print the minimum number of leaves (vertices with degree 1) in a tree T that achieves the minimum colorfulness.

Notes

The phrase "picking u as the root and picking v as the root would result in isomorphic rooted trees" for a tree G means that there exists a bijective function f_{uv} from the vertex set of G to itself such that both of the following conditions are met:

• f_{uv}(u)=v
• For every pair of two vertices (a,b), edge (a,b) exists if and only if edge (f_{uv}(a),f_{uv}(b)) exists.

Constraints

• 2 \leq N \leq 100
• 1 \leq a_i,b_i \leq N(1\leq i\leq N-1)
• The given graph is a tree.

Sample Input 1

5
1 2
2 3
3 4
3 5

Sample Output 1

2 4

If we connect a new vertex 6 to vertex 2, painting the vertices (1,4,5,6) red and painting the vertices (2,3) blue is a good coloring. Since painting all the vertices in a single color is not a good coloring, we can see that the colorfulness of this tree is 2. This is actually the optimal solution. There are four leaves, so we should print 2 and 4.

Sample Input 2

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

Sample Output 2

3 4

Sample Input 3

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

Sample Output 3

4 6

Sample Input 4

13
5 6
6 4
2 8
4 7
8 9
3 2
10 4
11 10
2 4
13 10
1 8
12 1

Sample Output 4

4 12

Problem Statement

Find the number of the possible tuples of sequences (A_0,A_1,...,A_N) that satisfy all of the following conditions, modulo M:

• For every i (0\leq i\leq N), A_i is a sequence of length i consisting of integers between 1 and K (inclusive);
• For every i (1\leq i\leq N), A_{i-1} is a subsequence of A_i, that is, there exists 1\leq x_i\leq i such that the removal of the x_i-th element of A_i would result in a sequence equal to A_{i-1};
• For every i (1\leq i\leq N), A_i is lexicographically larger than A_{i-1}.

Constraints

• 1 \leq N,K \leq 300
• 2 \leq M \leq 10^9
• N, K and M are integers.

Sample Input 1

2 2 100

Sample Output 1

5

Five tuples below satisfy the conditions:

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

Sample Input 2

4 3 999999999

Sample Output 2

358

Sample Input 3

150 150 998244353

Sample Output 3

186248260

Problem Statement

You are given a set S of strings consisting of 0 and 1, and an integer K.

Find the longest string that is a subsequence of K or more different strings in S. If there are multiple strings that satisfy this condition, find the lexicographically smallest such string.

Here, S is given in the format below:

• The data directly given to you is an integer N, and N+1 strings X_0,X_1,...,X_N. For every i (0\leq i\leq N), the length of X_i is 2^i.
• For every pair of two integers (i,j) (0\leq i\leq N,0\leq j\leq 2^i-1), the j-th character of X_i is 1 if and only if the binary representation of j with i digits (possibly with leading zeros) belongs to S. Here, the first and last characters in X_i are called the 0-th and (2^i-1)-th characters, respectively.
• S does not contain a string with length N+1 or more.

Here, a string A is a subsequence of another string B when there exists a sequence of integers t_1 < ... < t_{|A|} such that, for every i (1\leq i\leq |A|), the i-th character of A and the t_i-th character of B is equal.

Constraints

• 0 \leq N \leq 20
• X_i(0\leq i\leq N) is a string of length 2^i consisting of 0 and 1.
• 1 \leq K \leq |S|
• K is an integer.

Sample Input 1

3 4
1
01
1011
01001110

Sample Output 1

10

The following strings belong to S: the empty string, 1, 00, 10, 11, 001, 100, 101 and 110. The lexicographically smallest string among the longest strings that are subsequences of four or more of them is 10.

Sample Input 2

4 6
1
01
1011
10111010
1101110011111101

Sample Output 2

100

Sample Input 3

2 5
0
11
1111

Sample Output 3

The answer is the empty string.