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

You are given an integer N and a string S consisting of 0, 1, and ?. Let T be the set of values that can be obtained by replacing each ? in S with 0 or 1 and interpreting the result as a binary integer. For instance, if S= ?0?, we have T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace.

Print (as a decimal integer) the greatest value in T less than or equal to N. If T does not contain a value less than or equal to N, print -1 instead.

Constraints

• S is a string consisting of 0, 1, and ?.
• The length of S is between 1 and 60, inclusive.
• 1\leq N \leq 10^{18}
• N is an integer.

Sample Input 1

?0?
2

Sample Output 1

1

As shown in the problem statement, T=\lbrace 0,1,4,5\rbrace. Among them, 0 and 1 are less than or equal to N, so you should print the greatest of them, 1.

Sample Input 2

101
4

Sample Output 2

-1

We have T=\lbrace 5\rbrace, which does not contain a value less than or equal to N.

Sample Input 3

?0?
1000000000000000000

Sample Output 3

5

Problem Statement

For positive integers X and Y, a rectangle in a two-dimensional plane that satisfies the conditions below is said to be good.

• Every edge is parallel to the x- or y-axis.
• For every vertex, its x-coordinate is an integer between 0 and X (inclusive), and y-coordinate is an integer between 0 and Y (inclusive).

Determine whether it is possible to place the following three good rectangles without overlapping: a good rectangle of an area at least A, another of an area at least B, and another of an area at least C.

Here, three rectangles are considered to be non-overlapping when the intersection of any two of them has an area of 0.

Constraints

• 1 \leq X, Y \leq 10^9
• 1 \leq A, B, C \leq 10^{18}
• All values in input are integers.

Sample Input 1

3 3 2 2 3

Sample Output 1

Yes

The figure below shows a possible placement, where the number in a rectangle represents its area.

We can see that 2 \geq A, 3 \geq B, 3 \geq C, satisfying the conditions.

Sample Input 2

3 3 4 4 1

Sample Output 2

No

There is no possible placement under the conditions.

Sample Input 3

1000000000 1000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

No

Problem Statement

There are N types of items. The i-th type of item has a weight of w_i and a value of v_i. Each type has 10^{10} items available.

Takahashi is going to choose some items and put them into a bag with capacity W. He wants to maximize the value of the selected items while avoiding choosing too many items of the same type. Hence, he defines the happiness of choosing k_i items of type i as k_i v_i - k_i^2. He wants to choose items to maximize the total happiness over all types while keeping the total weight at most W. Calculate the maximum total happiness he can achieve.

Constraints

• 1 \leq N \leq 3000
• 1 \leq W \leq 3000
• 1 \leq w_i \leq W
• 1 \leq v_i \leq 10^9
• All input values are integers.

Sample Input 1

2 10
3 4
3 2

Sample Output 1

5

By choosing 2 items of type 1 and 1 item of type 2, the total happiness can be 5, which is optimal.

Here, the happiness for type 1 is 2 \times 4 - 2^2 = 4, and the happiness for type 2 is 1 \times 2 - 1^2 = 1.

The total weight is 9, which is within the capacity 10.

Sample Input 2

3 6
1 4
2 3
2 7

Sample Output 2

14

Sample Input 3

1 10
1 7

Sample Output 3

12