Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq D \leq 100
• There is an arithmetic sequence with first term A, last term B, and common difference D.
• All input values are integers.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

10

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

Problem Statement

You are given a string S of length N consisting of three kinds of characters: ., |, and *. S contains exactly two | and exactly one *.

Determine whether the * is between the two |, and if so, print in; otherwise, print out.

More formally, determine whether one of the characters before the * is | and one of the characters after the * is |.

Constraints

• 3\leq N\leq 100
• N is an integer.
• S is a string of length N consisting of ., |, and *.
• S contains exactly two |.
• S contains exactly one *.

Sample Input 1

10
.|..*...|.

Sample Output 1

in

Between the two |, we have |..*...|, which contains *, so you should print in.

Sample Input 2

10
.|..|.*...

Sample Output 2

out

Between the two |, we have |..|, which does not contain *, so you should print out.

Sample Input 3

3
|*|

Sample Output 3

in

Problem Statement

We define Extended A strings, Extended B strings, Extended C strings, and Extended ABC strings as follows:

• A string S is an Extended A string if all characters in S are A.
• A string S is an Extended B string if all characters in S are B.
• A string S is an Extended C string if all characters in S are C.
• A string S is an Extended ABC string if there is an Extended A string S_A, an Extended B string S_B, and an Extended C string S_C such that the string obtained by concatenating S_A, S_B, S_C in this order equals S.

For example, ABC, A, and AAABBBCCCCCCC are Extended ABC strings, but ABBAAAC and BBBCCCCCCCAAA are not. Note that the empty string is an Extended A string, an Extended B string, and an Extended C string.

You are given a string S consisting of A, B, and C. If S is an Extended ABC string, print Yes; otherwise, print No.

Constraints

• S is a string consisting of A, B, and C.
• 1\leq|S|\leq 100 (|S| is the length of the string S.)

Sample Input 1

AAABBBCCCCCCC

Sample Output 1

Yes

AAABBBCCCCCCC is an Extended ABC string because it is a concatenation of an Extended A string of length 3, AAA, an Extended B string of length 3, BBB, and an Extended C string of length 7, CCCCCCC, in this order.

Thus, print Yes.

Sample Input 2

ACABABCBC

Sample Output 2

No

There is no triple of Extended A string S_A, Extended B string S_B, and Extended C string S_C such that the string obtained by concatenating S_A, S_B, and S_C in this order equals ACABABCBC.

Therefore, print No.

Sample Input 3

A

Sample Output 3

Yes

Sample Input 4

ABBBBBBBBBBBBBCCCCCC

Sample Output 4

Yes

Problem Statement

We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

You are given characters B_{i,j} representing the current states of (i,j). . represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.

At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.

Print the board after the explosions.

Constraints

• 1\leq R,C \leq 20
• R and C are integers.
• Each B_{i,j} is one of ., #, 1, 2, \dots, 9.

Sample Input 1

4 4
.1.#
###.
.#2.
#.##

Sample Output 1

...#
#...
....
#...

• The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
• The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.

As seen in this sample, the explosion ranges of bombs may overlap.

Sample Input 2

2 5
..#.#
###.#

Sample Output 2

..#.#
###.#

There may be no bombs.

Sample Input 3

2 3
11#
###

Sample Output 3

...
..#

Sample Input 4

4 6
#.#3#.
###.#.
##.###
#1..#.

Sample Output 4

......
#.....
#....#
....#.

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

The programming contest World Tour Finals is underway, where N players are participating, and half of the competition time has passed. There are M problems in this contest, and the score A_i of problem i is a multiple of 100 between 500 and 2500, inclusive.

For each i = 1, \ldots, N, you are given a string S_i that indicates which problems player i has already solved. S_i is a string of length M consisting of o and x, where the j-th character of S_i is o if player i has already solved problem j, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player i is calculated as the sum of the scores of the problems they have solved, plus a bonus score of i points.
For each i = 1, \ldots, N, answer the following question.

• At least how many of the problems that player i has not yet solved must player i solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player i can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

• 2\leq N\leq 100
• 1\leq M\leq 100
• 500\leq A_i\leq 2500
• A_i is a multiple of 100.
• S_i is a string of length M consisting of o and x.
• S_i contains at least one x.
• All numeric values in the input are integers.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are 2001 points for player 1, 1502 points for player 2, and 1703 points for player 3.

