Problem Statement

There is a row of N people. They are described by a string S of length N. The i-th person from the front is male if the i-th character of S is M, and female if it is F.

Determine whether the men and women are alternating.

It is said that the men and women are alternating if and only if there is no position where two men or two women are adjacent.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is a string of length N consisting of M and F.

Sample Input 1

6
MFMFMF

Sample Output 1

Yes

There is no position where two men or two women are adjacent, so the men and women are alternating.

Sample Input 2

9
FMFMMFMFM

Sample Output 2

No

Sample Input 3

1
F

Sample Output 3

Yes

Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

• 2 \leq N \leq 2\times 10^5
• -10^9 \leq A_i \leq 10^9
• -10^9 \leq X \leq 10^9
• All values in the input are integers.

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.

Problem Statement

You are given positive integers N and M.
Find the smallest positive integer X that satisfies both of the conditions below, or print -1 if there is no such integer.

• X can be represented as the product of two integers a and b between 1 and N, inclusive. Here, a and b may be the same.
• X is at least M.

Constraints

• 1\leq N\leq 10^{12}
• 1\leq M\leq 10^{12}
• N and M are integers.

Sample Input 1

5 7

Sample Output 1

8

First, 7 cannot be represented as the product of two integers between 1 and 5.
Second, 8 can be represented as the product of two integers between 1 and 5, such as 8=2\times 4.

Thus, you should print 8.

Sample Input 2

2 5

Sample Output 2

-1

Since 1\times 1=1, 1\times 2=2, 2\times 1=2, and 2\times 2=4, only 1, 2, and 4 can be represented as the product of two integers between 1 and 2, so no number greater than or equal to 5 can be represented as the product of two such integers.
Thus, you should print -1.

Sample Input 3

100000 10000000000

Sample Output 3

10000000000

For a=b=100000 (=10^5), the product of a and b is 10000000000 (=10^{10}), which is the answer.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

You are given a sequence of N numbers: A=(A_1,A_2,\ldots,A_N). Here, each A_i (1\leq i\leq N) satisfies 1\leq A_i \leq N.

Takahashi and Aoki will play N rounds of a game. For each i=1,2,\ldots,N, the i-th game will be played as follows.

1. Aoki specifies a positive integer K_i.
2. After knowing K_i Aoki has specified, Takahashi chooses an integer S_i between 1 and N, inclusive, and writes it on a blackboard.

3. Repeat the following K_i times.

   • Replace the integer x written on the blackboard with A_x.

If i is written on the blackboard after the K_i iterations, Takahashi wins the i-th round; otherwise, Aoki wins.
Here, K_i and S_i can be chosen independently for each i=1,2,\ldots,N.

Find the number of rounds Takahashi wins if both players play optimally to win.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A_i\leq N
• All values in the input are integers.

Sample Input 1

3
2 2 3

Sample Output 1

2

In the first round, if Aoki specifies K_1=2, Takahashi cannot win whichever option he chooses for S_1: 1, 2, or 3.

For example, if Takahashi writes S_1=1 on the initial blackboard, the two operations will change this number as follows: 1\to 2(=A_1), 2\to 2(=A_2). The final number on the blackboard will be 2(\neq 1), so Aoki wins.

On the other hand, in the second and third rounds, Takahashi can win by writing 2 and 3, respectively, on the initial blackboard, whatever value Aoki specifies as K_i.

Therefore, if both players play optimally to win, Takashi wins two rounds: the second and the third. Thus, you should print 2.

Sample Input 2

2
2 1

Sample Output 2

2

In the first round, Takahashi can win by writing 2 on the initial blackboard if K_1 specified by Aoki is odd, and 1 if it is even.

Similarly, there is a way for Takahashi to win the second round. Thus, Takahashi can win both rounds: the answer is 2.

Problem Statement

You are given two sequences of N numbers: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

Takahashi can repeat the following operation any number of times (possibly zero).

