Problem Statement

Print the L-th through R-th characters of the string atcoder.

Constraints

• L and R are integers.
• 1 \le L \le R \le 7

Sample Input 1

3 6

Sample Output 1

code

The 3-rd through 6-th characters of atcoder are code.

Sample Input 2

4 4

Sample Output 2

o

Sample Input 3

1 7

Sample Output 3

atcoder

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

Takahashi and Aoki will play the following game against each other.

Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.

In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.

Constraints

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

Input and Output

This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.

First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.

1. Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
2. The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.

Notes

• After each output, you must flush Standard Output. Otherwise, you may get TLE.
• After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
• If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.

Sample Input and Output

Problem Statement

We have an undirected graph with (N_1+N_2) vertices and M edges. For i=1,2,\ldots,M, the i-th edge connects vertex a_i and vertex b_i.
The following properties are guaranteed:

• Vertex u and vertex v are connected, for all integers u and v with 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected, for all integers u and v with N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.

Consider performing the following operation exactly once:

• choose an integer u with 1 \leq u \leq N_1 and an integer v with N_1+1 \leq v \leq N_1+N_2, and add an edge connecting vertex u and vertex v.

We can show that vertex 1 and vertex (N_1+N_2) are always connected in the resulting graph; so let d be the minimum length (number of edges) of a path between vertex 1 and vertex (N_1+N_2).

Find the maximum possible d resulting from adding an appropriate edge to add.

Constraints

• 1 \leq N_1,N_2 \leq 1.5 \times 10^5
• 0 \leq M \leq 3 \times 10^5
• 1 \leq a_i \leq b_i \leq N_1+N_2
• (a_i,b_i) \neq (a_j,b_j) if i \neq j.
• Vertex u and vertex v are connected for all integers u and v such that 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected for all integers u and v such that N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If we set u=2 and v=5, the operation yields d=5, which is the maximum possible.

Sample Input 2

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

Sample Output 2

4

Problem Statement

You are given an undirected graph G with N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertices u_i and v_i.

A graph with N vertices is called good if the following condition holds for all i = 1, 2, \ldots, K:

• there is no path connecting vertices x_i and y_i in G.

The given graph G is good.

You are given Q independent questions. Answer all of them. For i = 1, 2, \ldots, Q, the i-th question is as follows.

• Is the graph G^{(i)} obtained by adding an undirected edge connecting vertices p_i and q_i to the given graph G good?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq K \leq 2 \times 10^5
• 1 \leq x_i, y_i \leq N
• x_i \neq y_i
• i \neq j \implies \lbrace x_i, y_i \rbrace \neq \lbrace x_j, y_j \rbrace
• For all i = 1, 2, \ldots, K, there is no path connecting vertices x_i and y_i.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq p_i, q_i \leq N
• p_i \neq q_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

No
No
Yes
Yes

• For the first question, the graph G^{(1)} is not good because it has a path 1 \rightarrow 2 \rightarrow 5 connecting vertices x_1 = 1 and y_1 = 5. Therefore, print No.
• For the second question, the graph G^{(2)} is not good because it has a path 2 \rightarrow 6 connecting vertices x_2 = 2 and y_2 = 6. Therefore, print No.
• For the third question, the graph G^{(3)} is good. Therefore, print Yes.
• For the fourth question, the graph G^{(4)} is good. Therefore, print Yes.

As seen in this sample input, note that the given graph G may have self-loops or multi-edges.

Problem Statement

We have a simple undirected graph G with (S+T) vertices and M edges. The vertices are numbered 1 through (S+T), and the edges are numbered 1 through M. Edge i connects Vertices u_i and v_i.
Here, vertex sets V_1 = \lbrace 1, 2,\dots, S\rbrace and V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace are both independent sets.

A cycle of length 4 is called a 4-cycle.
If G contains a 4-cycle, choose any of them and print the vertices in the cycle. You may print the vertices in any order.
If G does not contain a 4-cycle, print -1.

