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

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

• N is an integer such that 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa

Problem Statement

There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days. On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it. If no such noodle is available on any day, his plan fails. Additionally, he cannot eat the same noodle on multiple days.

Can Takahashi accomplish his meal plan?

Constraints

• 1 \leq M \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 2
1 1 3
3 1

Sample Output 1

Yes

He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.

Sample Input 2

1 1
1000000000
1

Sample Output 2

No

A noodle of length exactly 1 is needed.

Sample Input 3

5 2
1 2 3 4 5
5 5

Sample Output 3

No

Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

• All input values are integers.
• 1 \le M \le 100
• 1 \le D_i \le 100
• D_1 + D_2 + \dots + D_M is odd.

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

• Months 1,2,3,4,5,6 contain a total of 181 days.
• Day 1 of month 7 is the 182-th day.
• Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3

Problem Statement

You are given an integer X. The following action on this integer is called an operation.

• Choose and do one of the following.
  • Add 1 to X.
  • Subtract 1 from X.

The terms in the arithmetic progression S with N terms whose initial term is A and whose common difference is D are called good numbers.
Consider performing zero or more operations to make X a good number. Find the minimum number of operations required to do so.

Constraints

• All values in input are integers.
• -10^{18} \le X,A \le 10^{18}
• -10^6 \le D \le 10^6
• 1 \le N \le 10^{12}

Sample Input 1

6 2 3 3

Sample Output 1

1

Since A=2,D=3,N=3, we have S=(2,5,8).
You can subtract 1 from X once to make X=6 a good number.
It is impossible to make X good in zero operations.

Sample Input 2

0 0 0 1

Sample Output 2

0

We might have D=0. Additionally, no operation might be required.

Sample Input 3

998244353 -10 -20 30

Sample Output 3

998244363

Sample Input 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

Sample Output 4

444445

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

Given is a string S consisting of X and ..

You can do the following operation on S between 0 and K times (inclusive).

• Replace a . with an X.

What is the maximum possible number of consecutive Xs in S after the operations?

Constraints

• 1 \leq |S| \leq 2 \times 10^5
• Each character of S is X or ..
• 0 \leq K \leq 2 \times 10^5
• K is an integer.

Sample Input 1

XX...X.X.X.
2

Sample Output 1

5

After replacing the Xs at the 7-th and 9-th positions with X, we have XX...XXXXX., which has five consecutive Xs at 6-th through 10-th positions.
We cannot have six or more consecutive Xs, so the answer is 5.

Sample Input 2

XXXX
200000

Sample Output 2

4

It is allowed to do zero operations.

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

• Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

• 1 \le N \le 2 \times 10^5
• 0 \le M \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i,V_i \le N
• The given graph is simple.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

• Choose Vertex 3. The cost is A_1=3.
• Choose Vertex 1. The cost is A_2+A_4=3.
• Choose Vertex 2. The cost is 0.
• Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

1199

Problem Statement

You are given a positive integer X with N digits in decimal representation. None of the digits of X is 0.
For a subset S of \lbrace 1,2, \ldots, N-1 \rbrace , let f(S) be defined as follows.

See the decimal representation of X as a string of length N, and decompose it into |S| + 1 strings by splitting it between the i-th and (i + 1)-th characters if and only if i \in S.
Then, see these |S| + 1 strings as integers in decimal representation, and let f(S) be the product of these |S| + 1 integers.

There are 2^{N-1} subsets of \lbrace 1,2, \ldots, N-1 \rbrace , including the empty set, which can be S. Find the sum of f(S) over all these S, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• X has N digits in decimal representation, none of which is 0.
• All values in the input are integers.

Sample Input 1

3
234

Sample Output 1

418

For S = \emptyset, we have f(S) = 234.
For S = \lbrace 1 \rbrace, we have f(S) = 2 \times 34 = 68.
For S = \lbrace 2 \rbrace, we have f(S) = 23 \times 4 = 92.
For S = \lbrace 1, 2 \rbrace, we have f(S) = 2 \times 3 \times 4 = 24.
Thus, you should print 234 + 68 + 92 + 24 = 418.

Sample Input 2

4
5915

Sample Output 2

17800

Sample Input 3

9
998244353

Sample Output 3

258280134