Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

• For each j=1, 2, \dots, W, simultaneously do the following:
  • simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
• For each i = 1, 2, \dots, H, simultaneously do the following:
  • simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

• After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

• 2 \leq H, W \leq 30
• A_{i,j} is # or ., and so is B_{i,j}.
• H and W are integers.

Sample Input 1

4 3
..#
...
.#.
...
#..
...
.#.
...

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

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

We first apply a vertical shift to make A as follows.

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

Then we apply another vertical shift to make A as follows.

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

Finally, we apply a horizontal shift to make A as follows, which equals B.

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

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.

Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

• Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
• The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 2

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

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

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9
• 0 \leq Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All X_i and Y_i are integers.
• S is a string of length N consisting of L and R.

Sample Input 1

3
2 3
1 1
4 1
RRL

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

2
1 1
2 1
RR

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Sample Output 3

Yes

Problem Statement

Takahashi and Aoki are competing in an election.
There are N electoral districts. The i-th district has X_i + Y_i voters, of which X_i are for Takahashi and Y_i are for Aoki. (X_i + Y_i is always an odd number.)
In each district, the majority party wins all Z_i seats in that district. Then, whoever wins the majority of seats in the N districts as a whole wins the election. (\displaystyle \sum_{i=1}^N Z_i is odd.)
At least how many voters must switch from Aoki to Takahashi for Takahashi to win the election?

Constraints

• 1 \leq N \leq 100
• 0 \leq X_i, Y_i \leq 10^9
• X_i + Y_i is odd.
• 1 \leq Z_i
• \displaystyle \sum_{i=1}^N Z_i \leq 10^5
• \displaystyle \sum_{i=1}^N Z_i is odd.

Sample Input 1

1
3 8 1

Sample Output 1

3

Since there is only one district, whoever wins the seat in that district wins the election.
If three voters for Aoki in the district switch to Takahashi, there will be six voters for Takahashi and five for Aoki, and Takahashi will win the seat.

Sample Input 2

2
3 6 2
1 8 5

Sample Output 2

4

Since there are more seats in the second district than in the first district, Takahashi must win a majority in the second district to win the election.
If four voters for Aoki in the second district switch sides, Takahashi will win five seats. In this case, Aoki will win two seats, so Takahashi will win the election.

Sample Input 3

3
3 4 2
1 2 3
7 2 6

Sample Output 3

0

If Takahashi will win the election even if zero voters switch sides, the answer is 0.

Sample Input 4

10
1878 2089 16
1982 1769 13
2148 1601 14
2189 2362 15
2268 2279 16
2394 2841 18
2926 2971 20
3091 2146 20
3878 4685 38
4504 4617 29

Sample Output 4

86