Constraints

• 2 \leq S \leq 3 \times 10^5
• 2 \leq T \leq 3000
• 4 \leq M \leq \min(S \times T,3 \times 10^5)
• 1 \leq u_i \leq S
• S + 1 \leq v_i \leq S + T
• If i \neq j, then (u_i, v_i) \neq (u_j, v_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1 2 4 5

There are edges between Vertices 1 and 4, 4 and 2, 2 and 5, and 5 and 1, so Vertices 1, 2, 4, and 5 form a 4-cycle. Thus, 1, 2, 4, and 5 should be printed.
The vertices may be printed in any order. Besides the Sample Output, 2 5 1 4 is also considered correct, for example.

Sample Input 2

3 2 4
1 4
1 5
2 5
3 5

Sample Output 2

-1

Some inputs may give G without a 4-cycle.

Sample Input 3

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

Sample Output 3

1 7 2 9

Problem Statement

There is a complex composed of N 10^9-story skyscrapers. The skyscrapers are numbered 1 to N, and the floors are numbered 1 to 10^9.

From any floor of any skyscraper, one can use a skybridge to get to the same floor of any other skyscraper in one minute.

Additionally, there are M elevators. The i-th elevator runs between Floor B_i and Floor C_i of Skyscraper A_i. With this elevator, one can get from Floor x to Floor y of Skyscraper A_i in |x-y| minutes, for every pair of integers x,y such that B_i \le x,y \le C_i.

Answer the following Q queries.

• Determine whether it is possible to get from Floor Y_i of Skyscraper X_i to Floor W_i of Skyscraper Z_i, and find the shortest time needed to get there if it is possible.

Constraints

• 1 \le N,M,Q \le 2 \times 10^5
• 1 \le A_i \le N
• 1 \le B_i < C_i \le 10^9
• 1 \le X_i,Z_i \le N
• 1 \le Y_i,W_i \le 10^9
• All values in input are integers.

Sample Input 1

3 4 3
1 2 10
2 3 7
3 9 14
3 1 3
1 3 3 14
3 1 2 7
1 100 1 101

Sample Output 1

12
7
-1

For the 1-st query, you can get to the destination in 12 minutes as follows.

• Use Elevator 1 to get from Floor 3 to Floor 9 of Skyscraper 1, in 6 minutes.
• Use the skybridge on Floor 9 to get from Skyscraper 1 to Skyscraper 3, in 1 minute.
• Use Elevator 3 to get from Floor 9 to Floor 14 of Skyscraper 3, in 5 minutes.

For the 3-rd query, the destination is unreachable, so -1 should be printed.

Sample Input 2

1 1 1
1 1 2
1 1 1 2

Sample Output 2

1

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.

Find the number, modulo 998244353, of ways to write an integer between 1 and K, inclusive, on each vertex of this graph to satisfy the following condition:

• two vertices connected by an edge always have different numbers written on them.

Constraints

• 1 \leq N \leq 30
• 0 \leq M \leq \min \left(30, \frac{N(N-1)}{2} \right)
• 1 \leq K \leq 10^9
• 1 \leq u_i \lt v_i \leq N
• The given graph is simple.

Sample Input 1

4 3 2
1 2
2 4
2 3

Sample Output 1

2

Here are the two ways to satisfy the condition.

• Write 1 on vertices 1, 3, 4, and write 2 on vertex 2.
• Write 1 on vertex 2, and write 2 on vertex 1, 3, 4.

Sample Input 2

4 0 10

Sample Output 2

10000

All 10^4 ways satisfy the condition.

Sample Input 3

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

Sample Output 3

120

Sample Input 4

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

Sample Output 4

838338733

Sample Input 5

7 12 1000000000
4 5
2 7
3 4
6 7
3 5
5 6
5 7
1 3
4 7
1 5
2 3
3 6

Sample Output 5

418104233