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.

Problem Statement

You have decided to practice. Practice means solving a large number of problems in AtCoder.
Practice takes place over several days. The practice for one day is carried out in the following steps.

• Let M be the number of problems to be solved on that day. Each problem has a value called difficulty, which is a pair of non-negative integers (A, B).
• First, rearrange the M problems in any order. Then, solve the problems one by one in that order.
• You have a value called fatigue. The fatigue at the beginning of the day is 0, and it changes from x to Ax + B when solving a problem with difficulty (A, B).
• The fatigue at the end of solving all M problems is called the energy consumed for that day.

There is a sequence of N problems in AtCoder, called problem 1, problem 2, \dots, problem N in order. The difficulty of problem i is (A_i, B_i).
You have decided to solve all N problems through practice.
Practice is carried out in the following steps. Below, let [L, R] denote the following sequence of problems: problem L, problem L+1, ..., problem R.

• Choose an integer K freely between 1 and N, inclusive. The practice will last K days.
• Divide the sequence of N problems into K non-empty continuous subsequences, and let S_i be the i-th sequence.
  Formally, choose a strictly increasing non-negative integer sequence x_0, x_1, \dots, x_K such that 1 = x_0 and x_K = N + 1, and let S_i = [x_{i-1}, x_i - 1] for 1 \leq i \leq K.
• Then, for i=1, 2, \dots, K, solve all problems in S_i on the i-th day of practice.

You have decided to practice so that the total energy consumed throughout the practice is at most X.
Let D be the minimum possible value of K, the number of days, for such a practice. (Here, it is guaranteed that \sum_{i = 1}^N B_i \leq X. Under this constraint, such D always exists.)
Also, let M be the minimum possible total energy consumed throughout a practice such that K=D.

Find D and M.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X \leq 10^8
• 1 \leq A_i \leq 10^5
• 1 \leq B_i
• \sum_{i=1}^N B_i \leq X
• All input values are integers.

Sample Input 1

3 100
2 2
3 4
5 7

Sample Output 1

1 52

In this test case, you can solve all problems in one day while satisfying the condition for X.
By following the steps below, the total energy consumed during the practice will be 52, which is the minimum.

• Set K=1 and solve [1, 3] on the first day.
• Carry out the practice on the first day in the following steps.
  • Arrange the problems in the order (problem 3, problem 2, problem 1).
  • Initially, the fatigue is 0.
  • Solve problem 3. The fatigue changes to 5 \times 0 + 7 = 7.
  • Solve problem 2. The fatigue changes to 3 \times 7 + 4 = 25.
  • Solve problem 1. The fatigue changes to 2 \times 25 + 2 = 52.
  • The fatigue at the end of solving all problems is 52. Therefore, the energy consumed on this day is 52.
• The total energy consumed throughout the practice is also 52.

Sample Input 2

3 30
2 2
3 4
5 7

Sample Output 2

2 17

This test case is obtained by changing X from 100 to 30 in the first test case. Therefore, it is impossible to solve all problems in one day while satisfying the condition for X.

By following the steps below, you can achieve M=17 by practicing for two days.

• Set K = 2, and solve [1, 2] on the first day and [3, 3] on the second day.
• Carry out the practice on the first day in the following steps.
  • Arrange the problems in the order (problem 1, problem 2).
  • Initially, the fatigue is 0.
  • Solve problem 1. The fatigue changes to 2 \times 0 + 2 = 2.
  • Solve problem 2. The fatigue changes to 3 \times 2 + 4 = 10.
  • The fatigue at the end of solving all problems is 10. Therefore, the energy consumed on the first day is 10.
• Carry out the practice on the second day in the following steps.
  • Arrange the problems in the order (problem 3).
  • Initially, the fatigue is 0.
  • Solve problem 3. The fatigue changes to 5 \times 0 + 7 = 7.
  • The fatigue at the end of solving all problems is 7. Therefore, the energy consumed on the second day is 7.
• The total energy consumed throughout the practice is 10 + 7 = 17.

Sample Input 3

5 50000000
100000 10000000
100000 10000000
100000 10000000
100000 10000000
100000 10000000

Sample Output 3

5 50000000

The optimal practice is to solve one problem per day.

Sample Input 4

10 100000000
5 88
66 4
52 1
3 1
12 1
53 25
11 12
12 2
1 20
47 10

Sample Output 4

2 73647

Sample Input 5

15 100000000
2387 3178
2369 5772
1 29
36 3
52 2981
196 1
36 704
3 3
1501 5185
23 628
3623 810
80 101
6579 15
681 7
183 125

Sample Output 5

4 54468135