Problem Statement

There is an image with a width of X pixels and a height of Y pixels. Determine whether the ratio of the width to the height is 16 to 9, that is, whether X:Y=16:9.

Constraints

• 1 \leq X \leq 1000
• 1 \leq Y \leq 1000
• All input values are integers.

Sample Input 1

800 450

Sample Output 1

Yes

For an image with a width of 800 pixels and a height of 450 pixels, the ratio of the width to the height is 16 to 9.

Sample Input 2

234 108

Sample Output 2

No

For an image with a width of 234 pixels and a height of 108 pixels, the ratio of the width to the height is not 16 to 9.

Sample Input 3

108 192

Sample Output 3

No

For an image with a width of 108 pixels and a height of 192 pixels, the ratio of the width to the height is not 16 to 9.

Problem Statement

Takahashi is trying to reserve a seat on a train.

There are N trains he is considering as candidates for reservation, numbered 1, 2, \dots, N. Each train has seats in five columns, called column A, column B, column C, column D, and column E.

The current seat availability information for each train is given as strings S_1, S_2, \dots, S_N. Here, S_1, S_2, \dots, S_N all have length 5, and columns A through E of train i correspond to the first through fifth characters of S_i, respectively. If that character is o, there is a vacant seat in the corresponding column; if it is x, there is no vacant seat in the corresponding column.

Takahashi wants to reserve a seat in column X, where X is one of A, B, C, D, E. Determine whether there is a vacant seat in column X on at least one train.

Constraints

• N is an integer between 1 and 100, inclusive.
• X is one of A, B, C, D, E.
• S_i is a string of length 5 consisting of o and x.

Sample Input 1

3 A
xoxox
xxooo
oxxxx

Sample Output 1

Yes

Train 3 has a vacant seat in column A. Thus, output Yes.

Sample Input 2

5 C
xoxoo
oxxoo
oxxxo
xoxxx
oxxoo

Sample Output 2

No

No train has a vacant seat in column C. Thus, output No.

Problem Statement

Currently, there are N Takahashi in a conference room. The i-th (1\le i\le N) Takahashi has a height of H _ i and will leave the room L _ i minutes from now. Once a Takahashi leaves the room, he never returns.

You are given Q queries, so answer them in order. For the i-th (1\le i\le Q) query, you are given an integer T _ i, so find the maximum height among the Takahashi who are in the room T _ i+\dfrac12 minutes from now. Under the constraints of this problem, it is guaranteed that at least one Takahashi will be in the room T _ i+\dfrac12 minutes from now.

Constraints

• 1\le N\le3\times10 ^ 5
• 1\le H _ i\le10 ^ 9\ (1\le i\le N)
• 1\le L _ 1\le L _ 2\le\cdots\le L _ N\le10 ^ 9
• 1\le Q\le3\times10 ^ 5
• 0\le T _ i\lt L _ N\ (1\le i\le Q)
• All input values are integers.

Sample Input 1

4
31 4
26 5
3 5
15 9
4
3 4 5 6

Sample Output 1

31
26
15
15

3+\dfrac12 minutes from now, all Takahashi currently in the room are still there. Thus, the answer to the first query is 31, the maximum of \lbrace31,26,3,15\rbrace.

5+\dfrac12 minutes from now, only the fourth Takahashi is in the room. Thus, the answer to the third query is 15, the maximum of \lbrace15\rbrace.

Sample Input 2

10
587 138
772 155
755 404
519 408
529 432
169 586
114 632
249 656
329 972
299 984
14
443 801 824 276 399 314 300 510 311 580 498 930 359 5

Sample Output 2

329
329
329
755
755
755
755
329
755
329
329
329
755
772

Problem Statement

There are N cloths on a number line. The i-th (1\le i\le N) cloth covers the interval \lbrack L _ i,R _ i\rbrack on the line. A point on the line may be covered by two or more cloths, or not covered by any cloth.

Two cloths are said to overlap if some point on the line is covered by both of those cloths.

For two cloths that do not overlap, define their distance as follows:

• The minimum value of |p-q| over all points p covered by one cloth and all points q covered by the other cloth.

For K cloths no two of which overlap, define their score as the minimum distance among all pairs of those cloths. Find the maximum possible score when choosing K cloths from the N cloths so that no two of the chosen cloths overlap.

If it is impossible to choose K such cloths, output -1.

Constraints

• 2\le K\le N\le2\times10 ^ 5
• 0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)
• All input values are integers.

Sample Input 1

6 3
1 12
2 7
5 9
9 13
10 18
15 20

Sample Output 1

2

Choosing the second, fourth, and sixth cloths, no two of these overlap. The distance between the second and fourth cloths is 2, the distance between the second and sixth cloths is 8, and the distance between the fourth and sixth cloths is 2, so the score of this choice is 2.

It is impossible to choose three cloths with a score of 3 or more, so output 2.

Sample Input 2

2 2
1 5
5 9

Sample Output 2

-1

The given two cloths overlap, so it is impossible to choose two cloths so that no two overlap. Thus, output -1.

Note that the first and second cloths overlap only at the single point 5.

Sample Input 3

20 5
169 748
329 586
529 972
432 520
408 587
138 250
114 656
299 632
755 984
404 772
155 506
832 854
353 465
374 387
384 567
555 631
428 951
104 705
405 530
102 258

