Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• S consists of lowercase English letters.
• T is obtained by inserting a lowercase English letter into S.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

• N is an integer.
• 1 \leq N \leq 16

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

There is a grid with N \times N squares. We denote by (i, j) the square at the i-th row from the top and j-th column from the left.

Initially, a piece is placed on (1, 1). You may repeat the following operation any number of times:

• Let (i, j) be the square the piece is currently on. Move the piece to the square whose distance from (i, j) is exactly \sqrt{M}.

Here, we define the distance between square (i, j) and square (k, l) as \sqrt{(i-k)^2+(j-l)^2}.

For all squares (i, j), determine if the piece can reach (i, j). If it can, find the minimum number of operations required to do so.

Constraints

• 1 \le N \le 400
• 1 \le M \le 10^6
• All values in the input are integers.

Sample Input 1

3 1

Sample Output 1

0 1 2
1 2 3
2 3 4

You can move the piece to four adjacent squares.

For example, we can move the piece to (2,2) with two operations as follows.

• The piece is now on (1,1). The distance between (1,1) and (1,2) is exactly \sqrt{1}, so move the piece to (1,2).
• The piece is now on (1,2). The distance between (1,2) and (2,2) is exactly \sqrt{1}, so move the piece to (2,2).

Sample Input 2

10 5

Sample Output 2

0 3 2 3 2 3 4 5 4 5
3 4 1 2 3 4 3 4 5 6
2 1 4 3 2 3 4 5 4 5
3 2 3 2 3 4 3 4 5 6
2 3 2 3 4 3 4 5 4 5
3 4 3 4 3 4 5 4 5 6
4 3 4 3 4 5 4 5 6 5
5 4 5 4 5 4 5 6 5 6
4 5 4 5 4 5 6 5 6 7
5 6 5 6 5 6 5 6 7 6

Problem Statement

A graph with (k+1) vertices and k edges is called a level-k\ (k\geq 2) star if and only if:

• it has a vertex that is connected to each of the other k vertices with an edge, and there are no other edges.

At first, Takahashi had a graph consisting of stars. He repeated the following operation until every pair of vertices in the graph was connected:

• choose two vertices in the graph. Here, the vertices must be disconnected, and their degrees must be both 1. Add an edge that connects the chosen two vertices.

He then arbitrarily assigned an integer from 1 through N to each of the vertices in the graph after the procedure. The resulting graph is a tree; we call it T. T has (N-1) edges, the i-th of which connects u_i and v_i.

Takahashi has now forgotten the number and levels of the stars that he initially had. Find them, given T.

Constraints

• 3\leq N\leq 2\times 10^5
• 1\leq u_i, v_i\leq N
• The given graph is an N-vertex tree obtained by the procedure in the problem statement.
• All values in the input are integers.

Sample Input 1

6
1 2
2 3
3 4
4 5
5 6

Sample Output 1

2 2

Two level-2 stars yield T, as the following figure shows:

Sample Input 2

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

Sample Output 2

2 2 2

Sample Input 3

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

Sample Output 3

2 3 4 7

Problem Statement

On a circle, 2N points are placed at equal intervals and numbered 1,2,\dots,2N in clockwise order starting from an arbitrary point.

There are M line segments numbered 1,2,\dots,M connecting these points. Segment i connects points A_i and B_i. Here, A_i and B_i are distinct even numbers. It is guaranteed that no two of these segments share a point.

Process Q queries. The j‑th query is as follows:

• You are given two distinct odd numbers C_j and D_j. Among the M segments 1,2,\dots,M, find how many share a point with the segment connecting points C_j and D_j.

Constraints

• 2 \le N \le 10^6
• 1\leq M \leq \min\left(\lfloor\frac{N}{2}\rfloor, 2\times 10^5\right)
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i < B_i \le 2N
• 1 \le C_j < D_j \le 2N
• A_i and B_i are even.
• C_j and D_j are odd.
• For any i_1 and i_2 (i_1 \neq i_2), segments i_1 and i_2 do not share a point.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
2
0

The figure above illustrates Sample Input 1. Black dots are the 2N\ (=8) points, blue solid lines are the initial M\ (=2) segments, and red dashed lines are the Q\ (=3) query segments.

• For the first query, the segment connecting points 1 and 3 intersects one initial segment: segment 1.
• For the second query, the segment connecting points 3 and 7 intersects two initial segments: segments 1 and 2.
• For the third query, the segment connecting points 1 and 5 intersects zero initial segments.

Sample Input 2

20 7
24 34
26 28
18 38
2 14
8 12
30 32
20 22
10
7 29
31 39
9 21
19 29
15 21
11 39
17 21
15 31
5 25
25 31

Sample Output 2

3
3
4
1
2
2
2
3
3
1