Problem Statement

You are given an integer N between 1 and 9, inclusive, as input.

Concatenate N copies of the digit N and print the resulting string.

Constraints

• N is an integer between 1 and 9, inclusive.

Sample Input 1

3

Sample Output 1

333

Concatenate three copies of the digit 3 to yield the string 333.

Sample Input 2

9

Sample Output 2

999999999

Problem Statement

You are given two integers A and B, each between 0 and 9, inclusive.

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Constraints

• 0 \leq A \leq 9
• 0 \leq B \leq 9
• A + B \leq 9
• A and B are integers.

Sample Input 1

2 5

Sample Output 1

2

When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.

Sample Input 2

0 0

Sample Output 2

9

Sample Input 3

7 1

Sample Output 3

4

Problem Statement

You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.

Constraints

• S consists of lowercase English letters.
• 1 \le |S| \le 10^5 (|S| is the length of S.)
• L and R are integers.
• 1 \le L \le R \le |S|

Sample Input 1

3 7
abcdefgh

Sample Output 1

abgfedch

After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.

Sample Input 2

1 7
reviver

Sample Output 2

reviver

The operation may result in the same string as the original.

Sample Input 3

4 13
merrychristmas

Sample Output 3

meramtsirhcyrs

Problem Statement

You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

• 1 k x : set the value A _ k to x.
• 2 k : print the value A _ k.

Constraints

• 1 \leq N \leq 10 ^ 5
• 1 \leq Q \leq 10 ^ 5
• 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
• 1\leq k\leq N for all queries.
• 0\leq x\leq 10 ^ 9 for all queries of the first kind.
• There is at least one query of the second kind.
• All values in the input are integers.

Sample Input 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

Sample Output 1

3
5
0
8
1

Initially, A=(1,3,5).

• For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
• For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
• The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
• For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
• The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
• For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
• For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

2
16
0
0
16
100

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

478
317
838
838
176
595
468

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

Sample Input 3

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

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

Problem Statement

There is a 3\times3 grid with numbers between 1 and 9, inclusive, written in each square. The square at the i-th row from the top and j-th column from the left (1\leq i\leq3,1\leq j\leq3) contains the number c _ {i,j}.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that c _ {i,j} satisfies all of the following conditions.

• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

Constraints

• c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Sample Input 1

3 1 9
2 5 6
2 7 1

Sample Output 1

0.666666666666666666666666666667

For example, if Takahashi sees c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 in this order, he will get disappointed.

On the other hand, if Takahashi sees c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} in this order, he will see all numbers without getting disappointed.

The probability that Takahashi sees all the numbers without getting disappointed is \dfrac 23. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}, so outputs such as 0.666666657 and 0.666666676 would also be accepted.

Sample Input 2

7 7 6
8 6 8
7 7 6

Sample Output 2

0.004982363315696649029982363316

Sample Input 3

3 6 7
1 9 7
5 7 5

Sample Output 3

0.4

Problem Statement

There are N+Q points A_1,\dots,A_N,B_1,\dots,B_Q on a number line, where point A_i has a coordinate a_i and point B_j has a coordinate b_j.

For each j=1,2,\dots,Q, answer the following question:

• Let X be the point among A_1,A_2,\dots,A_N that is the k_j-th closest to point B_j. Find the distance between points X and B_j. More formally, let d_i be the distance between points A_i and B_j. Sort (d_1,d_2,\dots,d_N) in ascending order to get the sequence (d_1',d_2',\dots,d_N'). Find d_{k_j}'.

Constraints

• 1 \leq N, Q \leq 10^5
• -10^8 \leq a_i, b_j \leq 10^8
• 1 \leq k_j \leq N
• All input values are integers.

Sample Input 1

4 3
-3 -1 5 6
-2 3
2 1
10 4

Sample Output 1

7
3
13

Let us explain the first query.

The distances from points A_1, A_2, A_3, A_4 to point B_1 are 1, 1, 7, 8, respectively, so the 3rd closest to point B_1 is point A_3. Therefore, print the distance between point A_3 and point B_1, which is 7.

Sample Input 2

2 2
0 0
0 1
0 2

Sample Output 2

0
0

There may be multiple points with the same coordinates.

Sample Input 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

Sample Output 3

11
66
59
54
88

Problem Statement

We have a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W).

Each square is one of the following: the initial point, a road, and an obstacle.
A square (i, j) is represented by a character C_{i, j}. The square is the initial point if C_{i, j} = S, a road if C_{i, j} = ., and an obstacle if C_{i, j} = #. There is exactly one initial point.

Determine whether there is a path of length 4 or greater that starts at the initial point, repeats moving vertically or horizontally to an adjacent square, and returns to the initial point without going through an obstacle or visiting the same square multiple times except at the beginning and the end.
More formally, determine whether there are an integer n and a sequence of squares (x_0, y_0), (x_1, y_1), \dots, (x_n, y_n) that satisfy the following conditions.

• n \geq 4.
• C_{x_0, y_0} = C_{x_n, y_n} = S.
• If 1 \leq i \leq n - 1, then C_{x_i, y_i} = ..
• If 1 \leq i \lt j \leq n - 1, then (x_i, y_i) \neq (x_j, y_j).
• If 0 \leq i \leq n - 1, then square (x_i, y_i) and square (x_{i+1}, y_{i+1}) are vertically or horizontally adjacent to each other.

Constraints

• 4 \leq H \times W \leq 10^6
• H and W are integers greater than or equal to 2.
• C_{i, j} is S, ., or #.
• There is exactly one (i, j) such that C_{i, j} = S.

Sample Input 1

4 4
....
#.#.
.S..
.##.

Sample Output 1

Yes

The path (3, 2) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 2) satisfies the conditions.

Sample Input 2

2 2
S.
.#

Sample Output 2

No

Sample Input 3

5 7
.#...#.
..#.#..
...S...
..#.#..
.#...#.

Sample Output 3

No

Problem Statement

Consider a binary tree with N vertices numbered 1, 2, \ldots, N. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.

Determine whether there exists a binary tree rooted at Vertex 1 satisfying the conditions below, and present such a tree if it exists.

• The depth-first traversal of the tree in pre-order is (P_1, P_2, \ldots, P_N).
• The depth-first traversal of the tree in in-order is (I_1, I_2, \ldots, I_N).

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.
• (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
• (I_1, I_2, \ldots, I_N) is a permutation of (1, 2, \ldots, N).

Sample Input 1

6
1 3 5 6 4 2
3 5 1 4 6 2

Sample Output 1

3 6
0 0
0 5
0 0
0 0
4 2

The binary tree rooted at Vertex 1 shown in the following image satisfies the conditions.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

No binary tree rooted at Vertex 1 satisfies the conditions, so -1 should be printed.