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

Problem Statement

An election is being held with N candidates numbered 1, 2, \ldots, N. There are K votes, some of which have been counted so far.

Up until now, candidate i has received A_i votes.

After all ballots are counted, candidate i (1 \leq i \leq N) will be elected if and only if the number of candidates who have received more votes than them is less than M. There may be multiple candidates elected.

For each candidate, find the minimum number of additional votes they need from the remaining ballots to guarantee their victory regardless of how the other candidates receive votes.

Formally, solve the following problem for each i = 1,2,\ldots,N.

Determine if there is a non-negative integer X not exceeding K - \displaystyle{\sum_{i=1}^{N}} A_i satisfying the following condition. If it exists, find the minimum possible such integer.

• If candidate i receives X additional votes, then candidate i will always be elected.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{12}
• 0 \leq A_i \leq 10^{12}
• \displaystyle{\sum_{i=1}^{N} A_i} \leq K
• All input values are integers.

Sample Input 1

5 2 16
3 1 4 1 5

Sample Output 1

2 -1 1 -1 0

14 votes have been counted so far, and 2 votes are left.
The C to output is (2, -1, 1, -1, 0). For example:

• Candidate 1 can secure their victory by obtaining 2 more votes, while not by obtaining 1 more vote. Thus, C_1 = 2.
• Candidate 2 can never (even if they obtain 2 more votes) secure their victory, so C_2 = -1.

Sample Input 2

12 1 570
81 62 17 5 5 86 15 7 79 26 6 28

Sample Output 2

79 89 111 117 117 74 112 116 80 107 117 106