Problem Statement

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

• the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

• 1 \leq A,B,C,D,E\leq 13
• Not all of A, B, C, D, and E are the same.
• All values in input are integers.

Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.

Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

Problem Statement

There are N people, called Person 1, Person 2, \ldots, Person N.

The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.

How many generations away from Person N is Person 1?

Constraints

• 2 \le N \le 50
• 1 \le P_i < i(2 \le i \le N)
• All values in input are integers.

Sample Input 1

3
1 2

Sample Output 1

2

Person 2 is a parent of Person 3, and thus is one generation away from Person 3.

Person 1 is a parent of Person 2, and thus is two generations away from Person 3.

Therefore, the answer is 2.

Sample Input 2

10
1 2 3 4 5 6 7 8 9

Sample Output 2

9

Problem Statement

Print all strictly increasing integer sequences of length N where all elements are between 1 and M (inclusive), in lexicographically ascending order.

Notes

For two integer sequences of the same length A_1,A_2,\dots,A_N and B_1,B_2,\dots,B_N, A is said to be lexicographically earlier than B if and only if:

• there is an integer i (1 \le i \le N) such that A_j=B_j for all integers j satisfying 1 \le j < i, and A_i < B_i.

An integer sequence A_1,A_2,\dots,A_N is said to be strictly increasing if and only if:

• A_i < A_{i+1} for all integers i (1 \le i \le N-1).

Constraints

• 1 \le N \le M \le 10
• All values in input are integers.

Sample Input 1

2 3

Sample Output 1

1 2 
1 3 
2 3 

The sought sequences are (1,2),(1,3),(2,3), which should be printed in lexicographically ascending order.

Sample Input 2

3 5

Sample Output 2

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

Problem Statement

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

You will perform the following consecutive operations just once:

• Choose an integer x (0\leq x \leq N). If x is 0, do nothing. If x is 1 or greater, replace each of A_1,A_2,\ldots,A_x with L.

• Choose an integer y (0\leq y \leq N). If y is 0, do nothing. If y is 1 or greater, replace each of A_{N},A_{N-1},\ldots,A_{N-y+1} with R.

Print the minimum possible sum of the elements of A after the operations.

Constraints

• 1 \leq N \leq 2\times 10^5
• -10^9 \leq L, R\leq 10^9
• -10^9 \leq A_i\leq 10^9
• All values in input are integers.

Sample Input 1

5 4 3
5 5 0 6 3

Sample Output 1

14

If you choose x=2 and y=2, you will get A = (4,4,0,3,3), for the sum of 14, which is the minimum sum achievable.

Sample Input 2

4 10 10
1 2 3 4

Sample Output 2

10

If you choose x=0 and y=0, you will get A = (1,2,3,4), for the sum of 10, which is the minimum sum achievable.

Sample Input 3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

Sample Output 3

-58

L, R, and A_i may be negative.

Problem Statement

There are N squares called Square 1 though Square N. You start on Square 1.

Each of the squares from Square 1 through Square N-1 has a die on it. The die on Square i is labeled with the integers from 0 through A_i, each occurring with equal probability. (Die rolls are independent of each other.)

Until you reach Square N, you will repeat rolling a die on the square you are on. Here, if the die on Square x rolls the integer y, you go to Square x+y.

Find the expected value, modulo 998244353, of the number of times you roll a die.

Notes

It can be proved that the sought expected value is always a rational number. Additionally, if that value is represented \frac{P}{Q} using two coprime integers P and Q, there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N-i(1 \le i \le N-1)
• All values in input are integers.

Sample Input 1

3
1 1

Sample Output 1

4

The sought expected value is 4, so 4 should be printed.

Here is one possible scenario until reaching Square N:

• Roll 1 on Square 1, and go to Square 2.
• Roll 0 on Square 2, and stay there.
• Roll 1 on Square 2, and go to Square 3.

This scenario occurs with probability \frac{1}{8}.

Sample Input 2

5
3 1 2 1

Sample Output 2

332748122

Problem Statement

2^N people, numbered 1 to 2^N, will participate in a rock-paper-scissors tournament.

The tournament proceeds as follows:

• The participants are arranged in a row in the order Person 1, Person 2, \ldots, Person 2^N from left to right.
• Let 2M be the current length of the row. For each i\ (1\leq i \leq M), the (2i-1)-th and (2i)-th persons from the left play a game against each other. Then, the M losers are removed from the row. This process is repeated N times.

Here, if Person i wins exactly j games, they receive C_{i,j} yen (Japanese currency). A person winning zero games receives nothing. Find the maximum possible total amount of money received by the 2^N people if the results of all games can be manipulated freely.

Constraints

• 1 \leq N \leq 16
• 1 \leq C_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2
2 5
6 5
2 1
7 9

Sample Output 1

15

The initial row of the people is (1,2,3,4).

If Person 2 wins the game against Person 1, and Person 4 wins the game against Person 3, the row becomes (2,4).

Then, if Person 4 wins the game against Person 2, the row becomes (4), and the tournament ends.

Here, Person 2 wins exactly 1 game, and Person 4 wins exactly 2 games, so they receive 0+6+0+9=15 yen in total, which is the maximum possible sum.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 2

4

Problem Statement

There are integers with N different values written on a blackboard. The i-th value is A_i and is written B_i times.

You may repeat the following operation as many times as possible:

• Choose two integers x and y written on the blackboard such that x+y is prime. Erase these two integers.

Find the maximum number of times the operation can be performed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^7
• 1 \leq B_i \leq 10^9
• All A_i are distinct.
• All values in input are integers.

Sample Input 1

3
3 3
2 4
6 2

Sample Output 1

3

We have 2 + 3 = 5, and 5 is prime, so you can choose 2 and 3 to erase them, but nothing else. Since there are four 2s and three 3s, you can do the operation three times.

Sample Input 2

1
1 4

Sample Output 2

2

We have 1 + 1 = 2, and 2 is prime, so you can choose 1 and 1 to erase them. Since there are four 1s, you can do the operation twice.

Problem Statement

There are N lines in a two-dimensional plane. The i-th line is A_i x + B_i y + C_i = 0. It is guaranteed that no two of the lines are parallel.

In this plane, there are \frac{N(N-1)}{2} intersection points of two lines, including duplicates. Print the distance between the origin and the K-th nearest point to the origin among these \frac{N(N-1)}{2} points.

Constraints

• 2 \le N \le 5 \times 10^4
• 1 \le K \le \frac{N(N-1)}{2}
• -1000 \le |A_i|,|B_i|,|C_i| \le 1000(1 \le i \le N)
• No two of the lines are parallel.
• A_i \neq 0 or B_i \neq 0(1 \le i \le N).
• All values in input are integers.

Sample Input 1

3 2
1 1 1
2 1 -3
1 -1 2

Sample Output 1

2.3570226040

Let us call the i-th line Line i.

• The intersection point of Line 1 and Line 2 is (4,-5), whose distance to the origin is \sqrt{41} \simeq 6.4031242374.
• The intersection point of Line 1 and Line 3 is (\frac{-3}{2},\frac{1}{2}), whose distance to the origin is \frac{\sqrt{10}}{2} \simeq 1.5811388300.
• The intersection point of Line 2 and Line 3 is (\frac{1}{3},\frac{7}{3}), whose distance to the origin is \frac{5\sqrt{2}}{3} \simeq 2.3570226040.

Therefore, the second nearest intersection point is (\frac{1}{3},\frac{7}{3}), and \frac{5\sqrt{2}}{3} should be printed.

Sample Input 2

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

Sample Output 2

4.0126752298