Problem Statement

From the point (0,0) in a two-dimensional plane, let us move the distance of 1 toward the point (A, B). Find our coordinates after the move.

Here, after moving the distance of d from a point X to a point Y (d \le length of the segment XY), we are at the point on the segment XY whose distance from X is d.
The Constraints guarantee that the distance between the points (0, 0) and (A, B) is at least 1.

Constraints

• All values in input are integers.
• 0 \le A,B \le 1000
• (A,B) \neq (0,0)

Sample Input 1

3 4

Sample Output 1

0.600000000000 0.800000000000

Printing 0.5999999999 0.8000000001, for example, would also be accepted.

Sample Input 2

1 0

Sample Output 2

1.000000000000 0.000000000000

We may arrive at (A, B).

Sample Input 3

246 402

Sample Output 3

0.521964870245 0.852966983083

Problem Statement

There are 7 points A, B, C, D, E, F, and G on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.

• Between A and B: 3
• Between B and C: 1
• Between C and D: 4
• Between D and E: 1
• Between E and F: 5
• Between F and G: 9

You are given two uppercase English letters p and q. Each of p and q is A, B, C, D, E, F, or G, and it holds that p \neq q.
Find the distance between the points p and q.

Constraints

• Each of p and q is A,B,C,D,E,F, or G.
• p \neq q

Sample Input 1

A C

Sample Output 1

4

The distance between the points A and C is 3 + 1 = 4.

Sample Input 2

G B

Sample Output 2

20

The distance between the points G and B is 9 + 5 + 1 + 4 + 1 = 20.

Sample Input 3

C F

Sample Output 3

10

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

• Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
• Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

• 1 \leq N \leq 10
• 1 \leq X \leq 5
• 1 \leq Y \leq 5
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

12

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

• First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
  • After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
• Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
  • After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
• He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

0

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

Given a sequence of N positive integers A=(A_1,A_2,\dots,A_N), find every integer k between 1 and M (inclusive) that satisfies the following condition:

• \gcd(A_i,k)=1 for every integer i such that 1 \le i \le N.

Constraints

• All values in input are integers.
• 1 \le N,M \le 10^5
• 1 \le A_i \le 10^5

Sample Input 1

3 12
6 1 5

Sample Output 1

3
1
7
11

For example, 7 has the properties \gcd(6,7)=1,\gcd(1,7)=1,\gcd(5,7)=1, so it is included in the set of integers satisfying the requirement.
On the other hand, 9 has the property \gcd(6,9)=3, so it is not included in that set.
We have three integers between 1 and 12 that satisfy the condition: 1, 7, and 11. Be sure to print them in ascending order.