Problem Statement

Takahashi wants a beverage called AtCoder Drink in a restaurant. It can be ordered at a regular price of P yen.

He also has a discount coupon that allows him to order it at a lower price of Q yen. However, he must additionally order one of the restaurant's N dishes to use that coupon. For each i = 1, 2, \ldots, N, the price of the i-th dish is D_i yen.

Print the minimum total amount of money that he must pay to get the drink.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \lt P \leq 10^5
• 1 \leq D_i \leq 10^5
• All input values are integers.

Sample Input 1

3 100 50
60 20 40

Sample Output 1

70

If he uses the coupon and orders the second dish, he can get the drink by paying 50 yen for it and 20 yen for the dish, for a total of 70 yen, which is the minimum total payment needed.

Sample Input 2

3 100 50
60000 20000 40000

Sample Output 2

100

The total payment will be minimized by not using the coupon and paying the regular price of 100 yen.

Problem Statement

AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.

Takahashi wonders whether there is a product that is strictly superior to another. If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.

• P _ i\geq P _ j.
• The j-th product has all functions of the i-th product.
• P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.

Constraints

• 2\leq N\leq100
• 1\leq M\leq100
• 1\leq P _ i\leq10^5\ (1\leq i\leq N)
• 1\leq C _ i\leq M\ (1\leq i\leq N)
• 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

Sample Output 1

Yes

(i,j)=(4,3) satisfies all of the conditions.

No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.

Sample Input 2

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

Sample Output 2

No

Multiple products may have the same price and functions.

Sample Input 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

Sample Output 3

Yes

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

• N is an integer.
• 2 \leq N \leq 2 \times 10^5
• S_i is a string consisting of lowercase English letters.
• |S_i| \geq 1
• \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3

• S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
• S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
• S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

Problem Statement

There are N sports players.

Among them, there are M incompatible pairs. The i-th incompatible pair (1\leq i\leq M) is the A_i-th and B_i-th players.

You will divide the players into T teams. Every player must belong to exactly one team, and every team must have one or more players. Additionally, for each i=1,2,\ldots,M, the A_i-th and B_i-th players must not belong to the same team.

Find the number of ways to satisfy these conditions. Here, two divisions are considered different when there are two players who belong to the same team in one division and different teams in the other.

Constraints

