Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

• N is an integer.
• 2 \leq N \leq 2 \times 10^5
• S_i is a string consisting of lowercase English letters.
• |S_i| \geq 1
• \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3

• S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
• S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
• S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

• N is an integer between 1 and 2\times 10^5, inclusive.
• S is a string of length N consisting of lowercase English letters, ,, and ".
• S contains an even number of ".

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

Problem Statement

There is a rectangular cake with some strawberries on the xy-plane. The cake occupies the rectangular area \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.

There are N strawberries on the cake, and the coordinates of the i-th strawberry are (p_i, q_i) for i = 1, 2, \ldots, N. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

• First, cut the cake along A different lines parallel to the y-axis: lines x = a_1, x = a_2, \ldots, x = a_A.
• Next, cut the cake along B different lines parallel to the x-axis: lines y = b_1, y = b_2, \ldots, y = b_B.

As a result, the cake will be divided into (A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

• 3 \leq W, H \leq 10^9
• 1 \leq N \leq 2 \times 10^5
• 0 \lt p_i \lt W
• 0 \lt q_i \lt H
• i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
• 1 \leq A, B \leq 2 \times 10^5
• 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
• 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
• p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
• q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
• All input values are integers.

Sample Input 1

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

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0, and the maximum possible number is 2.

Sample Input 2

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

Sample Output 2

1 1

Each piece has one strawberry on it.

Problem Statement

There is a town represented as an xy-plane, where Santa lives, along with N children numbered 1 to N. Santa's house is at coordinates (S_X,S_Y), and the house of child i\ (1\leq i\leq N) is at (X_i,Y_i).

Santa wants to deliver one present to each of the N children in numerical order. To deliver a present to child i, Santa must visit the house of child i with at least one present in hand. However, Santa can only carry up to K presents at a time, and he must return to his own house to replenish presents (there are enough presents at Santa's house).

Find the minimum distance Santa must travel to leave his house, deliver presents to all N children, and return to his house.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
• (S_X,S_Y)\neq (X_i,Y_i)
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• All input values are integers.

Sample Input 1

3 2
1 1
3 1
1 2
3 2

Sample Output 1

9.236067977499790

In the figure above, the red circle represents Santa's house, and the circles with numbers represent the houses of the children with those numbers.

Consider Santa acting as follows:

1. Leave his house with two presents.
2. Go to child 1's house and deliver a present.
3. Return to his house and replenish one present.
4. Go to child 2's house and deliver a present.
5. Go to child 3's house and deliver a present.
6. Return to his house.

In this case, Santa travels the distance of 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots, which is the minimum.

Sample Input 2

2 1
0 1
-1 1
1 1

Sample Output 2

4.000000000000000

Sample Input 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

Sample Output 3

11347715738.116592407226562