Choose three pairwise distinct integers i, j, and k between 1 and N.
Swap the i-th and j-th elements of A, and swap the i-th and k-th elements of B.

If there is a way for Takahashi to repeat the operation to make A and B equal, print Yes; otherwise, print No.
Here, A and B are said to be equal when, for every 1\leq i\leq N, the i-th element of A and that of B are equal.

Constraints

• 3 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• All values in the input are integers.

Sample Input 1

3
1 2 1
1 1 2

Sample Output 1

Yes

Performing the operation once with (i,j,k)=(1,2,3) swaps A_1 and A_2, and swaps B_1 and B_3,
making both A and B equal to (2,1,1). Thus, you should print Yes.

Sample Input 2

3
1 2 2
1 1 2

Sample Output 2

No

There is no way to perform the operation to make A and B equal, so you should print No.

Sample Input 3

5
1 2 3 2 1
3 2 2 1 1

Sample Output 3

Yes

Sample Input 4

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

Sample Output 4

No

Problem Statement

There is a convex N-gon S in the two-dimensional coordinate plane where the positive x-axis points to the right and the positive y-axis points upward. The vertices of S have the coordinates (X_1,Y_1),\ldots,(X_N,Y_N) in counter-clockwise order.

For each of Q points (A_i,B_i), answer the following question: is that point inside or outside or on the boundary of S?

Constraints

• 3 \leq N \leq 2\times 10^5
• 1 \leq Q \leq 2\times 10^5
• -10^9 \leq X_i,Y_i,A_i,B_i \leq 10^9
• S is a strictly convex N-gon. That is, its interior angles are all less than 180 degrees.
• (X_1,Y_1),\ldots,(X_N,Y_N) are the vertices of S in counter-clockwise order.
• All values in the input are integers.

Sample Input 1

4
0 4
-2 2
-1 0
3 1
3
-1 3
0 2
2 0

Sample Output 1

ON
IN
OUT

The figure below shows S and the given three points. The first point is on the boundary of S, the second is inside S, and the third is outside S.

Sample Input 2

3
0 0
1 0
0 1
3
0 0
1 0
0 1

Sample Output 2

ON
ON
ON

Problem Statement

We have a grid with N rows and M columns, where each square is painted black or white. Here, at least one square is painted black.
The initial state of the grid is given as N strings S_1,S_2,\ldots,S_N of length M.
The square at the i-th row from the top and j-th column from the left is painted black if the j-th character of S_i is #, and white if it is ..

Takahashi wants to repaint some white squares (possibly zero) black so that the squares painted black are connected. Find the minimum number of squares he needs to repaint to achieve his objective.

Here, the squares painted black are said to be connected when, for every pair of squares (S,T) painted black, there are a positive integer K and a sequence of K squares X=(x_1,x_2,\ldots,x_K) painted black such that x_1=S, x_K=T, and x_i and x_{i+1} share a side for every 1\leq i\leq K-1.
It can be proved that, under the constraints of the problem, there is always a way for Takahashi to achieve his objective.

Constraints

• 1 \leq N \leq 100
• 1\leq M \leq 7
• N and M are integers.
• S_i is a string of length M consisting of # and ..
• The given grid has at least one square painted black.

Sample Input 1

3 5
...#.
.#...
....#

Sample Output 1

3

The initial grid looks as follows, where (i,j) denotes the square at the i-th row from the top and j-th column from the left.

Assume that Takahashi repaints three squares (2,3),(2,4),(3,4) (shown red in the figure below) black.

Then, we have the following squares painted black, including the ones painted black from the beginning. These squares are connected.

It is impossible to repaint two or fewer squares black so that the squares painted black are connected, so the answer is 3.
Note that the squares painted white do not have to be connected.

Sample Input 2

3 3
###
###
###

Sample Output 2

0

All squares might be painted black from the beginning.

Sample Input 3

10 1
.
#
.
.
.
.
.
.
#
.

Sample Output 3

6