Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

• All participants who ranked A-th or higher get a T-shirt.
• Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

• All values in input are integers.
• 1 \le A < B \le 1000
• 1 \le C \le B-A
• 1 \le X \le 1000

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

Problem Statement

You are given a string S consisting of digits.

Remove all characters from S except for 2, and then concatenate the remaining characters in their original order to form a new string.

Constraints

• S is a string consisting of digits with length between 1 and 100, inclusive.
• S contains at least one 2.

Sample Input 1

20250222

Sample Output 1

22222

By removing 0, 5, and 0 from 20250222 and then concatenating the remaining characters in their original order, the string 22222 is obtained.

Sample Input 2

2

Sample Output 2

2

Sample Input 3

22222000111222222

Sample Output 3

22222222222

Problem Statement

There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.

Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.

Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).

Constraints

• -10^{18}\leq A \leq 10^{18}
• 1\leq M \leq 10^9
• -10^{18}\leq L\leq R \leq 10^{18}
• All input values are integers.

Sample Input 1

5 3 -1 6

Sample Output 1

3

Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.

Sample Input 2

-2 2 1 1

Sample Output 2

0

Sometimes, Takahashi and Aoki are standing at the same point.

Sample Input 3

-177018739841739480 2436426 -80154573737296504 585335723211047198

Sample Output 3

273142010859

Problem Statement

N people participated in a programming contest consisting of M problems.
The participants are numbered person 1, person 2, \ldots, person N, and the problems are numbered problem 1, problem 2, \ldots, problem M.

In this contest, K events occurred in order; in the i-th event (1\leq i\leq K), the following happened:

• Person A_i solved problem B_i.

The same event does not occur two or more times. Also, apart from these K events, nobody solves any problem.

Output the numbers of all people who solved all problems.
If there are multiple such people, output them in ascending order of the time at which they solved all problems.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 10
• K \geq 1
• 1 \leq A_i \leq N
• 1 \leq B_i \leq M
• If i\neq j then (A_i,B_i)\neq (A_j,B_j).
• All input values are integers.

Sample Input 1

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

Sample Output 1

3 1

In the contest, the following happened in order.

• Person 1 solved problem 1. So far, person 1 has solved only problem 1.
• Person 3 solved problem 2. So far, person 3 has solved only problem 2.
• Person 2 solved problem 1. So far, person 2 has solved only problem 1.
• Person 3 solved problem 1. So far, person 3 has solved problems 1,2. Thus, at this point person 3 has solved all problems.
• Person 1 solved problem 2. So far, person 1 has solved problems 1,2. Thus, at this point person 1 has solved all problems.

Thus, the people who solved all problems are persons 1,3, and the one who solved all problems earlier is person 3. Thus, output 3,1 in this order, separated by spaces.

Sample Input 2

2 2 2
1 1
2 2

Sample Output 2

If there is no person who solved all problems, output nothing.

Problem Statement

You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.

You may perform the following two kinds of operations zero or more times in any order:

• Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.

• Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.

How many yen do you need to pay to make S a palindrome?

Constraints

• 1\leq N \leq 5000
• 1\leq A,B\leq 10^9
• S is a string of length N consisting of lowercase English letters.
• All values in the input except for S are integers.

Sample Input 1

5 1 2
rrefa

Sample Output 1

3

First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.

Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.

Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.

Sample Input 2

8 1000000000 1000000000
bcdfcgaa

Sample Output 2

4000000000

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N).

Find the minimum possible sum of all elements of A after performing the following operation exactly K times.

• Choose an integer x. For each i such that A_i = x, replace the value of A_i with 0.

Constraints

• 1 \leq K \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

6 2
7 2 7 2 2 9

Sample Output 1

6

Initially, A = (7, 2, 7, 2, 2, 9).

Performing the operation with x = 9 gives A = (7, 2, 7, 2, 2, 0).

Next, performing the operation with x = 7 gives A = (0, 2, 0, 2, 2, 0).

