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 is an enemy with stamina A. Every time you attack the enemy, its stamina reduces by B.

At least how many times do you need to attack the enemy to make its stamina 0 or less?

Constraints

• 1 \le A,B \le 10^{18}
• A and B are integers.

Sample Input 1

7 3

Sample Output 1

3

Attacking three times make the enemy's stamina -2.

Attacking only twice makes the stamina 1, so you need to attack it three times.

Sample Input 2

123456789123456789 987654321

Sample Output 2

124999999

Sample Input 3

999999999999999998 2

Sample Output 3

499999999999999999

Problem Statement

N people, person 1, person 2, \ldots, person N, are playing roulette. The outcome of a spin is one of the 37 integers from 0 to 36. For each i = 1, 2, \ldots, N, person i has bet on C_i of the 37 possible outcomes: A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}.

The wheel has been spun, and the outcome is X. Print the numbers of all people who have bet on X with the fewest bets, in ascending order.

More formally, print all integers i between 1 and N, inclusive, that satisfy both of the following conditions, in ascending order:

• Person i has bet on X.
• For each j = 1, 2, \ldots, N, if person j has bet on X, then C_i \leq C_j.

Note that there may be no number to print (see Sample Input 2).

Constraints

• 1 \leq N \leq 100
• 1 \leq C_i \leq 37
• 0 \leq A_{i, j} \leq 36
• A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} are all different for each i = 1, 2, \ldots, N.
• 0 \leq X \leq 36
• All input values are integers.

Sample Input 1

4
3
7 19 20
4
4 19 24 0
2
26 10
3
19 31 24
19

Sample Output 1

2
1 4

The wheel has been spun, and the outcome is 19. The people who has bet on 19 are person 1, person 2, and person 4, and the number of their bets are 3, 4, and 3, respectively. Therefore, among the people who has bet on 19, the ones with the fewest bets are person 1 and person 4.

Sample Input 2

3
1
1
1
2
1
3
0

Sample Output 2

0

The wheel has been spun and the outcome is 0, but no one has bet on 0, so there is no number to print.

Problem Statement

An election is taking place.

N people voted. The i-th person (1 \leq i \leq N) cast a vote to the candidate named S_i.

Find the name of the candidate who received the most votes. The given input guarantees that there is a unique candidate with the most votes.

Constraints

• 1 \leq N \leq 100
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• N is an integer.
• There is a unique candidate with the most votes.

Sample Input 1

5
snuke
snuke
takahashi
takahashi
takahashi

Sample Output 1

takahashi

takahashi got 3 votes, and snuke got 2, so we print takahashi.

Sample Input 2

5
takahashi
takahashi
aoki
takahashi
snuke

Sample Output 2

takahashi

Sample Input 3

1
a

Sample Output 3

a

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

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

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1

Problem Statement

You are given a string S consisting of three different characters: A, B, and C.

As long as S contains the string ABC as a consecutive substring, repeat the following operation:

Remove the leftmost occurrence of the substring ABC from S.

Print the final string S after performing the above procedure.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of the characters A, B, and C.

Sample Input 1

BAABCBCCABCAC

Sample Output 1

BCAC

For the given string S = BAABCBCCABCAC, the operations are performed as follows.

• In the first operation, the ABC from the 3-rd to the 5-th character in S = BAABCBCCABCAC is removed, resulting in S = BABCCABCAC.
• In the second operation, the ABC from the 2-nd to the 4-th character in S = BABCCABCAC is removed, resulting in S = BCABCAC.
• In the third operation, the ABC from the 3-rd to the 5-th character in S = BCABCAC is removed, resulting in S = BCAC.

Therefore, the final S is BCAC.

Sample Input 2

ABCABC

Sample Output 2

In this example, the final S is an empty string.

Sample Input 3

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

Sample Output 3

AAABBBCCC

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered from 1 through N, and the edges are numbered from 1 through M. Edge i connects Vertex U_i and Vertex V_i.

You are given integers K, S, T, and X. How many sequences A = (A_0, A_1, \dots, A_K) are there satisfying the following conditions?

• A_i is an integer between 1 and N (inclusive).
• A_0 = S
• A_K = T
• There is an edge that directly connects Vertex A_i and Vertex A_{i+1}.
• Integer X\ (X≠S,X≠T) appears even number of times (possibly zero) in sequence A.

Since the answer can be very large, find the answer modulo 998244353.

Constraints

• All values in input are integers.
• 2≤N≤2000
• 1≤M≤2000
• 1≤K≤2000
• 1≤S,T,X≤N
• X≠S
• X≠T
• 1≤U_i<V_i≤N
• If i ≠ j, then (U_i, V_i) ≠ (U_j, V_j).

Sample Input 1

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

Sample Output 1

4

The following 4 sequences satisfy the conditions:

• (1, 2, 1, 2, 3)
• (1, 2, 3, 2, 3)
• (1, 4, 1, 4, 3)
• (1, 4, 3, 4, 3)

On the other hand, (1, 2, 3, 4, 3) and (1, 4, 1, 2, 3) do not, since there are odd number of occurrences of 2.

Sample Input 2

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

Sample Output 2

0

The graph is not necessarily connected.

Sample Input 3

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

Sample Output 3

952504739

Find the answer modulo 998244353.

Problem Statement

Given is a sequence A of length N. You can do this operation any number of times: when the length of the sequence is at least 2, choose two adjacent values, delete them, and insert their sum where they were. How many sequences can result from zero or more operations? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 -1 1

Sample Output 1

4

The following four sequences can result from zero or more operations.

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

Sample Input 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

Sample Output 2

321