Problem Statement

There is an ultramarathon course totaling $100\;\mathrm{km}$. Water stations are set up every $5\;\mathrm{km}$ along the course, including the start and goal, for a total of $21$.

Takahashi is at the $N\;\mathrm{km}$ point of this course. Find the position of the nearest water station to him.

Under the constraints of this problem, it can be proven that the nearest water station is uniquely determined.

Constraints

• $0\leq N\leq100$
• $N$ is an integer.

Sample Input 1

53

Sample Output 1

55

Takahashi is at the $53\;\mathrm{km}$ point of the course. The water station at the $55\;\mathrm{km}$ point is $2\;\mathrm{km}$ away, and there is no closer water station. Therefore, you should print $55$.

Sample Input 2

21

Sample Output 2

20

Takahashi could also go back the way.

Sample Input 3

100

Sample Output 3

100

There are also water stations at the start and goal. Additionally, Takahashi may already be at a water station.

Problem Statement

There are $7$ points $A$, $B$, $C$, $D$, $E$, $F$, and $G$ on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.

• Between $A$ and $B$: $3$
• Between $B$ and $C$: $1$
• Between $C$ and $D$: $4$
• Between $D$ and $E$: $1$
• Between $E$ and $F$: $5$
• Between $F$ and $G$: $9$

You are given two uppercase English letters $p$ and $q$. Each of $p$ and $q$ is A, B, C, D, E, F, or G, and it holds that $p \neq q$.
Find the distance between the points $p$ and $q$.

Constraints

• Each of $p$ and $q$ is A,B,C,D,E,F, or G.
• $p \neq q$

Sample Input 1

A C

Sample Output 1

4

The distance between the points $A$ and $C$ is $3 + 1 = 4$.

Sample Input 2

G B

Sample Output 2

20

The distance between the points $G$ and $B$ is $9 + 5 + 1 + 4 + 1 = 20$.

Sample Input 3

C F

Sample Output 3

10

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$-th row from the top and the $j$-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least $2$ squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers $(a,b,c,d)$ that satisfied all of the following conditions.

• $1 \leq a \lt b \leq H$
• $1 \leq c \lt d \leq W$
• There was one cookie on each square $(i, j)$ such that $a \leq i \leq b, c \leq j \leq d$, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square $(i, j)$ is given as the character $S_{i,j}$, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

• $2 \leq H, W \leq 500$
• $S_{i,j}$ is # or ..

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with $(2, 3)$ as the top-left corner and $(4, 5)$ as the bottom-right corner, and Snuke ate the cookie on $(2, 4)$. Thus, you should print $(2, 4)$.

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with $(1, 1)$ as the top-left corner and $(3, 2)$ as the bottom-right corner, and Snuke ate the cookie at $(1, 2)$.

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

Problem Statement

Takahashi keeps a sleep log. The log is represented as an odd-length sequence $A=(A _ 1(=0), A _ 2,\ldots,A _ N)$, where odd-numbered elements represent times he got up, and even-numbered elements represent times he went to bed. More formally, he had the following sleep sessions after starting the sleep log.

• For every integer $i$ such that $1\leq i\leq\dfrac{N-1}2$, he fell asleep exactly $A _ {2i}$ minutes after starting the sleep log and woke up exactly $A _ {2i+1}$ minutes after starting the sleep log.
• He did not fall asleep or wake up at any other time.

Answer the following $Q$ questions. For the $i$-th question, you are given a pair of integers $(l _ i,r _ i)$ such that $0\leq l _ i\leq r _ i\leq A _ N$.

• What is the total number of minutes for which Takahashi was asleep during the $r _ i-l _ i$ minutes from exactly $l _ i$ minutes to $r _ i$ minutes after starting the sleep log?

Constraints

• $3\leq N\lt2\times10^5$
• $N$ is odd.
• $0=A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^9$
• $1\leq Q\leq2\times10^5$
• $0\leq l _ i\leq r _ i\leq A _ N\ (1\leq i\leq Q)$
• All input values are integers.

Sample Input 1

7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

Sample Output 1

480
0
960

Takahashi slept as shown in the following figure.

The answers to each question are as follows.

• Between $480$ minutes and $1920$ minutes after starting the sleep log, Takahashi slept from $480$ minutes to $720$ minutes, from $1320$ minutes to $1440$ minutes, and from $1800$ minutes to $1920$ minutes in $3$ sleep sessions. The total sleep time is $240+120+120=480$ minutes.
• Between $720$ minutes and $1200$ minutes after starting the sleep log, Takahashi did not sleep. The total sleep time is $0$ minutes.
• Between $0$ minutes and $2160$ minutes after starting the sleep log, Takahashi slept from $240$ minutes to $720$ minutes, from $1320$ minutes to $1440$ minutes, and from $1800$ minutes to $2160$ minutes in $3$ sleep sessions. The total sleep time is $480+120+360=960$ minutes.

Therefore, the three lines of the output should contain $480$, $0$, and $960$.

Sample Input 2

21
0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000
10
77 721
255 541
478 970
369 466
343 541
42 165
16 618
222 592
730 983
338 747

Sample Output 2

296
150
150
49
89
20
279
183
61
177

Problem Statement

