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

You are given an integer S between 100 and 999 (inclusive).

If S is between 200 and 299 (inclusive), print Success; otherwise, print Failure.

Constraints

• 100 \le S \le 999
• S is an integer.

Sample Input 1

200

Sample Output 1

Success

200 is between 200 and 299, so print Success.

Sample Input 2

401

Sample Output 2

Failure

401 is not between 200 and 299, so print Failure.

Sample Input 3

999

Sample Output 3

Failure

Problem Statement

You are given N types of strings S_1,S_2,\ldots,S_N.

You perform the following operation once:

• Choose distinct integers i and j\ (1\le i\le N,1\le j\le N) and concatenate S_i and S_j in this order.

How many different strings can be obtained as a result of this operation?

If different choices of (i,j) result in the same concatenated string, it is counted as one string.

Constraints

• 2\le N\le100
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.
• S_i\ne S_j\ (1\le i\lt j\le N)

Sample Input 1

4
at
atco
coder
der

Sample Output 1

11

The possible strings are atatco, atcoat, atcoder, atcocoder, atder, coderat, coderatco, coderder, derat, deratco, dercoder, which are 11 strings.

Thus, print 11.

Sample Input 2

5
a
aa
aaa
aaaa
aaaaa

Sample Output 2

7

The possible strings are aaa, aaaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaa, aaaaaaaaa, which are 7 strings.

Thus, print 7.

Sample Input 3

10
armiearggc
ukupaunpiy
cogzmjmiob
rtwbvmtruq
qapfzsitbl
vhkihnipny
ybonzypnsn
esxvgoudra
usngxmaqpt
yfseonwhgp

Sample Output 3

90

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

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9
• A_i \neq B_i
• All values in the input are integers.

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

Problem Statement

There is a grid with 10^9 rows and W columns. The cell at the x-th column from the left and the y-th row from the bottom is denoted by (x,y).

There are N blocks. Each block is a 1 \times 1 square, and block i-th (1 \leq i \leq N) is located at cell (X_i,Y_i) at time 0.

At times t=1,2,\dots,10^{100}, the blocks are moved according to the following rules:

• If the entire bottom row is filled with blocks, then all blocks in the bottom row are removed.
• For each remaining block, in order from bottom to top, perform the following:
  • If the block is in the bottom row, or if there is a block in the cell immediately below it, do nothing.
  • Otherwise, move the block one cell downward.

You are given Q queries. For the j-th query (1 \leq j \leq Q), answer whether block A_j exists at time T_j+0.5.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W \leq N
• 1 \leq X_i \leq W
• 1 \leq Y_i \leq 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq T_j \leq 10^9
• 1 \leq A_j \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes
No
Yes
No
Yes

The positions of the blocks change as follows: ("時刻" means "time.")

• Query 1: At time 1.5, block 1 exists, so the answer is Yes.
• Query 2: At time 1.5, block 2 exists, so the answer is Yes.
• Query 3: Block 3 disappears at time 2, so it does not exist at time 2.5, and the answer is No.

Sample Input 2

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

Sample Output 2

No
No
Yes
Yes

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and an integer K.
There are 2^{N-1} ways to divide A into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to K? Find the count modulo 998244353.

Here, "to divide A into several contiguous subsequences" means the following procedure.

• Freely choose the number k (1 \leq k \leq N) of subsequences and an integer sequence (i_1, i_2, \dots, i_k, i_{k+1}) satisfying 1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1.
• For each 1 \leq n \leq k, the n-th subsequence is formed by taking the i_n-th through (i_{n+1} - 1)-th elements of A, maintaining their order.

Here are some examples of divisions for A = (1, 2, 3, 4, 5):

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

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^{15} \leq K \leq 10^{15}
• -10^9 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

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

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

Sample Output 3

428

Problem Statement

There is a weighted simple directed graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge has a weight of W_i and extends from vertex U_i to vertex V_i. The weights can be negative, but the graph does not contain negative cycles.

Determine whether there is a walk that visits each vertex at least once. If such a walk exists, find the minimum total weight of the edges traversed. If the same edge is traversed multiple times, the weight of that edge is added for each traversal.

Here, "a walk that visits each vertex at least once" is a sequence of vertices v_1,v_2,\dots,v_k that satisfies both of the following conditions:

• For every i (1\leq i\leq k-1), there is an edge extending from vertex v_i to vertex v_{i+1}.
• For every j\ (1\leq j\leq N), there is i (1\leq i\leq k) such that v_i=j.

Constraints

• 2\leq N \leq 20
• 1\leq M \leq N(N-1)
• 1\leq U_i,V_i \leq N
• U_i \neq V_i
• (U_i,V_i) \neq (U_j,V_j) for i\neq j
• -10^6\leq W_i \leq 10^6
• The given graph does not contain negative cycles.
• All input values are integers.

Sample Input 1

3 4
1 2 5
2 1 -3
2 3 -4
3 1 100

Sample Output 1

-2

By following the vertices in the order 2\rightarrow 1\rightarrow 2\rightarrow 3, you can visit all vertices at least once, and the total weight of the edges traversed is (-3)+5+(-4)=-2. This is the minimum.

Sample Input 2

3 2
1 2 0
2 1 0

Sample Output 2

No

There is no walk that visits all vertices at least once.

Sample Input 3

5 9
1 2 -246288
4 5 -222742
3 1 246288
3 4 947824
5 2 -178721
4 3 -947824
5 4 756570
2 5 707902
5 1 36781

Sample Output 3

-449429