Problem Statement

Given is a string S of length 3.
Move the first character of S to the end of S and print the resulting string S'.

Constraints

• S is a string of length 3 consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

bca

Moving the first character a of the string abc results in bca.

Sample Input 2

aab

Sample Output 2

aba

Problem Statement

We have a grid of H horizontal rows and W vertical columns, where some of the squares contain obstacles.
Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
You are given H strings S_1, S_2, S_3, \dots, S_H. The j-th character of S_i describes the square (i, j); # means the square contains an obstacle, and . means it does not.
We say a square is visible from another when it is on the same row or the same column, and there is no obstacle between them (including themselves).
Print the number of squares visible from the square (X, Y) (including (X, Y) itself).

Constraints

• 1 \le H \le 100
• 1 \le W \le 100
• 1 \le X \le H
• 1 \le Y \le W
• S_i is a string of length W consisting of . and #.
• The square (X, Y) does not contain an obstacle.

Sample Input 1

4 4 2 2
##..
...#
#.#.
.#.#

Sample Output 1

4

The squares visible from the square (2, 2) are:

• (2, 1)
• (2, 2)
• (2, 3)
• (3, 2)

Sample Input 2

3 5 1 4
#....
#####
....#

Sample Output 2

4

Even if two squares are on the same row or the same column, they are not visible from each other when there are obstacles between them.

Sample Input 3

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

Sample Output 3

3

Problem Statement

Given is a number sequence A of length N.
Let us divide this sequence into one or more non-empty contiguous intervals.
Then, for each of these intervals, let us compute the bitwise \mathrm{OR} of the numbers in it.
Find the minimum possible value of the bitwise \mathrm{XOR} of the values obtained in this way.

Constraints

• 1 \le N \le 20
• 0 \le A_i \lt 2^{30}
• All values in input are integers.

Sample Input 1

3
1 5 7

Sample Output 1

2

If we divide [1, 5, 7] into [1, 5] and [7], their bitwise \mathrm{OR}s are 5 and 7, whose \mathrm{XOR} is 2.
It is impossible to get a smaller result, so we print 2.

Sample Input 2

3
10 10 10

Sample Output 2

0

We should divide this sequence into [10] and [10, 10].

Sample Input 3

4
1 3 3 1

Sample Output 3

0

We should divide this sequence into [1, 3] and [3, 1].

Problem Statement

On a two-dimensional coordinate plane where the \mathrm{x} axis points to the right and the \mathrm{y} axis points up, we have a regular N-gon with N vertices p_0, p_1, p_2, \dots, p_{N - 1}.
Here, N is guaranteed to be even, and the vertices p_0, p_1, p_2, \dots, p_{N - 1} are in counter-clockwise order.
Let (x_i, y_i) denotes the coordinates of p_i.
Given x_0, y_0, x_{\frac{N}{2}}, and y_{\frac{N}{2}}, find x_1 and y_1.

Constraints

• 4 \le N \le 100
• N is even.
• 0 \le x_0, y_0 \le 100
• 0 \le x_{\frac{N}{2}}, y_{\frac{N}{2}} \le 100
• (x_0, y_0) \neq (x_{\frac{N}{2}}, y_{\frac{N}{2}})
• All values in input are integers.

Sample Input 1

4
1 1
2 2

Sample Output 1

2.00000000000 1.00000000000

We are given p_0 = (1, 1) and p_2 = (2, 2).
The fact that p_0, p_1, p_2, and p_3 form a square and they are in counter-clockwise order uniquely determines the coordinates of the other vertices, as follows:

• p_1 = (2, 1)
• p_3 = (1, 2)

Sample Input 2

6
5 3
7 4

Sample Output 2

5.93301270189 2.38397459622

Problem Statement

There are N balls, called Ball 1 through N, on a number line.
Ball i is at the coordinate X_i.
Each ball has a color represented by an integer ID between 1 and N (inclusive); the ID of the color of Ball i is C_i.
You are now at the coordinate 0. You will collect all the balls by moving along the line at the speed of 1 per second, and then return to the coordinate 0.
Here, you have to collect the balls in a non-descending order of their IDs.
When collecting a ball, you have to be at the coordinate of that ball, but it is not mandatory to collect it when you are there.
Find the minimum time needed to start at the coordinate 0, collect all the balls, and return to the coordinate 0.

Constraints

• 1 \le N \le 2 \times 10^5
• |X_i| \le 10^9
• X_i \neq X_j (i \neq j)
• X_i \neq 0
• 1 \le C_i \le N
• All values in input are integers.

Sample Input 1

5
2 2
3 1
1 3
4 2
5 3

Sample Output 1

12

The optimal strategy is:

• spend 3 seconds to reach the coordinate 3 and collect Ball 2;
• spend 1 second to reach the coordinate 2 and collect Ball 1;
• spend 2 seconds to reach the coordinate 4 and collect Ball 4;
• spend 1 second to reach the coordinate 5 and collect Ball 5;
• spend 4 seconds to reach the coordinate 1 and collect Ball 3;
• spend 1 second to return to the coordinate 0.

Here, we collected the balls in a non-descending order of their IDs: 1, 2, 2, 3, 3.

Sample Input 2

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

Sample Output 2

38

Problem Statement

We have a connected undirected graph with N vertices and M edges, which is not necessarily simple.
Edge i connects Vertex A_i and Vertex B_i, and has a character C_i written on it.
Let us make a string by choosing a path from Vertex 1 to Vertex N (possibly with repetitions of the same edge and vertex) and arrange the characters written on the edges in that path.
Determine whether this string can be a palindrome. If it can, find the minimum possible length of such a palindrome.

Constraints

• 2 \le N \le 1000
• 1 \le M \le 1000
• 1 \le A_i \le N
• 1 \le B_i \le N
• C_i is a lowercase English letter.
• The given graph is connected.

Sample Input 1

8 8
1 2 a
2 3 b
1 3 c
3 4 b
4 5 a
5 6 c
6 7 b
7 8 a

Sample Output 1

10

By traversing the edges in the order 1, 2, 3, 1, 2, 4, 5, 6, 7, 8, we can make a string abcabbacba, which is a palindrome.
It is impossible to make a shorter palindrome, so the answer is 10.

Sample Input 2

4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a

Sample Output 2

5

By traversing the edges in the order 2, 3, 4, 5, 5, we can make a string aabaa, which is a palindrome.
Note that repetitions of the same edge and vertex are allowed.

Sample Input 3

3 4
1 1 a
1 2 a
2 3 b
3 3 b

Sample Output 3

-1

We cannot make a palindrome.