Problem Statement

Does 2^n \gt n^2 hold?

Constraints

• n is an integer between 1 and 10^9 (inclusive).

Sample Input 1

5

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

Problem Statement

Print how many distinct integers there are in given five integers A, B, C, D, and E.

Constraints

• 0 \leq A, B, C, D, E \leq 100
• All values in input are integers.

Sample Input 1

31 9 24 31 24

Sample Output 1

3

In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.

Sample Input 2

0 0 0 0 0

Sample Output 2

1

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

• 2 \leq N \leq 100
• -1000 \leq x_i,y_i \leq 1000
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 0
0 1
1 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

5
315 271
-2 -621
-205 -511
-952 482
165 463

Sample Output 2

1455.7159750446

Problem Statement

There are N birds of M types flying in the sky.
The bird types are numbered 1,2,\dots,M.
The N birds are numbered 1,2,\dots,N, and bird i is of type A_i and has size B_i.

For every k=1,2,\dots,M, find the average size of the flying birds of type k.
It is guaranteed that for every k=1,2,\dots,M, there is at least one bird of type k flying.

Constraints

• 1 \le M \le N \le 100
• 1 \le A_i \le M
• 1 \le B_i \le 100
• There exists at least one bird of type k ( 1 \le k \le M ).
• All input values are integers.

Sample Input 1

10 5
4 92
1 16
3 77
4 99
2 89
3 8
1 40
5 56
1 40
4 77

Sample Output 1

32.00000000000000000000
89.00000000000000000000
42.50000000000000000000
89.33333333333333333333
56.00000000000000000000

• The average size of birds of type 1 is (16+40+40)/3 = 32.
• The average size of birds of type 2 is 89.
• The average size of birds of type 3 is (77+8)/2 = 42.5.
• The average size of birds of type 4 is (92+99+77)/3 \approx 89.3333.
• The average size of birds of type 5 is 56.

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le W \le 3 \times 10^8
• 1 \le A_i \le 10^9
• 1 \le B_i \le 1000

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

Problem Statement

There are N types of chemicals 1,2,\dots,N. Your goal is to create a state where all of them are mixed.
You are given a string S of length 2^N-1 consisting of 0 and 1, which represents the following information:

• First, define state i (1 \le i \le 2^N-1) where one or more types of chemicals are mixed as follows:
  • When the k-th digit (1 \le k \le N) from the bottom in the binary representation of i is 1, and only then, chemical k is included.
  • For example, 13 in binary is 1101_{(2)}, so state 13 represents a state where chemicals 1,3,4 are mixed.
• When the i-th character of S is 0, state i is safe.
• When the i-th character of S is 1, state i is dangerous.

You mix chemicals using the following operation:

• First, prepare an empty bottle.
• Next, repeat the following:
  • Choose one type of chemical that has not yet been poured into the bottle and pour it into the bottle.
  • At this time, the chemicals mixed in the bottle must not be in a dangerous state.

Determine whether this operation can create a state where all chemicals are mixed.

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

Constraints

• T is an integer between 1 and 40000, inclusive.
• N is an integer between 1 and 18, inclusive.
• S is a string of length 2^N-1 consisting of 0 and 1.
• The sum of |S| = 2^N-1 in each input does not exceed 5 \times 10^5.

Sample Input 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

Sample Output 1

Yes
No
No
Yes
Yes

This input contains five test cases.

The 1st case is as follows:

• There are three types of chemicals.
• Only state 3 where chemicals 1,2 are mixed is dangerous, and the other states are safe.
• For example, you can create a state where all chemicals are mixed with the following procedure:
  • First, pour chemical 2 into the bottle. Only chemical 2 is mixed in the bottle, which is state 2, so it is safe.
  • Next, pour chemical 3 into the bottle. Chemicals 2,3 are mixed in the bottle, which is state 6, so it is safe.
  • Finally, pour chemical 1 into the bottle. Chemicals 1,2,3 are mixed in the bottle, which is state 7, so it is safe.

The 2nd case is as follows:

• There are three types of chemicals.
• State 3 where chemicals 1,2 are mixed, state 5 where chemicals 1,3 are mixed, and state 6 where chemicals 2,3 are mixed are dangerous, and the other states are safe.
• For this case, it is impossible to create a state where all chemicals are mixed.

The 3rd case is as follows:

• There is one type of chemical.
• Since state 1 where only chemical 1 is mixed is dangerous, it is impossible to create a state where all chemicals are mixed.

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

Takahashi and Aoki walk on a two-dimensional plane.

Takahashi's start point is (TS_X, TS_Y) and goal point is (TG_X, TG_Y). Aoki's start point is (AS_X, AS_Y) and goal point is (AG_X, AG_Y).

They simultaneously depart from their respective start points and walk straight toward their respective goal points at speed 1, and stop when they reach their respective goal points. (Note that they depart simultaneously, but they do not necessarily stop at the same time.)

Find the distance between them at the moment when the distance between them is shortest (including the moment they depart and after they stop).

Here, distance refers to Euclidean distance. That is, the distance between two points (x_1,y_1),(x_2,y_2) is defined as \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

You are given T test cases, so solve each of them.

Constraints

• 1\leq T\leq 2\times 10^5
• -100\leq TS_X,TS_Y,TG_X,TG_Y,AS_X,AS_Y,AG_X,AG_Y \leq 100
• (TS_X,TS_Y)\neq (TG_X,TG_Y)
• (AS_X,AS_Y)\neq (AG_X,AG_Y)
• All input values are integers.

Sample Input 1

4
0 0 -2 2
-1 -1 4 4
4 0 2 0
6 0 8 0
1 0 1 1
-1 0 1 1
-8 9 2 6
-10 -10 17 20

Sample Output 1

1.000000000000000
2.000000000000000
0.000000000000000
1.783905950993199

For the first test case, let time 0 be the moment they depart. Their behavior is as follows:

• Time 0: Takahashi departs from (0,0) and starts walking toward (-2,2) at speed 1. At the same time, Aoki departs from (-1,-1) and starts walking toward (4,4) at speed 1.
• Time 2\sqrt{2}: Takahashi reaches his goal point (-2,2) and stops. At this time, Aoki is at (1,1) and is still walking.
• Time 5\sqrt{2}: Aoki reaches his goal point (4,4) and stops.

The distance between them is shortest at time \frac{1}{\sqrt{2}}, when Takahashi and Aoki are at (-\frac{1}{2},\frac{1}{2}) and (-\frac{1}{2},-\frac{1}{2}) respectively, and the distance is 1.

For the second test case, the distance between them is shortest at the moment they depart, and the distance at that time is 2.

For the third test case, the distance between them is shortest after they both stop, and the distance at that time is 0.

Problem Statement

There is an empty array A. For i = 1,2,\ldots,N, perform the following operation in order:

• Insert the number i into A so that it becomes the P_i-th element from the beginning.
  • More precisely, replace A with the concatenation of the first P_i-1 elements of A, then i, then the remaining elements of A starting from the P_i-th element, in this order.

Output the final array A after all operations have been completed.

Constraints

• 1 \leq N \leq 5\times 10^5
• 1 \leq P_i \leq i
• All input values are integers.

Sample Input 1

4
1 1 2 1

Sample Output 1

4 2 3 1

The operations are performed as follows:

• Insert the number 1 so that it becomes the 1st element of A. Now, A = (1).
• Insert the number 2 so that it becomes the 1st element of A. Now, A = (2, 1).
• Insert the number 3 so that it becomes the 2nd element of A. Now, A = (2, 3, 1).
• Insert the number 4 so that it becomes the 1st element of A. Now, A = (4, 2, 3, 1).

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5