Problem Statement

Team Takahashi and Team Aoki are playing a baseball game, with Team Takahashi batting first.
Currently, the game has finished through the top of the ninth inning, and the bottom of the ninth is about to begin.

Team Takahashi scored A_i runs in the top of the i-th inning (1\leq i\leq 9), and Team Aoki scored B_j runs in the bottom of the j-th inning (1\leq j\leq 8).
At the end of the top of the ninth, Team Takahashi's score is not less than Team Aoki's score.
Determine the minimum number of runs Team Aoki needs to score in the bottom of the ninth to win the game.

Here, if the game is tied at the end of the bottom of the ninth, it results in a draw. Therefore, for Team Aoki to win, they must score strictly more runs than Team Takahashi by the end of the bottom of the ninth.
Team Takahashi's score at any point is the total runs scored in the tops of the innings up to that point, and Team Aoki's score is the total runs scored in the bottoms of the innings.

Constraints

• 0\leq A_i, B_j\leq 99
• A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
• All input values are integers.

Sample Input 1

0 1 0 1 2 2 0 0 1
1 1 0 0 0 0 1 0

Sample Output 1

5

At the end of the top of the ninth inning, Team Takahashi has scored seven runs, and Team Aoki has scored three runs.
Therefore, if Team Aoki scores five runs in the bottom of the ninth, the scores will be 7-8, allowing them to win.
Note that scoring four runs would result in a draw and not a victory.

Sample Input 2

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Sample Output 2

1

Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

• 1\leq N\leq 100
• N is an integer.
• T and A are strings of length N consisting of o and x.

Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.

Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.

Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes

Problem Statement

You are given a horizontally written text. Convert it to vertical writing, filling spaces with *.

You are given N strings S_1, S_2, \dots, S_N consisting of lowercase English letters. Let M be the maximum length of these strings.

Print M strings T_1, T_2, \dots, T_M that satisfy the following conditions:

• Each T_i consists of lowercase English letters and *.
• Each T_i does not end with *.
• For each 1 \leq i \leq N, the following holds:
  • For each 1 \leq j \leq |S_i|, the (N-i+1)-th character of T_j exists, and the concatenation of the (N-i+1)-th characters of T_1, T_2, \dots, T_{|S_i|} in this order equals S_i.
  • For each |S_i| + 1 \leq j \leq M, the (N-i+1)-th character of T_j either does not exist or is *.

Here, |S_i| denotes the length of the string S_i.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is a string of lowercase English letters with length between 1 and 100, inclusive.

Sample Input 1

3
abc
de
fghi

Sample Output 1

fda
geb
h*c
i

Placing * as the 2nd character of T_3 puts the c in the correct position. On the other hand, placing * as the 2nd and 3rd characters of T_4 would make T_4 end with *, which violates the condition.

Sample Input 2

3
atcoder
beginner
contest

Sample Output 2

cba
oet
ngc
tio
end
sne
ter
*r

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

• If the L_i-th piece from the left is on its rightmost square, do nothing.
• Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

• 1\leq K\leq N\leq 200
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1\leq Q\leq 1000
• 1\leq L_i\leq K
• All values in input are integers.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

• The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
• The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
• The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
• The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
• The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No