• 1\leq T\leq N\leq10
• 0\leq M\leq\dfrac{N(N-1)}2
• 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
• (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
• All input values are integers.

Sample Input 1

5 2 2
1 3
3 4

Sample Output 1

4

The following four divisions satisfy the conditions.

No other division satisfies them, so print 4.

Sample Input 2

5 1 2
1 3
3 4

Sample Output 2

0

There may be no division that satisfies the conditions.

Sample Input 3

6 4 0

Sample Output 3

65

There may be no incompatible pair.

Sample Input 4

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

Sample Output 4

8001

Problem Statement

You are given a string S of length N consisting of 0 and 1. It describes a length-N sequence A=(A _ 1,A _ 2,\ldots,A _ N). If the i-th character of S (1\leq i\leq N) is 0, then A _ i=0; if it is 1, then A _ i=1.

Find the following:

\[\sum _ {1\leq i\leq j\leq N}(\cdots((A _ i\barwedge A _ {i+1})\barwedge A _ {i+2})\barwedge\cdots\barwedge A _ j)\]

More formally, find \displaystyle\sum _ {i=1} ^ {N}\sum _ {j=i} ^ Nf(i,j) for f(i,j)\ (1\leq i\leq j\leq N) defined as follows:

\[f(i,j)=\left\{\begin{matrix} A _ i&(i=j)\\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{matrix}\right.\]

Here, \barwedge, NAND, is a binary operator satisfying the following:

\[0\barwedge0=1,0\barwedge1=1,1\barwedge0=1,1\barwedge1=0.\]

Constraints

• 1\leq N\leq10^6
• S is a string of length N consisting of 0 and 1.
• All input values are integers.

Sample Input 1

5
00110

Sample Output 1

9

Here are the values of f(i,j) for the pairs (i,j) such that 1\leq i\leq j\leq N:

• f(1,1)=0=0
• f(1,2)=0\barwedge0=1
• f(1,3)=(0\barwedge0)\barwedge1=0
• f(1,4)=((0\barwedge0)\barwedge1)\barwedge1=1
• f(1,5)=(((0\barwedge0)\barwedge1)\barwedge1)\barwedge0=1
• f(2,2)=0=0
• f(2,3)=0\barwedge1=1
• f(2,4)=(0\barwedge1)\barwedge1=0
• f(2,5)=((0\barwedge1)\barwedge1)\barwedge0=1
• f(3,3)=1=1
• f(3,4)=1\barwedge1=0
• f(3,5)=(1\barwedge1)\barwedge0=1
• f(4,4)=1=1
• f(4,5)=1\barwedge0=1
• f(5,5)=0=0

Their sum is 0+1+0+1+1+0+1+0+1+1+0+1+1+1+0=9, so print 9.

Note that \barwedge does not satisfy the associative property. For instance, (1\barwedge1)\barwedge0=0\barwedge0=1\neq0=1\barwedge1=1\barwedge(1\barwedge0).

Sample Input 2

30
101010000100101011010011000010

Sample Output 2

326

Problem Statement

We have N dice. For each i = 1, 2, \ldots, N, when the i-th die is thrown, it shows a random integer between 1 and A_i, inclusive, with equal probability.

Find the probability, modulo 998244353, that the following condition is satisfied when the N dice are thrown simultaneously.

There is a way to choose some (possibly all) of the N dice so that the sum of their results is 10.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

4
1 7 2 9

Sample Output 1

942786334

For instance, if the first, second, third, and fourth dice show 1, 3, 2, and 7, respectively, these results satisfy the condition. In fact, if the second and fourth dice are chosen, the sum of their results is 3 + 7 = 10. Alternatively, if the first, third, and fourth dice are chosen, the sum of their results is 1 + 2 + 7 = 10.

On the other hand, if the first, second, third, and fourth dice show 1, 6, 1, and 5, respectively, there is no way to choose some of them so that the sum of their results is 10, so the condition is not satisfied.

In this sample input, the probability of the results of the N dice satisfying the condition is \frac{11}{18}. Thus, print this value modulo 998244353, that is, 942786334.

Sample Input 2

7
1 10 100 1000 10000 100000 1000000

Sample Output 2

996117877

Problem Statement

There are N Takahashi.

The i-th Takahashi has an integer A_i and B_i balls.

An integer x between 1 and K, inclusive, will be chosen uniformly at random, and they will repeat the following operation x times.

• For every i, the i-th Takahashi gives all his balls to the A_i-th Takahashi.

Beware that all N Takahashi simultaneously perform this operation.

For each i=1,2,\ldots,N, find the expected value, modulo 998244353, of the number of balls the i-th Takahashi has at the end of the operations.

Constraints

• 1\leq N\leq 2\times10^5
• 1\leq K\leq 10^{18}
• K is not a multiple of 998244353.
• 1\leq A _ i\leq N\ (1\leq i\leq N)
• 0\leq B _ i\lt998244353\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

3 0 499122179 499122178 5

During two operations, the five Takahashi have the following number of balls.

If x=1 is chosen, the five Takahashi have 4,0,1,2,5 balls.
If x=2 is chosen, the five Takahashi have 2,0,4,1,5 balls.

Thus, the sought expected values are 3,0,\dfrac52,\dfrac32,5. Print these values modulo 998244353, that is, 3,0,499122179,499122178,5, separated by spaces.

Sample Input 2

3 1000
1 1 1
1 10 100

Sample Output 2

111 0 0

After one or more operations, the first Takahashi gets all balls.

Sample Input 3

16 1000007
16 12 6 12 1 8 14 14 5 7 6 5 9 6 10 9
719092922 77021920 539975779 254719514 967592487 476893866 368936979 465399362 342544824 540338192 42663741 165480608 616996494 16552706 590788849 221462860

Sample Output 3

817852305 0 0 0 711863206 253280203 896552049 935714838 409506220 592088114 0 413190742 0 363914270 0 14254803

Sample Input 4

24 100000000007
19 10 19 15 1 20 13 15 8 23 22 16 19 22 2 20 12 19 17 20 16 8 23 6
944071276 364842194 5376942 671161415 477159272 339665353 176192797 2729865 676292280 249875565 259803120 103398285 466932147 775082441 720192643 535473742 263795756 898670859 476980306 12045411 620291602 593937486 761132791 746546443

Sample Output 4

918566373 436241503 0 0 0 455245534 0 356196743 0 906000633 0 268983266 21918337 0 733763572 173816039 754920403 0 273067118 205350062 0 566217111 80141532 0

Problem Statement

A monster with health H has appeared right in front of you. Your magic power is now 0.

You can use N moves called move 1, move 2, \ldots, move N, any number of times in any order.

For each i = 1, 2, \ldots, N, move i can only be used when your magic power is at least C_i, and its use will decrease your magic power by C_i and the monster's health by D_i. Here, if C_i is negative, decreasing your magic power by C_i means increasing it by -C_i.

Find the minimum possible number of times you use moves before the monster's health is 0 or lower. The constraints of this problem guarantee that a finite number of uses of moves can make it 0 or lower (see below).

Constraints

• 1 \leq N \leq 300
• 1 \leq H \leq 10^{18}
• -300 \leq C_i \leq 300
• C_i \leq 0 for some 1 \leq i \leq N.
• 1 \leq D_i \leq 10^9
• All input values are integers.

Sample Input 1

3 48
3 20
-4 2
1 5

Sample Output 1

5

From the initial state where your magic power is 0 and the monster's health is 48, consider using moves as follows.

• Use move 2. Now, your magic power is 4, and the monster's health is 46.
• Use move 3. Now, your magic power is 3, and the monster's health is 41.
• Use move 1. Now, your magic power is 0, and the monster's health is 21.
• Use move 2. Now, your magic power is 4, and the monster's health is 19.
• Use move 1. Now, your magic power is 1, and the monster's health is -1.

Here, you use moves five times before the monster's health is not greater than 0, which is the minimum possible number.

Sample Input 2

20 583988303060450752
-64 273760634
-238 960719353
-114 191410838
-250 357733867
232 304621362
-286 644706927
210 37849132
-230 556412112
-142 136397527
101 380675202
-140 152300688
190 442931589
-187 940659077
-12 312523039
32 126515475
-143 979861204
105 488280613
240 664922712
290 732741849
69 541282303

Sample Output 2

595990842