Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

• |T| is odd. Here, |T| denotes the length of T.
• The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
• The (\frac{|T|+1}{2})-th character is /.
• The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

You are given a string S of length N consisting of 1, 2, and /, where S contains at least one /.
Find the maximum length of a (contiguous) substring of S that is an 11/22 string.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 1, 2, and /.
• S contains at least one /.

Sample Input 1

8
211/2212

Sample Output 1

5

The substring from the 2-nd to 6-th character of S is 11/22, which is an 11/22 string. Among all substrings of S that are 11/22 strings, this is the longest. Therefore, the answer is 5.

Sample Input 2

5
22/11

Sample Output 2

1

Sample Input 3

22
/1211/2///2111/2222/11

Sample Output 3

7

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.

When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.

• The endpoints of the chosen edges are pairwise distinct.

Constraints

• 2\leq N\leq 16
• 1\leq D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

4
1 5 4
7 8
6

Sample Output 1

13

If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.

It can be shown that this is the maximum achievable value.

Sample Input 2

3
1 2
3

Sample Output 2

3

N can be odd.

Sample Input 3

16
5 6 5 2 1 7 9 7 2 5 5 2 4 7 6
8 7 7 9 8 1 9 6 10 8 8 6 10 3
10 5 8 1 10 7 8 4 8 6 5 1 10
7 4 1 4 5 4 5 10 1 5 1 2
2 9 9 7 6 2 2 8 3 5 2
9 10 3 1 1 2 10 7 7 5
10 6 1 8 9 3 2 4 2
10 10 8 9 2 10 7 9
5 8 8 7 5 8 2
4 2 2 6 8 3
2 7 3 10 3
5 7 10 3
8 5 7
9 1
4

Sample Output 3

75

Problem Statement

A positive integer N is a 400 number if and only if it satisfies both of the following two conditions:

• N has exactly 2 distinct prime factors.
• For each prime factor p of N, p divides N an even number of times. More formally, the maximum non-negative integer k such that p^k divides N is even.

Process Q queries. Each query gives you an integer A, so find the largest 400 number not exceeding A. Under the constraints of this problem, a 400 number not exceeding A always exists.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• For each query, 36 \leq A \leq 10^{12}.
• All input values are integers.

Sample Input 1

5
404
36
60
1000000000000
123456789

Sample Output 1

400
36
36
1000000000000
123454321

Let us explain the first query.

There are exactly 2 prime factors of 400: 2 and 5. Also, 2 divides 400 four times and 5 divides it twice, so 400 is a 400 number. None of 401, 402, 403, and 404 is a 400 number, so the answer is 400.

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

There are N horizontal bars numbered from 1 to N placed on the grid. Bar i consists of L_i blocks of size 1 \times 1 connected horizontally, and its leftmost block is initially at cell (R_i, C_i). That is, initially, bar i occupies the cells (R_i, C_i), (R_i, C_i + 1), \dots, (R_i, C_i + L_i - 1). It is guaranteed that there is no cell occupied by two different bars.

The current time is t = 0. At every time t = 0.5 + n for some non-negative integer n, the following occurs in order of i = 1, 2, \dots, N:

• If bar i is not on the bottom row (the H-th row), and none of the cells directly below the cells occupied by bar i is occupied by any bar, then bar i moves down by one cell. That is, if at that time bar i occupies the cells (r,C_i),(r,C_i+1),\dots,(r,C_i+L_i-1)\ (r < H), and the cell (r + 1, C_i + j) is not occupied by any bar for all j (0 \leq j \leq L_i - 1), then bar i now occupies (r + 1, C_i), (r + 1, C_i + 1), \dots, (r + 1, C_i + L_i - 1).
• Otherwise, nothing happens.

Let (R'_i, C_i), (R'_i, C_i + 1), \dots, (R'_i, C_i + L_i - 1) be the cells occupied by bar i at time t = 10^{100}. Find R'_1, R'_2, \dots, R'_N.

Constraints

• 1 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq R_i \leq H
• 1 \leq C_i \leq W
• 1 \leq L_i \leq W - C_i + 1
• In the initial state, there is no cell occupied by two different bars.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
4
3
4

The following three diagrams represent the grid at times t = 0, 1, and 2 from left to right. Colored rectangles represent the bars, and the number inside each rectangle indicates its bar number.

The changes in the grid state are explained as follows:

• At t = 0.5:
  • i = 1: The cells directly below bar 1 are (2,2),(2,3),(2,4). Among these, (2,2) is occupied by bar 3 and (2,4) is occupied by bar 4, so nothing happens.
  • i = 2: The cells directly below bar 2 are (4,2),(4,3), which are not occupied by any other bar, so bar 2 moves down by one cell.
  • i = 3: The cells directly below bar 3 are (3,1),(3,2), which are not occupied by any other bar, so bar 3 moves down by one cell.
  • i = 4: The cell directly below bar 4 is (3,4), which is not occupied by any other bar, so bar 4 moves down by one cell.
• At t = 1.5:
  • i = 1: The cells directly below bar 1 are (2,2),(2,3),(2,4), which are not occupied by any other bar, so bar 1 moves down by one cell.
  • i = 2: Bar 2 is on the bottom row, so nothing happens.
  • i = 3: The cells directly below bar 3 are (4,1),(4,2). Among these, (4,2) is occupied by bar 2, so nothing happens.
  • i = 4: The cell directly below bar 4 is (4,4), which is not occupied by any other bar, so bar 4 moves down by one cell.

At times t = 2.5, 3.5, \dots, there is no bar such that the cells directly below it are all unoccupied, so nothing happens. Thus, the grid at time t = 10^{100} is the same as at t = 2 (the rightmost diagram above).

Therefore, R'_1 = 2, R'_2 = 4, R'_3 = 3, R'_4 = 4.

Sample Input 2

382 382 3
3 3 3
8 8 8
2 2 2

Sample Output 2

382
382
381

Sample Input 3

5 10 8
2 2 1
4 3 1
4 8 2
1 2 2
2 5 3
5 4 3
4 5 2
1 5 2

Sample Output 3

5
5
5
4
3
5
4
2