Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence A of length N, according to the following procedure.

• First, make a cut from the center in the 12 o'clock direction.
• Next, do N operations. The i-th operation is as follows.
  • Rotate the pizza A_i degrees clockwise.
  • Then, make a cut from the center in the 12 o'clock direction.

For example, if A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

• All values in input are integers.
• 1 \le N \le 359
• 1 \le A_i \le 359
• There will be no multiple cuts at the same position.

Sample Input 1

4
90 180 45 195

Sample Output 1

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120 degrees.

Sample Input 2

1
1

Sample Output 2

359

Sample Input 3

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3

170

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

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

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

Note that the input may not fit into a 32-bit integer type.

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

• For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• (p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
• All values in input are integers.

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

• For i = 1, we have p_i = 2, q_2 = 1.
• For i = 2, we have p_i = 3, q_3 = 2.
• For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

Problem Statement

There is a printing machine that prints line segments on the xy-plane by emitting a laser.

• At the start of printing, the laser position is at coordinate (0, 0).

• When printing a line segment, the procedure below is followed.

  • First, move the laser position to one of the endpoints of the line segment.
    • One may start drawing from either endpoint.
  • Then, move the laser position in a straight line from the current endpoint to the other endpoint while emitting the laser.
    • It is not allowed to stop printing in the middle of a line segment.

• When not emitting the laser, the laser position can move in any direction at a speed of S units per second.

• When emitting the laser, the laser position can move along the line segment being printed at a speed of T units per second.
• The time required for operations other than moving the laser position can be ignored.

Takahashi wants to print N line segments using this printing machine.
The i-th line segment connects coordinates (A_i, B_i) and (C_i, D_i).
Some line segments may overlap, in which case he needs to print the overlapping parts for each line segment separately.

What is the minimum number of seconds required to complete printing all the line segments when he operates the printing machine optimally?

Constraints

• All input values are integers.
• 1 \le N \le 6
• 1 \le T \le S \le 1000
• -1000 \le A_i,B_i,C_i,D_i \le 1000
• (A_i,B_i) \neq (C_i,D_i) ( 1 \le i \le N )

Sample Input 1

3 2 1
1 3 2 1
0 2 0 0
3 0 2 0

Sample Output 1

6.44317475868633722080

• Emit the laser while moving the laser position from (0,0) to (0,2), printing the second line segment.
  • This takes 2 seconds.
• Move the laser position from (0,2) to (1,3) without emitting the laser.
  • This takes \sqrt{2}/2 seconds.
• Emit the laser while moving the laser position from (1,3) to (2,1), printing the first line segment.
  • This takes \sqrt{5} seconds.
• Move the laser position from (2,1) to (2,0) without emitting the laser.
  • This takes 1/2 second.
• Emit the laser while moving the laser position from (2,0) to (3,0), printing the third line segment.
  • This takes 1 second.
• The total time taken is 2 + (\sqrt{2}/2) + \sqrt{5} + (1/2) + 1 \approx 6.443175 seconds.

Sample Input 2

2 1 1
0 0 10 10
0 2 2 0

Sample Output 2

20.97056274847714058517

Sample Input 3

6 3 2
-1000 -1000 1000 1000
1000 -1000 -1000 1000
-1000 -1000 1000 1000
1000 -1000 -1000 1000
1000 1000 -1000 -1000
-1000 1000 1000 -1000

Sample Output 3

9623.35256169626864153344

Multiple line segments overlap here, and you need to print the overlapping parts for each line segment separately.

Sample Input 4

6 10 8
1000 1000 -1000 -1000
1000 -1000 -1000 -1000
-1000 1000 1000 1000
-1000 1000 -1000 -1000
1000 1000 1000 -1000
1000 -1000 -1000 1000

Sample Output 4

2048.52813742385702910909