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

There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i. If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• 6 \leq N \leq 1000
• \lvert S_i\rvert =N
• S_i consists of # and ..

Sample Input 1

8
........
........
.#.##.#.
........
........
........
........
........

Sample Output 1

Yes

By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.

Sample Input 2

6
######
######
######
######
######
######

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

Sample Output 3

No

Problem Statement

Determine whether there is a way to line up N people, numbered 1 to N, in a row side by side to satisfy all of the M conditions in the following format.

• Condition: Person A_i and Person B_i are adjacent.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 1\leq A_i < B_i \leq N
• All pairs (A_i,B_i) are distinct.

Sample Input 1

4 2
1 3
2 3

Sample Output 1

Yes

One way to satisfy all the conditions is to line them up in the order 4,1,3,2.

Sample Input 2

4 3
1 4
2 4
3 4

Sample Output 2

No

There is no way to line them up to satisfy all the conditions.

Problem Statement

There are N cities in a certain country.
You will travel from your office in city 1 to a destination in city N, via zero or more cities.
Two types of transportation are available: company car and train. The time required to travel from city i to city j is as follows:

• D_{i,j} \times A minutes by company car, and
• D_{i,j} \times B + C minutes by train.

You can switch from company car to train, but not vice versa.
You can do so without spending time, but only in a city.

What is the minimum time in minutes to travel from city 1 to city N?

Constraints

• 2 \leq N \leq 1000
• 1 \leq A, B, C \leq 10^6
• D_{i,j} \leq 10^6
• D_{i,i} = 0
• D_{i,j} = D_{j,i} > 0 (i \neq j)
• All input values are integers.

Sample Input 1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

Sample Output 1

78

You can travel from city 1 to city 4 in a total of 78 minutes by moving as follows.

• Travel by company car from city 1 to city 3. This takes 2 \times 8 = 16 minutes.
• Travel by company car from city 3 to city 2. This takes 3 \times 8 = 24 minutes.
• Travel by train from city 2 to city 4. This takes 5 \times 5 + 13 = 38 minutes.

It is impossible to travel from city 1 to city 4 in less than 78 minutes.

Sample Input 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

Sample Output 2

1

Sample Input 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

Sample Output 3

168604826785

Problem Statement

There are integer sequences A, B, C of length M each.

C is represented by integers x_1, \dots, x_N, y_1, \dots, y_N. The first y_1 terms of C are x_1, the subsequent y_2 terms are x_2, \ldots, the last y_N terms are x_N.

B is defined by B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).

A is defined by A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).

Find the maximum value among A_1, \dots, A_M.

You will be given T test cases to solve.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• The sum of N in a single file is at most 2 \times 10^5.
• 1 \leq M \leq 10^9
• |x_i| \leq 4 \, (1 \leq i \leq N)
• y_i \gt 0 \, (1 \leq i \leq N)
• \sum_{k = 1}^N y_k = M
• All values in input are integers.

Sample Input 1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

Sample Output 1

4
53910
2000000002000000000

In the first test case, we have:

• C = (-1, -1, 2, 2, 2, -3, -3)
• B = (-1, -2, 0, 2, 4, 1, -2)
• A = (-1, -3, -3, -1, 3, 4, 2)

Thus, the maximum value among A_1, \dots, A_M is 4.