Problem Statement

You are given a string S consisting of lowercase English letters. The length of S is between 3 and 100, inclusive.

All characters but one of S are the same.

Find x such that the x-th character of S differs from all other characters.

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of two different lowercase English letters.
• All characters but one of S are the same.

Sample Input 1

yay

Sample Output 1

2

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

1

Sample Input 3

zzzzzwz

Sample Output 3

6

Problem Statement

Takahashi melted and mixed A grams of gold and B grams of silver (0 \leq A,B,\ 0 \lt A+B) to produce new metal.

What metal did he produce: pure gold, pure silver, or an alloy?

Formally, the product is called as follows.

• Pure gold, if 0 \lt A and B=0.
• Pure silver, if A=0 and 0 \lt B.
• An alloy, if 0 \lt A and 0 \lt B.

Constraints

• 0 \leq A,B \leq 100
• 1 \leq A+B
• All values in input are integers.

Sample Input 1

50 50

Sample Output 1

Alloy

We have 0 \lt A and 0 \lt B, so the product is an alloy.

Sample Input 2

100 0

Sample Output 2

Gold

We have 0 \lt A and B=0, so the product is pure gold.

Sample Input 3

0 100

Sample Output 3

Silver

We have A=0 and 0 \lt B, so the product is pure silver.

Sample Input 4

100 2

Sample Output 4

Alloy

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

• N is an integer.
• 1 \leq N \leq 16

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

Problem Statement

There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.

You are given M pieces of information in the following form:

• From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.

Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1\leq A_i, B_i \leq N
• A_i \neq B_i
• -10^9 \leq X_i,Y_i \leq 10^9
• All input values are integers.
• The given information is consistent.

Sample Input 1

3 2
1 2 2 1
1 3 -1 -2

Sample Output 1

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 2

3 2
2 1 -2 -1
2 3 -3 -3

Sample Output 2

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

Sample Output 3

0 0
0 0
0 0
undecidable
undecidable

The same piece of information may be given multiple times, and multiple people may be at the same coordinates.

Problem Statement

We have a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W).

Each square is one of the following: the initial point, a road, and an obstacle.
A square (i, j) is represented by a character C_{i, j}. The square is the initial point if C_{i, j} = S, a road if C_{i, j} = ., and an obstacle if C_{i, j} = #. There is exactly one initial point.

Determine whether there is a path of length 4 or greater that starts at the initial point, repeats moving vertically or horizontally to an adjacent square, and returns to the initial point without going through an obstacle or visiting the same square multiple times except at the beginning and the end.
More formally, determine whether there are an integer n and a sequence of squares (x_0, y_0), (x_1, y_1), \dots, (x_n, y_n) that satisfy the following conditions.

• n \geq 4.
• C_{x_0, y_0} = C_{x_n, y_n} = S.
• If 1 \leq i \leq n - 1, then C_{x_i, y_i} = ..
• If 1 \leq i \lt j \leq n - 1, then (x_i, y_i) \neq (x_j, y_j).
• If 0 \leq i \leq n - 1, then square (x_i, y_i) and square (x_{i+1}, y_{i+1}) are vertically or horizontally adjacent to each other.

Constraints

• 4 \leq H \times W \leq 10^6
• H and W are integers greater than or equal to 2.
• C_{i, j} is S, ., or #.
• There is exactly one (i, j) such that C_{i, j} = S.

Sample Input 1

4 4
....
#.#.
.S..
.##.

Sample Output 1

Yes

The path (3, 2) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 2) satisfies the conditions.

Sample Input 2

2 2
S.
.#

Sample Output 2

No

Sample Input 3

5 7
.#...#.
..#.#..
...S...
..#.#..
.#...#.

Sample Output 3

No

Problem Statement

There are N rooms numbered 1, 2, \ldots, N, each with one person living in it, and M corridors connecting two different rooms. The i-th corridor connects room U_i and room V_i with a length of W_i.

One day (we call this day 0), the K people living in rooms A_1, A_2, \ldots, A_K got (newly) infected with a virus. Furthermore, on the i-th of the following D days (1\leq i\leq D), the infection spread as follows.

People who were infected at the end of the night of day (i-1) remained infected at the end of the night of day i.
For those who were not infected, they were newly infected if and only if they were living in a room within a distance of X_i from at least one room where an infected person was living at the end of the night of day (i-1). Here, the distance between rooms P and Q is defined as the minimum possible sum of the lengths of the corridors when moving from room P to room Q using only corridors. If it is impossible to move from room P to room Q using only corridors, the distance is set to 10^{100}.

For each i (1\leq i\leq N), print the day on which the person living in room i was newly infected. If they were not infected by the end of the night of day D, print -1.

Constraints

• 1 \leq N\leq 3\times 10^5
• 0 \leq M\leq 3\times 10^5
• 1 \leq U_i < V_i\leq N
• All (U_i,V_i) are different.
• 1\leq W_i\leq 10^9
• 1 \leq K\leq N
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1 \leq D\leq 3\times 10^5
• 1\leq X_i\leq 10^9
• All input values are integers.

Sample Input 1

4 4
1 2 2
2 3 1
2 4 3
3 4 2
1
1
2
3 3

Sample Output 1

0
1
1
2

The infection spreads as follows.

• On the night of day 0, the person living in room 1 gets infected.
• The distances between room 1 and rooms 2,3,4 are 2,3,5, respectively. Thus, since X_1=3, the people living in rooms 2 and 3 are newly infected on the night of day 1.
• The distance between rooms 3 and 4 is 2. Thus, since X_2=3, the person living in room 4 also gets infected on the night of day 2.

Therefore, the people living in rooms 1,2,3,4 were newly infected on days 0,1,1,2, respectively, so print 0,1,1,2 in this order on separate lines.

Sample Input 2

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

Sample Output 2

0
1
2
-1
2
0
-1

Sample Input 3

5 1
1 2 5
2
1 3
3
3 7 5

Sample Output 3

0
2
0
-1
-1

Note that it is not always possible to move between any two rooms using only corridors.