Problem Statement

We have the following 3 \times 3 board with integers from 1 through 9 written on it.

You are given two integers A and B between 1 and 9, where A < B.

Determine if the two squares with A and B written on them are adjacent horizontally.

Constraints

• 1 \le A < B \le 9
• A and B are integers.

Sample Input 1

7 8

Sample Output 1

Yes

The two squares with 7 and 8 written on them are adjacent horizontally, so print Yes.

Sample Input 2

1 9

Sample Output 2

No

Sample Input 3

3 4

Sample Output 3

No

Problem Statement

There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.

Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.

Constraints

• -100 \leq x_i, y_i \leq 100
• There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
• All values in input are integers.

Sample Input 1

-1 -1
-1 2
3 2

Sample Output 1

3 -1

The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).

Sample Input 2

-60 -40
-60 -80
-20 -80

Sample Output 2

-20 -40

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:

• Sort A in descending order. Then, decrease both A_1 and A_2 by 1.

Find the number of times he performs this operation.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

4
1 2 3 3

Sample Output 1

4

The process goes as follows:

• After the 1st operation, A is (2, 2, 2, 1).
• After the 2nd operation, A is (1, 1, 2, 1).
• After the 3rd operation, A is (1, 0, 1, 1).
• After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.

Sample Input 2

3
1 1 100

Sample Output 2

2

Problem Statement

KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.

You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.

More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:

• 1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
• |S| < i \leq |T|.
• |T| < i \leq |S|.

Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.

Constraints

• S and T are strings of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

abcde
abedc

Sample Output 1

3

We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.

Sample Input 2

abcde
abcdefg

Sample Output 2

6

We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.

Sample Input 3

keyence
keyence

Sample Output 3

0

S and T are equal, so print 0.

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

• All inputs are integers.
• 1 \le K < N \le 2 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from A=(3,1,5,4,9).

• For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
  • In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18

Problem Statement

There are zero or more sensors placed on a grid of H rows and W columns. Let (i, j) denote the square in the i-th row from the top and the j-th column from the left.
Whether each square contains a sensor is given by the strings S_1, S_2, \ldots, S_H, each of length W. (i, j) contains a sensor if and only if the j-th character of S_i is #.
These sensors interact with other sensors in the squares horizontally, vertically, or diagonally adjacent to them and operate as one sensor. Here, a cell (x, y) and a cell (x', y') are said to be horizontally, vertically, or diagonally adjacent if and only if \max(|x-x'|,|y-y'|) = 1.
Note that if sensor A interacts with sensor B and sensor A interacts with sensor C, then sensor B and sensor C also interact.

Considering the interacting sensors as one sensor, find the number of sensors on this grid.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W where each character is # or ..

Sample Input 1

5 6
.##...
...#..
....##
#.#...
..#...

Sample Output 1

3

When considering the interacting sensors as one sensor, the following three sensors exist:

• The interacting sensors at (1,2),(1,3),(2,4),(3,5),(3,6)
• The sensor at (4,1)
• The interacting sensors at (4,3),(5,3)

Sample Input 2

3 3
#.#
.#.
#.#

Sample Output 2

1

Sample Input 3

4 2
..
..
..
..

Sample Output 3

0

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

7

Problem Statement

There are N cards with an integer written on each side. Card i (1 \leq i \leq N) has an integer a_i written on the front and an integer b_i written on the back.

You may choose whether to place each card with its front or back side visible.

Determine if you can place the cards so that the sum of the visible integers exactly equals S. If possible, find a placement of the cards to realize it.

Constraints

• 1 \leq N \leq 100
• 1 \leq S \leq 10000
• 1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)
• All values in the input are integers.

Sample Input 1

3 11
1 4
2 3
5 7

Sample Output 1

Yes
THH

For example, the following placements make the sum of the visible integers exactly equal S (= 11):

• Place the 1-st card with its front side visible, 2-nd with its back, and 3-rd with its back.
• Place the 1-st card with its back side visible, 2-nd with its front, and 3-rd with its front.

Therefore, outputs like HTT and THH are accepted.

Sample Input 2

5 25
2 8
9 3
4 11
5 1
12 6

Sample Output 2

No

You cannot place the cards so that the sum of the visible integers exactly equals S (= 25).

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

You are given a tree with N vertices numbered from 1 to N and an integer K. The i-th edge bidirectionally connects vertices u_i and v_i.

You are currently at vertex 1. You can repeat the following operation zero or more times:

• Choose a vertex whose distance from the vertex you are currently at is K, and move to that vertex. Here, the distance between two vertices is the number of edges in the simple path connecting the two vertices.

For each k=2,\ldots,N, determine whether you can move to vertex k by repeating the operation, and if you can move, find the minimum number of operations.

You have T test cases, so solve each of them.

Constraints

• 1\leq T\leq 10^5
• 2\leq N\leq 2\times 10^5
• 1\leq K\leq 20
• 1\leq u_i\lt v_i\leq N
• The given graph is a tree.
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

1
6 2
1 2
2 3
2 4
4 5
5 6

Sample Output 1

-1 1 1 -1 2

This sample input/output consists of one test case.

The vertices whose distance from vertex 1 is 2 are vertices 3 and 4, so you can move to these two vertices with one operation.

Also, by moving from vertex 1 to vertex 4, then moving to vertex 6 whose distance from vertex 4 is 2, you can move to vertex 6 with two operations.

You cannot move to vertices 2 and 5 no matter how you perform the operations.

Sample Input 2

3
2 20
1 2
10 2
1 9
1 8
1 5
6 8
4 5
2 8
5 10
7 9
3 5
10 1
2 6
2 9
8 9
9 10
3 9
4 9
7 9
1 6
3 5

Sample Output 2

-1
1 1 1 -1 1 1 -1 -1 1
2 4 4 5 1 4 4 3 4