Player 1 is already ahead of all other players' total scores without solving any more problems.

Player 2 can, for example, solve problem 4 to have a total score of 3502 points, which would exceed all other players' total scores.

Player 3 can also, for example, solve problem 4 to have a total score of 3703 points, which would exceed all other players' total scores.

Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0

Problem Statement

Determine whether there is a way to line up N people, numbered 1 to N, in a row side by side to satisfy all of the M conditions in the following format.

• Condition: Person A_i and Person B_i are adjacent.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 1\leq A_i < B_i \leq N
• All pairs (A_i,B_i) are distinct.

Sample Input 1

4 2
1 3
2 3

Sample Output 1

Yes

One way to satisfy all the conditions is to line them up in the order 4,1,3,2.

Sample Input 2

4 3
1 4
2 4
3 4

Sample Output 2

No

There is no way to line them up to satisfy all the conditions.

Problem Statement

There are N cities. There are also one-way direct flights that connect different cities.
The availability of direct flights is represented by N strings S_1,S_2,\ldots,S_N of length N each. If the j-th character of S_i is Y, there is a direct flight from city i to city j; if it is N, there is not.
Each city sells a souvenir; city i sells a souvenir of value A_i.

Consider the following problem:

Takahashi is currently at city S and wants to get to city T (that is different from city S) using some direct flights.
Every time he visits a city (including S and T), he buys a souvenir there.
If there are multiple routes from city S to city T, Takahashi decides the route as follows:

• He tries to minimize the number of direct flights in the route from city S to city T.
• Then he tries to maximize the total value of the souvenirs he buys.

Determine if he can travel from city S to city T using the direct flights. If he can, find the "number of direct flights" and "total value of souvenirs" in the route that satisfies the conditions above.

You are given Q pairs (U_i,V_i) of distinct cities.
For each 1\leq i\leq Q, print the answer to the problem above when S=U_i and T=V_i.

Constraints

• 2 \leq N \leq 300
• 1\leq A_i\leq 10^9
• S_i is a string of length N consisting of Y and N.
• The i-th character of S_i is N.
• 1\leq Q\leq N(N-1)
• 1\leq U_i,V_i\leq N
• U_i\neq V_i
• If i \neq j, then (U_i,V_i)\neq (U_j,V_J).
• N,A_i,Q,U_i, and V_i are all integers.

Sample Input 1

5
30 50 70 20 60
NYYNN
NNYNN
NNNYY
YNNNN
YNNNN
3
1 3
3 1
4 5

Sample Output 1

1 100
2 160
3 180

For (S,T)=(U_1,V_1)=(1,3), there is a direct flight from city 1 to city 3, so the minimum possible number of direct flights is 1, which is achieved when he uses that direct flight. In this case, the total value of the souvenirs is A_1+A_3=30+70=100.

For (S,T)=(U_2,V_2)=(3,1), the minimum possible number of direct flights is 2. The following two routes achieve the minimum: cities 3\to 4\to 1, and cities 3\to 5\to 1. Since the total value of souvenirs in the two routes are 70+20+30=120 and 70+60+30=160, respectively, so he chooses the latter route, and the total value of the souvenirs is 160.

For (S,T)=(U_3,V_3)=(4,5), the number of direct flights is minimum when he travels cities 4\to 1\to 3\to 5, where the total value of the souvenirs is 20+30+70+60=180.

Sample Input 2

2
100 100
NN
NN
1
1 2

Sample Output 2

Impossible

There may be no direct flight at all.

Problem Statement

There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).

In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle. Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.

Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).

Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.

Constraints

• 1\leq H \leq 10^9
• 1\leq W \leq 10^9
• 1\leq N \leq 10^5
• 1\leq s_x,g_x\leq H
• 1\leq s_y,g_y\leq W
• 1\leq X_i \leq H
• 1\leq Y_i \leq W
• (s_x,s_y)\neq (g_x,g_y)
• (s_x,s_y)\neq (X_i,Y_i)
• (g_x,g_y)\neq (X_i,Y_i)
• If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

In the figure, (s_x,s_y) is denoted by S and (g_x,g_y) is denoted by G.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.

Sample Input 2

4 6 2
3 2
3 5
4 5
2 5

Sample Output 2

-1

He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.

Sample Input 3

1 10 1
1 5
1 1
1 7

Sample Output 3

-1

If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.