Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

• 1 \leq N \leq 2\times 10^5
• The records are consistent. That is:
  • 1\leq A_i \leq 2i-1.
  • A_i are distinct integers.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

• Amoeba 1 is zero generations away from amoeba 1.
• Amoeba 2 is one generation away from amoeba 1.
• Amoeba 3 is one generation away from amoeba 1.
• Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
• Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

You are given positive integers A and B.

You will repeat the following operation until A=B:

• compare A and B to perform one of the following two:
  • if A > B, replace A with A-B;
  • if A < B, replace B with B-A.

How many times will you repeat it until A=B? It is guaranteed that a finite repetition makes A=B.

Constraints

• 1 \le A,B \le 10^{18}
• All values in the input are integers.

Sample Input 1

3 8

Sample Output 1

4

Initially, A=3 and B=8. You repeat the operation as follows:

• A<B, so replace B with B-A=5, making A=3 and B=5.
• A<B, so replace B with B-A=2, making A=3 and B=2.
• A>B, so replace A with A-B=1, making A=1 and B=2.
• A<B, so replace B with B-A=1, making A=1 and B=1.

Thus, you repeat it four times.

Sample Input 2

1234567890 1234567890

Sample Output 2

0

Note that the input may not fit into a 32-bit integer type.

Sample Input 3

1597 987

Sample Output 3

15

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertices U_i and V_i.

There are 2^N ways to paint each vertex red or blue. Find the number, modulo 998244353, of such ways that satisfy all of the following conditions:

• There are exactly K vertices painted red.
• There is an even number of edges connecting vertices painted in different colors.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

4 4 2
1 2
1 3
2 3
3 4

Sample Output 1

2

The following two ways satisfy the conditions.

• Paint Vertices 1 and 2 red and Vertices 3 and 4 blue.
• Paint Vertices 3 and 4 red and Vertices 1 and 2 blue.

In either of the ways above, the 2-nd and 3-rd edges connect vertices painted in different colors.

Sample Input 2

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

Sample Output 2

64

Problem Statement

There is a weighted simple directed graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge has a weight of W_i and extends from vertex U_i to vertex V_i. The weights can be negative, but the graph does not contain negative cycles.

Determine whether there is a walk that visits each vertex at least once. If such a walk exists, find the minimum total weight of the edges traversed. If the same edge is traversed multiple times, the weight of that edge is added for each traversal.

Here, "a walk that visits each vertex at least once" is a sequence of vertices v_1,v_2,\dots,v_k that satisfies both of the following conditions:

• For every i (1\leq i\leq k-1), there is an edge extending from vertex v_i to vertex v_{i+1}.
• For every j\ (1\leq j\leq N), there is i (1\leq i\leq k) such that v_i=j.

Constraints

• 2\leq N \leq 20
• 1\leq M \leq N(N-1)
• 1\leq U_i,V_i \leq N
• U_i \neq V_i
• (U_i,V_i) \neq (U_j,V_j) for i\neq j
• -10^6\leq W_i \leq 10^6
• The given graph does not contain negative cycles.
• All input values are integers.

Sample Input 1

3 4
1 2 5
2 1 -3
2 3 -4
3 1 100

Sample Output 1

-2

By following the vertices in the order 2\rightarrow 1\rightarrow 2\rightarrow 3, you can visit all vertices at least once, and the total weight of the edges traversed is (-3)+5+(-4)=-2. This is the minimum.

Sample Input 2

3 2
1 2 0
2 1 0

Sample Output 2

No

There is no walk that visits all vertices at least once.

Sample Input 3

5 9
1 2 -246288
4 5 -222742
3 1 246288
3 4 947824
5 2 -178721
4 3 -947824
5 4 756570
2 5 707902
5 1 36781

Sample Output 3

-449429