At this point, the sum of all elements of A is 0 + 2 + 0 + 2 + 2 + 0 = 6.

Sample Input 2

8 6
1 2 3 4 1 2 3 4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

8

Problem Statement

This problem is a subproblem of Problem G.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
  1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
  2. Define an integer x as follows:
     • If S_i = 0 and S_{i+1} = 0, let x = 1.
     • If S_i = 0 and S_{i+1} = 1, let x = 0.
     • If S_i = 1 and S_{i+1} = 0, let x = 0.
     • If S_i = 1 and S_{i+1} = 1, let x = 1.
  3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
     For example, if S= 10101 and you choose i=2, the string after the operation is 1001.

You are given a string T of length N consisting of 0 and 1.
Find the number of beautiful strings that are substrings of T. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

3
110

Sample Output 1

3

The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1. The beautiful strings that are substrings of T are the following three strings:

• The string 1 obtained by taking the 1st character of T.
• The string 1 obtained by taking the 2nd character of T.
• The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

4

Sample Input 3

30
011011100101110111100010011010

Sample Output 3

225

Problem Statement

There are N cities in a certain country.
You will travel from your office in city 1 to a destination in city N, via zero or more cities.
Two types of transportation are available: company car and train. The time required to travel from city i to city j is as follows:

• D_{i,j} \times A minutes by company car, and
• D_{i,j} \times B + C minutes by train.

You can switch from company car to train, but not vice versa.
You can do so without spending time, but only in a city.

What is the minimum time in minutes to travel from city 1 to city N?

Constraints

• 2 \leq N \leq 1000
• 1 \leq A, B, C \leq 10^6
• D_{i,j} \leq 10^6
• D_{i,i} = 0
• D_{i,j} = D_{j,i} > 0 (i \neq j)
• All input values are integers.

Sample Input 1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

Sample Output 1

78

You can travel from city 1 to city 4 in a total of 78 minutes by moving as follows.

• Travel by company car from city 1 to city 3. This takes 2 \times 8 = 16 minutes.
• Travel by company car from city 3 to city 2. This takes 3 \times 8 = 24 minutes.
• Travel by train from city 2 to city 4. This takes 5 \times 5 + 13 = 38 minutes.

It is impossible to travel from city 1 to city 4 in less than 78 minutes.

Sample Input 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

Sample Output 2

1

Sample Input 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

Sample Output 3

168604826785

Problem Statement

You are given sequences of length N, A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).
You are also given Q queries to process in order.

There are three types of queries:

• 1 l r x : Add x to each of A_l, A_{l+1}, \ldots, A_r.
• 2 l r x : Add x to each of B_l, B_{l+1}, \ldots, B_r.
• 3 l r : Print the remainder of \displaystyle\sum_{i=l}^r (A_i\times B_i) when divided by 998244353.

Constraints

• 1\leq N,Q\leq 2\times 10^5
• 0\leq A_i,B_i\leq 10^9
• 1\leq l\leq r\leq N
• 1\leq x\leq 10^9
• All input values are integers.
• There is at least one query of the third type.

Sample Input 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

Sample Output 1

16
25
84

Initially, A=(1,3,5,6,8) and B=(3,1,2,1,2). The queries are processed in the following order:

• For the first query, print (1\times 3)+(3\times 1)+(5\times 2)=16 modulo 998244353, which is 16.
• For the second query, add 3 to A_2,A_3,A_4,A_5. Now A=(1,6,8,9,11).
• For the third query, print (1\times 3)+(6\times 1)+(8\times 2)=25 modulo 998244353, which is 25.
• For the fourth query, add 1 to A_1,A_2,A_3. Now A=(2,7,9,9,11).
• For the fifth query, add 2 to B_5. Now B=(3,1,2,1,4).
• For the sixth query, print (2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84 modulo 998244353, which is 84.

Thus, the first, second, and third lines should contain 16, 25, and 84, respectively.

Sample Input 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

Sample Output 2

716070898
151723988

Make sure to print the sum modulo 998244353 for the third type of query.