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.

Problem Statement

There is a field divided into a grid of H rows and W columns.
The square at the i-th row from the north (top) and the j-th column from the west (left) is represented by the character A_{i, j}. Each character represents the following.

• . : An empty square. Passable.
• # : An obstacle. Impassable.
• >, v, <, ^ : Squares with a person facing east, south, west, and north, respectively. Impassable. The person's line of sight is one square wide and extends straight in the direction the person is facing, and is blocked by an obstacle or another person. (See also the description at Sample Input/Output 1.)
• S : The starting point. Passable. There is exactly one starting point. It is guaranteed not to be in a person's line of sight.
• G : The goal. Passable. There is exactly one goal. It is guaranteed not to be in a person's line of sight.

Naohiro is at the starting point and can move one square to the east, west, south, and north as many times as he wants. However, he cannot enter an impassable square or leave the field.
Determine if he can reach the goal without entering a person's line of sight, and if so, find the minimum number of moves required to do so.

Constraints

• 2 \leq H, W \leq 2000
• A_{i,j} is ., #, >, v, <, ^, S, or G.
• Each of S and G occurs exactly once among A_{i, j}.
• Neither the starting point nor the goal is in a person's line of sight.

Sample Input 1

5 7
....Sv.
.>.....
.......
>..<.#<
^G....>

Sample Output 1

15

For Sample Input 1, the following figure shows the empty squares that are in the lines of sight of one or more people as !.

Let us describe some of the squares. (Let (i, j) denote the square in the i-th row from the north and the j-th column from the west.)

• (2, 4) is a square in the line of sight of the east-facing person at (2, 2).
• (2, 6) is a square in the lines of sight of two people, one facing east at (2, 2) and the other facing south at (1, 6).
• The square (4, 5) is not in anyone's line of sight. The line of sight of the west-facing person at (4, 7) is blocked by the obstacle at (4, 6), and the line of sight of the east-facing person at (4, 1) is blocked by the person at (4, 4).

Naohiro must reach the goal without passing through impassable squares or squares in a person's line of sight.

Sample Input 2

4 3
S..
.<.
.>.
..G

Sample Output 2

-1

Print -1 if he cannot reach the goal.

Problem Statement

Takahashi and a cargo are on a coordinate plane.

Takahashi is currently at (X_A,Y_A), and the cargo is at (X_B,Y_B). He wants to move the cargo to (X_C,Y_C).

When he is at (x,y), he can make one of the following moves in a single action.

• Move to (x+1,y). If the cargo is at (x+1,y) before the move, move it to (x+2,y).
• Move to (x-1,y). If the cargo is at (x-1,y) before the move, move it to (x-2,y).
• Move to (x,y+1). If the cargo is at (x,y+1) before the move, move it to (x,y+2).
• Move to (x,y-1). If the cargo is at (x,y-1) before the move, move it to (x,y-2).

Find the minimum number of actions required to move the cargo to (X_C,Y_C).

Constraints

• -10^{17}\leq X_A,Y_A,X_B,Y_B,X_C,Y_C\leq 10^{17}
• (X_A,Y_A)\neq (X_B,Y_B)
• (X_B,Y_B)\neq (X_C,Y_C)
• All input values are integers.

Sample Input 1

1 2 3 3 0 5

Sample Output 1

9

Takahashi can move the cargo to (0,5) in nine actions as follows.

• Move to (2,2).
• Move to (3,2).
• Move to (3,3). The cargo moves to (3,4).
• Move to (3,4). The cargo moves to (3,5).
• Move to (4,4).
• Move to (4,5).
• Move to (3,5). The cargo moves to (2,5).
• Move to (2,5). The cargo moves to (1,5).
• Move to (1,5). The cargo moves to (0,5).

It is impossible to move the cargo to (0,5) in eight or fewer actions, so you should print 9.

Sample Input 2

0 0 1 0 -1 0

Sample Output 2

6

Sample Input 3

-100000000000000000 -100000000000000000 100000000000000000 100000000000000000 -100000000000000000 -100000000000000000

Sample Output 3

800000000000000003