There is a simple undirected graph with $N$ vertices and $M$ edges, where vertices are numbered from $1$ to $N$, and edges are numbered from $1$ to $M$. Edge $i$ connects vertex $a_i$ and vertex $b_i$.
$K$ security guards numbered from $1$ to $K$ are on some vertices. Guard $i$ is on vertex $p_i$ and has a stamina of $h_i$. All $p_i$ are distinct.

A vertex $v$ is said to be guarded when the following condition is satisfied:

• there is at least one guard $i$ such that the distance between vertex $v$ and vertex $p_i$ is at most $h_i$.

Here, the distance between vertex $u$ and vertex $v$ is the minimum number of edges in the path connecting vertices $u$ and $v$.

List all guarded vertices in ascending order.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right)$
• $1 \leq K \leq N$
• $1 \leq a_i, b_i \leq N$
• The given graph is simple.
• $1 \leq p_i \leq N$
• All $p_i$ are distinct.
• $1 \leq h_i \leq N$
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
1 2 3 5

The guarded vertices are $1, 2, 3, 5$.
These vertices are guarded because of the following reasons.

• The distance between vertex $1$ and vertex $p_1 = 1$ is $0$, which is not greater than $h_1 = 1$. Thus, vertex $1$ is guarded.
• The distance between vertex $2$ and vertex $p_1 = 1$ is $1$, which is not greater than $h_1 = 1$. Thus, vertex $2$ is guarded.
• The distance between vertex $3$ and vertex $p_2 = 5$ is $1$, which is not greater than $h_2 = 2$. Thus, vertex $3$ is guarded.
• The distance between vertex $5$ and vertex $p_1 = 1$ is $1$, which is not greater than $h_1 = 1$. Thus, vertex $5$ is guarded.

Sample Input 2

3 0 1
2 3

Sample Output 2

1
2

The given graph may have no edges.

Sample Input 3

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

Sample Output 3

7
1 2 3 5 6 8 9

Problem Statement

This is an interactive problem (where your program and the judge program interact through Standard Input and Output).

There is a simple connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered with integers from $1$ to $N$.

Initially, you are at vertex $1$. Repeat moving to an adjacent vertex at most $2N$ times to reach vertex $N$.

Here, you do not initially know all edges of the graph, but you will be informed of the vertices adjacent to the vertex you are at.

Constraints

• $2\leq N\leq100$
• $N-1\leq M\leq\dfrac{N(N-1)}2$
• The graph is simple and connected.
• All input values are integers.

Input and Output

First, receive the number of vertices $N$ and the number of edges $M$ in the graph from Standard Input:

$N$ $M$

Next, you get to repeat the operation described in the problem statement at most $2N$ times against the judge.

At the beginning of each operation, the vertices adjacent to the vertex you are currently at are given from Standard Input in the following format:

$k$ $v _ 1$ $v _ 2$ $\ldots$ $v _ k$

Here, $v _ i\ (1\leq i\leq k)$ are integers between $1$ and $N$ such that $v _ 1\lt v _ 2\lt\cdots\lt v _ k$.

Choose one of $v _ i\ (1\leq i\leq k)$ and print it to Standard Output in the following format:

$v _ i$

After this operation, you will be at vertex $v _ i$.

If you perform more than $2N$ operations or print invalid output, the judge will send -1 to Standard Input.

If the destination of a move is vertex $N$, the judge will send OK to Standard Input and terminate.

When receiving -1 or OK, immediately terminate the program.

Notes

• In each output, insert a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
• The verdict will be indeterminate if the program prints invalid output or quits prematurely in the middle of the interaction.
• Terminate the program immediately after reaching vertex $N$. Otherwise, the verdict will be indeterminate.
• The judge for this problem is adaptive. This means that the graph may change without contradicting the constraints or previous outputs.

Sample Interaction

In the following sample interaction, we have $N=4$, $M=5$, and the graph in the figure below.

You will be judged as correct if you immediately terminate the program after receiving OK.

Problem Statement

You are given a set $S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace$ of non-empty strings of length at most $6$ consisting of a and b. Find the number of strings $T$ of length $N$ consisting of a and b that satisfy the following condition:

• $T$ does not contain $s _ i$ as a consecutive substring for any $s _ i\in S$.

Since the answer can be enormous, find it modulo $998244353$.

Constraints

• $1\leq N\leq10^{18}$
• $1\leq M\leq126$
• $N$ and $M$ are integers.
• $s _ i$ is a non-empty string of length at most $6$ consisting of a and b.
• $s _ i\neq s _ j\ (1\leq i\lt j\leq M)$

Sample Input 1

4 3
aab
bbab
abab

Sample Output 1

10

There are $10$ strings of length $4$ consisting of a and b that do not contain aab, bbab, or abab as consecutive substrings: aaaa, abaa, abba, abbb, baaa, baba, babb, bbaa, bbba, and bbbb. Thus, you should print $10$.

Sample Input 2

20 1
aa

Sample Output 2

17711

Sample Input 3

1000000007 28
bbabba
bbbbaa
aabbab
bbbaba
baaabb
babaab
bbaaba
aabaaa
aaaaaa
aabbaa
bbaaaa
bbaabb
bbabab
aababa
baaaba
ababab
abbaba
aabaab
ababaa
abbbba
baabaa
aabbbb
abbbab
baaaab
baabbb
ababbb
baabba
abaaaa

Sample Output 3

566756841

Print the answer modulo $998244353$.