Problem Statement

Consider an xy-plane. The positive direction of the x-axis is in the direction of east, and the positive direction of the y-axis is in the direction of north.
Takahashi is initially at point (x, y) = (0, 0) and facing east (in the positive direction of the x-axis).

You are given a string T = t_1t_2\ldots t_N of length N consisting of S and R. Takahashi will do the following move for each i = 1, 2, \ldots, N in this order.

• If t_i = S, Takahashi advances in the current direction by distance 1.
• If t_i = R, Takahashi turns 90 degrees clockwise without changing his position. As a result, Takahashi's direction changes as follows.
  • If he is facing east (in the positive direction of the x-axis) before he turns, he will face south (in the negative direction of the y-axis) after he turns.
  • If he is facing south (in the negative direction of the y-axis) before he turns, he will face west (in the negative direction of the x-axis) after he turns.
  • If he is facing west (in the negative direction of the x-axis) before he turns, he will face north (in the positive direction of the y-axis) after he turns.
  • If he is facing north (in the positive direction of the y-axis) before he turns, he will face east (in the positive direction of the x-axis) after he turns.

Print the coordinates Takahashi is at after all the steps above have been done.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• T is a string of length N consisting of S and R.

Sample Input 1

4
SSRS

Sample Output 1

2 -1

Takahashi is initially at (0, 0) facing east. Then, he moves as follows.

1. t_1 = S, so he advances in the direction of east by distance 1, arriving at (1, 0).
2. t_2 = S, so he advances in the direction of east by distance 1, arriving at (2, 0).
3. t_3 = R, so he turns 90 degrees clockwise, resulting in facing south.
4. t_4 = S, so he advances in the direction of south by distance 1, arriving at (2, -1).

Thus, Takahashi's final position, (x, y) = (2, -1), should be printed.

Sample Input 2

20
SRSRSSRSSSRSRRRRRSRR

Sample Output 2

0 1

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

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 sent a string T consisting of lowercase English letters to Aoki. As a result, Aoki received a string T' consisting of lowercase English letters.

T' may have been altered from T. Specifically, exactly one of the following four conditions is known to hold.

• T' is equal to T.
• T' is a string obtained by inserting one lowercase English letter at one position (possibly the beginning and end) in T.
• T' is a string obtained by deleting one character from T.
• T' is a string obtained by changing one character in T to another lowercase English letter.

You are given the string T' received by Aoki and N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters. Find all the strings among S_1, S_2, \ldots, S_N that could equal the string T sent by Takahashi.

Constraints

• N is an integer.
• 1 \leq N \leq 5 \times 10^5
• S_i and T' are strings of length between 1 and 5 \times 10^5, inclusive, consisting of lowercase English letters.
• The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Sample Input 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

Sample Output 1

4
1 2 3 4

Among S_1, S_2, \ldots, S_5, the strings that could be equal to T are S_1, S_2, S_3, S_4, as explained below.

• S_1 could be equal to T, because T' = ababc is equal to S_1 = ababc.
• S_2 could be equal to T, because T' = ababc is obtained by inserting the letter a at the beginning of S_2 = babc.
• S_3 could be equal to T, because T' = ababc is obtained by deleting the fourth character c from S_3 = abacbc.
• S_4 could be equal to T, because T' = ababc is obtained by changing the third character d in S_4 = abdbc to b.
• S_5 could not be equal to T, because if we take S_5 = abbac as T, then T' = ababc does not satisfy any of the four conditions in the problem statement.

Sample Input 2

1 aoki
takahashi

Sample Output 2

0

Sample Input 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

Sample Output 3

6
1 2 4 7 8 9

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.