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

Print how many distinct integers there are in given five integers A, B, C, D, and E.

Constraints

• 0 \leq A, B, C, D, E \leq 100
• All values in input are integers.

Sample Input 1

31 9 24 31 24

Sample Output 1

3

In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.

Sample Input 2

0 0 0 0 0

Sample Output 2

1

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

• The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

• S is a string consisting of o and x.
• The length of S is between 1 and 10 (inclusive).

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

• -1000 \leq X,Y,Z \leq 1000
• X, Y, and Z are distinct, and none of them is 0.
• All values in the input are integers.

Sample Input 1

10 -10 1

Sample Output 1

10

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

40

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

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

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• N \geq 2
• L_i \geq 2
• The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
• 1 \leq a_{i,j} \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

Problem Statement

You are given an integer N and a string S consisting of 0, 1, and ?. Let T be the set of values that can be obtained by replacing each ? in S with 0 or 1 and interpreting the result as a binary integer. For instance, if S= ?0?, we have T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace.

Print (as a decimal integer) the greatest value in T less than or equal to N. If T does not contain a value less than or equal to N, print -1 instead.

Constraints

• S is a string consisting of 0, 1, and ?.
• The length of S is between 1 and 60, inclusive.
• 1\leq N \leq 10^{18}
• N is an integer.

Sample Input 1

?0?
2

Sample Output 1

1

As shown in the problem statement, T=\lbrace 0,1,4,5\rbrace. Among them, 0 and 1 are less than or equal to N, so you should print the greatest of them, 1.

Sample Input 2

101
4

Sample Output 2

-1

We have T=\lbrace 5\rbrace, which does not contain a value less than or equal to N.

Sample Input 3

?0?
1000000000000000000

Sample Output 3

5

Problem Statement

Given are a tree with N vertices, a sequence of M numbers A=(A_1,\ldots,A_M), and an integer K.
The vertices are numbered 1 through N, and the i-th edge connects Vertices U_i and V_i.

We will paint each of the N-1 edges of this tree red or blue. Among the 2^{N-1} such ways, find the number of ones that satisfies the following condition, modulo 998244353.

Condition:
Let us put a piece on Vertex A_1, and for each i=1,\ldots,M-1 in this order, move it from Vertex A_i to Vertex A_{i+1} along the edges in the shortest path. After all of these movements, R-B=K holds, where R and B are the numbers of times the piece traverses a red edge and a blue edge, respectively.

Constraints

• 2 \leq N \leq 1000
• 2 \leq M \leq 100
• |K| \leq 10^5
• 1 \leq A_i \leq N
• 1\leq U_i,V_i\leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2

If we paint the 1-st and 3-rd edges red and the 2-nd edge blue, the piece will traverse the following numbers of red and blue edges:

• 0 red edges and 1 blue edge when moving from Vertex 2 to 3,
• 0 red edges and 1 blue edge when moving from Vertex 3 to 2,
• 1 red edge and 0 blue edges when moving from Vertex 2 to 1,
• 2 red edges and 1 blue edge when moving from Vertex 1 to 4,

for a total of 3 red edges and 3 blue edges, satisfying the condition.

Another way to satisfy the condition is to paint the 1-st and 3-rd edges blue and the 2-nd edge red. There is no other way to satisfy it, so the answer is 2.

Sample Input 2

3 10 10000
1 2 1 2 1 2 2 1 1 2
1 2
1 3

Sample Output 2

0

There may be no way to paint the tree to satisfy the condition.

Sample Input 3

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

Sample Output 3

126

Sample Input 4

5 8 -1
1 4 1 4 2 1 3 5
1 2
4 1
3 1
1 5

Sample Output 4

2

Problem Statement

You are given a permutation P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).

Find the following value for all i\ (1\leq i\leq N):

• D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen.

Constraints

• 2 \leq N \leq 2\times10^5
• 1 \leq P _ i \leq N\ (1\leq i\leq N)
• i\neq j\implies P _ i\neq P _ j
• All values in the input are integers.

Sample Input 1

4
3 2 4 1

Sample Output 1

2 2 3 3 

For example, for i=1,

• if j=2, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=1;
• if j=3, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=2;
• if j=4, we have \left\lvert P _ i-P _ j\right\rvert=2 and \left\lvert i-j\right\rvert=3.

Thus, the value is minimum when j=2, where \left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert=2, so D _ 1=2.

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

2 2 2 2 2 2 2 

Sample Input 3

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

Sample Output 3

3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7