Sample Output 3

35

Problem Statement

The country of AtCoder has N cities and M roads. The i-th road (1\le i\le M) connects cities u _ i and v _ i bidirectionally, and allows travel from one to the other in T _ i minutes.

Additionally, each city has a warp gate installed, and you can travel from city i\ (1\le i\le N) to city j\ (1\le j\le N) using the warp gate in X _ i+X _ j+Y minutes.

There are no other ways to travel between cities in the country.

For each k=2,3,\ldots,N, solve the following problem:

• Find the minimum time required to travel from city 1 to city k.

The time required to transfer from a road or warp gate to another road or warp gate at the same city is negligible.

Constraints

• 2\le N\le2\times10 ^ 5
• 0\le M\le2\times10 ^ 5
• 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
• 1\le T _ i\le10 ^ 9\ (1\le i\le M)
• 1\le X _ i\le10 ^ 9\ (1\le i\le N)
• 1\le Y\le 10 ^ 9
• All input values are integers.

Sample Input 1

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

Sample Output 1

1 5 6 8 14 7

For example, you can travel from city 1 to city 7 in 7 minutes as follows:

• Use the first road to travel from city 1 to city 2 in 1 minute.
• Use the warp gate to travel from city 2 to city 7 in 1+2+3=6 minutes.

It is impossible to travel from city 1 to city 7 in 6 minutes or less, so the answer for k=7 is 7.

Sample Input 2

2 0 1000000000
1000000000 1000000000

Sample Output 2

3000000000

Note that the answer may be 2 ^ {31} or greater.

Sample Input 3

12 20 873
2 7 940
6 9 444
6 11 809
7 8 786
9 10 468
7 10 234
6 10 660
4 12 939
8 10 896
1 11 953
8 10 818
4 8 967
3 9 724
6 7 929
3 4 948
1 3 999
10 11 724
7 10 338
1 8 967
1 12 733
581 978 950 629 583 729 554 712 438 930 774 279

Sample Output 3

2432 999 1672 2037 1762 1753 967 1723 1677 953 733

Problem Statement

A tournament is being held with 2N players. From now on, each player will play exactly one match. In the remaining N matches, the i-th (1\le i\le N) match is played between the (2i-1)-th and 2i-th players.

In each match, one of the two competing players wins and the other loses. Which player wins is determined independently for each match, and each player wins with probability \dfrac12.

Before the last N matches begin, the i-th (1\le i\le2N) player has won A _ i times. After all matches are over, the champion is chosen from among the players with the most wins, uniformly at random and independently of the previous match results.

For each of the first, second, \ldots, 2N-th players, find the probability, modulo 998244353, of that player becoming the champion.

Constraints

• 1\le N\le2\times10 ^ 5
• 0\le A _ i\lt2N\ (1\le i\le 2N)
• All input values are integers.

Sample Input 1

4
1 2
3 4
2 3
1 4

Sample Output 1

0 0 259959467 883862188 0 967049217 0 883862188

For example, the third player becomes the champion in the following cases:

• If the third player wins in the second match, the fifth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability \dfrac13.
• If the third player wins in the second match, the sixth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability \dfrac14.

Thus, the probability of the third player becoming the champion is \dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96}. We have 259959467\times96\equiv7\pmod{998244353}, so the probability of the third player becoming the champion in modulo-998244353 expression is 259959467.

The probability of each player becoming the champion is 0,0,\dfrac7{96},\dfrac{43}{96},0,\dfrac3{96},0,\dfrac{43}{96}. Thus, output 0 0 259959467 883862188 0 967049217 0 883862188.

Sample Input 2

6
0 0
0 0
0 0
0 0
0 0
0 0

Sample Output 2

582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206

It is possible that no one has won yet.

By symmetry, each player becomes the champion with probability \dfrac1{12}.

Sample Input 3

10
18 17
16 18
18 16
16 16
17 17
16 16
17 16
17 18
16 16
17 18

Sample Output 3

357877533 151989635 0 357877533 357877533 0 0 0 575116994 575116994 0 0 597386855 0 151989635 357877533 0 0 151989635 357877533

Problem Statement

You are given a positive integer N and an integer X.

Takahashi is at coordinate 0 on a number line. He will now perform the following move N times:

• When at coordinate x, choose coordinate x-1 or coordinate x+1 with equal probability and move there.

The choices of destination across the N moves are all independent. Let x' be the coordinate after all N moves. Find the expected value, modulo 998244353, of |x'-X|.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• |X| \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

5
3 2
6 4
2026 -620
12345 67890
98765 -43210

Sample Output 1

748683267
935854085
270602660
67890
844852181

For the first test case, Takahashi ends up at coordinate -3 with probability \frac{1}{8}, at coordinate -1 with probability \frac{3}{8}, at coordinate 1 with probability \frac{3}{8}, and at coordinate 3 with probability \frac{1}{8}. Thus, the expected value of |x'-X| is \frac{1}{8}\cdot|{-3}-2|+\frac{3}{8}\cdot|{-1}-2|+\frac{3}{8}\cdot|1-2|+\frac{1}{8}\cdot|3-2|=\frac{9}{4}.